Savitch verwendet Messbarkeit

In Savitchs Arbeit von 1969 "Beziehungen zwischen nichtdeterministischen und deterministischen Bandkomplexitäten" stellt er fest, dass "alle gängigen Speicherfunktionen L (n)> = lg n messbar sind. Insbesondere ist jedes Polynom in n und lg n messbar." Seine Definition von messbar lautet: "Eine Funktion L (n) gilt als messbar, wenn es eine Turing-Maschine mit nur einem Speicherband gibt, so dass die Maschine bei einer Eingabe der Länge n nach einer Berechnung, in der die Speicherung erfolgt, anhält Der Bandkopf scannt genau L (n) Quadrate. "

Mein Problem ist also, dass ich aufgrund seiner Definition nicht verstehe, warum Speicherfunktionen L (n)> = lg n messbar wären, während Funktionen L (n) <lg n nicht messbar wären. Ist das irgendwie implizit in seiner Definition? Oder gibt es einige Veröffentlichungen, die ich lesen sollte?

Ich denke, dass diese Definition heutzutage unter dem Begriff raumkonstruierbare Funktion bekannt ist . Es gibt Funktionen im sublogarithmischen Raum, die räumlich konstruierbar sind, andere jedoch nicht.

http://dl2.acm.org/citation.cfm?id=31171 Andrzej Szepietowski: Zwischen log log n und log n gibt es keine vollständig platzierbaren Funktionen. Information Processing Letters 24 (6), 361-362.