¿Qué significa el espacio sublineal para las máquinas de Turing?

10

Se ha demostrado que el problema de decidir si una entrada es un palíndromo o no requiere espacio en una máquina Turing. Sin embargo, incluso almacenar la entrada ocupa espacio  ¿no significa eso que todas las máquinas de Turing requieren espacio ?Ω(Iniciar sesiónnorte)norteΩ(norte)

Por supuesto, no hay contradicción aquí, ya que cualquier función que use al menos espacio lineal también usa al menos espacio logarítmico. Pero escribir sugiere que es posible que una máquina de Turing use menos espacio lineal; después de todo, ¿por qué la gente pasaría todo ese tiempo probando si eso fuera exactamente lo mismo? ¿Qué parece ser un trivial obligado? Entonces, ¿qué significa para una máquina de Turing usar menos espacio lineal?Ω(Iniciar sesiónnorte)Ω(Iniciar sesiónnorte)Ω(norte)

jsguy
fuente
3
Afaik, la complejidad del espacio generalmente considera memoria adicional exactamente por esta razón. (Tenga en cuenta que su pregunta está mal planteada; desea preguntar "cómo lograr O (log n) ...".)
Raphael

Respuestas:

15

O(Iniciar sesiónnorte)O(Iniciar sesiónnorte)

Yuval Filmus
fuente
Gracias por la respuesta. ¿Por qué necesitamos convertir el índice a un formato binario? Pensé que las máquinas de Turing eran modelos abstractos de cálculo, entonces, ¿por qué deberían convertir los números decimales en sus representaciones binarias?
jsguy
44
O(Iniciar sesiónnorte)
@DavidRicherby, ¿no puede una celda de cinta contener un número que tiene más de un dígito?
jsguy
44
@jsguy Actualice la definición de máquinas de Turing. Una celda de cinta contiene un solo símbolo del alfabeto.
David Richerby
@DavidRicherby, ¡gracias, creo que tiene sentido para mí ahora!
jsguy