Uso da mensurabilidade por Savitch

No artigo de Savitch em 1969, "Relações entre complexidades de fita não determinísticas e determinísticas", ele afirma que "todas as funções comuns de armazenamento L (n)> = lg n são mensuráveis. Em particular, qualquer polinômio em n e lg n é mensurável". Sua definição de mensurável é: "Diz-se que uma função L (n) é mensurável se houver alguma máquina de Turing com apenas uma fita de armazenamento, de modo que, dada qualquer entrada de comprimento n, a máquina pare após um cálculo no qual o armazenamento a cabeça da fita digitaliza exatamente L (n) quadrados ".

Portanto, meu problema é que, com base em sua definição, não entendo por que as funções de armazenamento L (n)> = lg n seriam mensuráveis, enquanto as funções L (n) <lg n não seriam. Isso está de alguma forma implícito em sua definição? Ou existem algumas publicações que devo ler?

Penso que hoje essa definição é conhecida sob o termo função construtível no espaço . Existem funções no espaço sublogarítmico que são construtíveis no espaço, enquanto outras não.

http://dl2.acm.org/citation.cfm?id=31171 Andrzej Szepietowski: Não há funções construtivas com espaço total entre o log log n e log n. Cartas de processamento de informações 24 (6), 361-362.