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 ) ∗
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?
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.
fuente
Respuestas:
No se puede calcular en el tiempo .o ( n lgn )
Sea una máquina que, dada una cadena de entrada detiene con el tamaño de escrito en binario en la cinta.x xMETRO X X
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 .METRO o ( n lgn ) o ( n lgn ) reT i m e (nlgn )
fuente