¿Se pueden calcular todas las funciones que es computable en el tiempo en una máquina Turing de una sola cinta usando un alfabeto de tamaño tiempo en una máquina de Turing de una sola cinta usando un alfabeto de tamaño (digamos, y en blanco)?t k = O ( 1 ) O ( t ) 3 0 , 1 ,
(De los comentarios a continuación del OP) Tenga en cuenta que la entrada se escribe usando , pero la máquina Turing que usa un alfabeto de tamaño puede sobrescribir los símbolos de entrada con símbolos del alfabeto más grande. No veo cómo codificar símbolos en el alfabeto más grande en el alfabeto más pequeño sin tener que cambiar la entrada, lo que costaría tiempo .k n 2
Respuestas:
Una respuesta parcial si TM se ejecuta eno ( | x | logEl | x | )
Si TM4 es un TM de 4 símbolos (con alfabeto ) que calcula f : { 0 , 1 } ∗ → { 0 , 1 } , es decir, decide el idioma L = { x | f ( x ) = 1 } en ( o ( | x | log | x | ) )Σ4 4= { ϵ , 0 , 1 , 2 } f:{0,1}∗→{0,1} L={x|f(x)=1} (o(|x|log|x|))
Una complejidad de tiempo lineal determinista de cinta es1DLIN=1DTime(O(n))
Entonces es regular, y obviamente sigue siendo regular sobre el alfabeto Σ 3 = { ϵ , 0 , 1 }L Σ3={ϵ,0,1}
Entonces, hay un DFA que decide L y usa solo símbolos en . Se puede construir un TM3 de una cinta y 3 símbolos directamente desde el DFA y decide L usando la misma entrada sin relleno del TM4 original .Σ3
... no puede compilarlo directamente desde TM4, pero TM3 existe.
Si TM4 funciona en , puede cambiar la entrada y realizar una conversión directa de TM4 a TM3.Ω(n2)
Como se observó en los comentarios, el caso difícil es cuando TM4 se ejecuta en .Ω(nlogn)∩o(n2)
(1) Hennie, cálculos de máquina de Turing fuera de línea , una cinta (1965)
(2) Kobayashi, Sobre la estructura de la jerarquía de tiempo de máquina de Turing no determinista de una cinta (1985)
fuente
Para todos los tamaños de alfabeto mayores que , los tiempos de ejecución solo cambian por un factor constante ya que log k ( x ) ∈ Θ ( log l ( x ) ) para todos k , l > 1 .1 logk(x)∈Θ(logl(x)) k,l>1 fuente