El uso de Savitch de la mensurabilidad

8

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?

djkern
fuente

Respuestas:

9

Creo que esta definición se conoce hoy en día bajo el término función construible en el espacio . Hay funciones en el espacio sublogarítmico que son construibles en el espacio, mientras que otras no lo son.

http://dl2.acm.org/citation.cfm?id=31171 Andrzej Szepietowski: No hay funciones totalmente construibles en el espacio entre log log n y log n. Cartas de procesamiento de información 24 (6), 361-362.

Hermann Gruber
fuente
1
¡Excelente! Leeré ese periódico. Gracias Hermann
djkern