En el artículo de Savitch de 1969, "Relaciones entre complejidades de cinta no deterministas y deterministas", afirma que "todas las funciones de almacenamiento comunes L (n)> = lg n son medibles. En particular, cualquier polinomio en ny lg n es medible". Su definición de mensurable es: "Se dice que una función L (n) es medible si hay alguna máquina de Turing con una sola cinta de almacenamiento de tal manera que, dada cualquier entrada de longitud n, la máquina se detendrá después de un cálculo en el que el almacenamiento la cabeza de la cinta escanea exactamente L (n) cuadrados ".
Entonces, mi problema es que, según su definición, no entiendo por qué las funciones de almacenamiento L (n)> = lg n serían medibles, mientras que las funciones L (n) <lg n no lo serían. ¿Es esto de alguna manera implícito en su definición? ¿O hay algunas publicaciones que debería leer?