Calcular la longitud de entrada en una máquina Turing de una cinta

13

En relación con esta pregunta , se me ocurrió preguntarme: ¿cuál es la complejidad del tiempo para que una máquina Turing de una sola cinta y un solo cabezal calcule la longitud de su entrada? Para ser específicos, digamos que el alfabeto de la cinta es , la entrada es una cadena en rodeada de espacios en blanco, la máquina comienza en el símbolo de entrada más a la izquierda y debe terminar en el símbolo más a la izquierda de una cadena en (nuevamente rodeado de espacios en blanco) que proporciona la representación binaria de la longitud de entrada. Esto también puede considerarse como el problema de convertir un número de unario a binario.( 0 + 1 ) ( 0 + 1 ) {0 0,1,si}(0 0+1)(0 0+1)

Es fácil resolver esto en una máquina de dos cintas o una máquina de dos cabezales en tiempo lineal (simplemente escanee la entrada con una cabeza mientras usa la otra cabeza para incrementar repetidamente un contador; incrementar es una operación de tiempo amortizado constante). Pero las soluciones de un solo cabezal que se me ocurren son solo (por ejemplo, incremente repetidamente un contador y luego muévalo en una posición a lo largo de la cinta). ¿Hay un límite inferior a juego?O(norteIniciar sesiónnorte)

Intenté algunas búsquedas, pero frases como "una cabeza" y "longitud de entrada" son tan comunes que dificultan la búsqueda de resultados conocidos sobre este problema en la literatura.

David Eppstein
fuente
Interesante ... Esto es menos obvio de lo que parece ser. Tengo curiosidad por saber si hay una relación entre un límite inferior para esto y un límite inferior para la simulación inconsciente de TM. (Cualquier TM que resuelva este problema sería, por definición, ajeno (o tendría un código innecesario).)
Daniel Apon

Respuestas:

11

No se puede calcular en el tiempo .o(nortelgnorte)

Sea una máquina que, dada una cadena de entrada detiene con el tamaño de escrito en binario en la cinta.x xMETROXX

Podemos agregar un DFA simple (tiempo lineal de espacio cero) a para verificar si el tamaño de la entrada es una potencia de dos: solo verifique que el primer bit sea 1 y el resto sea cero.METRO

Supongamos que ejecuta el tiempo . Entonces podemos decidir a tiempo que el tamaño de la entrada es una potencia de dos. En otras palabras, el siguiente idioma es decidible en . Se deduce de que debe ser regular. Pero es fácil verificar que el idioma no sea regular. Entonces no puede ejecutarse en el tiempo .METROo(nortelgnorte)o(nortelgnorte)reTyometromi(nortelgnorte)

L={0 0yok yo=2k}
reTyometromi(o(nortelgnorte))=RmisolLMETROo(nortelgnorte)
Kaveh
fuente
Echo de menos algo aquí: cuando dices que , ¿estás considerando los cálculos en una máquina de una sola cinta? Por lo general, creo que las máquinas de dos cintas se usan para definir clases de complejidad. Una pregunta muy relacionada es ¿de dónde viene el resultado anterior? reTyometromi(o(nortelgnorte))=Rmisol
Bruno
@ Bruno, sí, estoy hablando de máquinas Turing de una sola cinta. No estoy seguro de cuál es el estándar para definir las clases de complejidad, varios libros usan diferentes modelos. Creo que los documentos originales de teoría de la complejidad usaban cintas múltiples, pero parece que ha cambiado, mira esto . Para puede encontrarlo en "Teoría de la recursión clásica" vol. II y "Manual de informática teórica". reTyometromi(nortelgnorte)=Rmisol
Kaveh
Gracias por los consejos, eché un vistazo en "Classical Recursion Theory" vol. II Por el hecho de que ha cambiado, no está tan claro para mí. Por ejemplo, el libro de Sipser usa TM de una sola cinta para definir las clases de complejidad temporal, pero el libro de Hopcroft-Ullman y los más recientes de Arora-Barak y Goldreich usan TM de múltiples cintas.
Bruno
1
@ Bruno, creo que la definición más común de DTime es más complicada. Por ejemplo, la afirmación comúnmente establecida de que "no se sabe que el teorema de la jerarquía del tiempo sea estricto" solo es cierto para las máquinas de una sola cinta, para las máquinas de dos cintas se sabe que es estricto desde 1982.
Kaveh
En realidad, esta consideración sobre el teorema de la jerarquía de tiempo solo existe en los libros de texto que utilizan una TM de cinta única como modelo (por ejemplo, Sipser). Pero en otros, no hay nada sobre la falta de estanqueidad (Arora-Barak, Goldreich, etc.). Por supuesto, todo esto no es de gran importancia, pero me parece que decir que generalmente se define usando TM de una sola cinta no es cierto: algunos autores usan TM de una sola cinta, otros usan multitapa TM, y muchos autores son vagos sobre este tema ... En otras palabras, no parece haber un consenso sobre esta cuestión. reTyometromi
Bruno