Simulación universal de máquinas de Turing

16

Sea una función fija construible en el tiempo.f

El clásico resultado de la simulación universal para TMs (Hennie y Stearns, 1966) establece que hay una TM dos cintas tal queU

  • la descripción de un TM , yM
  • una cadena de entrada ,x

corre por pasos y devuelve la respuesta de en . Y se puede considerar que es cualquier función en .g(|x|)Mxsolω(f(n)lgf(n))

Mis preguntas son:

  1. ¿Cuál es el resultado de simulación más conocido en una sola cinta TM? ¿El resultado anterior también se mantiene?

  2. ¿Hay alguna mejora en [HS66]? ¿Podemos simular TM en una TM de dos cintas para pasos de una manera más rápida? ¿Podemos tomar para estar en en lugar de ?g ( n ) ω ( f ( n ) )f(n)g(n)ω(f(n))ω(f(n)lgf(n))

Kaveh
fuente
¿Debería ser el mismo número de cintas o estar limitado de alguna manera?
Raphael
Y se pueden simular múltiples cintas en tiempo cuadrático en una cinta, así que si este tipo de simulación es justa, ¿por qué espera una diferencia? ¿O el tiempo de simulación lineal es justo por otros motivos?
Raphael
"Estoy preguntando si la simulación se puede hacer con una sobrecarga lineal". No puedo hacer coincidir eso con la pregunta. ¿Quiso decir ? o(f(n))
Raphael
1
@Raphael, lo volví a verificar y actualicé la pregunta. La es correcta, tenga en cuenta que es una función arbitraria en . (en el teorema necesitamos algo que crezca más rápido que porque el alfabeto y el número de estados de la máquina simulada no son fijos, por lo que hay una constante dependiendo de la máquina. se usa por ellos.)gωgf ( n ) lg f ( n ) ωω(f(n))f(n)lgf(n)ω
Kaveh

Respuestas:

7

¿Cuál es el resultado de simulación más conocido en una sola cinta TM? ¿El resultado anterior también se mantiene?

Podemos simular una TM de cinta múltiple en una TM de cinta única con un aumento cuadrático en el tiempo. El tiempo de simulación es . El aumento cuadrático es necesario ya que hay idiomas (p. Ej., Palíndromos) que requieren tiempo Ω ( n 2 ) en un DTM de una sola cinta, pero pueden resolverse en el tiempo O ( n ) en un DTM de dos cintas.O(n2)Ω(n2)O(n)

En resumen, el resultado anterior no funciona cuando el simulador es una TM de una sola cinta.

Para la simulación de TM de una sola cinta en una TM de una sola cinta (con alfabeto finito arbitrario), el resultado es válido, es decir, la simulación se puede hacer con un aumento del factor en el tiempo. Ver (2) y (3). La referencia parece ser (6).lg

¿Hay alguna mejora en [HS66]? ¿Podemos simular TM en una TM de dos cintas para pasos de una manera más rápida? ¿Podemos tomar g ( n ) para estar en ω ( f ( n ) ) en lugar de ω ( f ( n ) lg f ( n ) ) ?f(n)g(n)ω(f(n))ω(f(n)lgf(n))

Parece que no ha habido ninguna mejora, ya que eso implicaría un mejor teorema de la jerarquía temporal que el que se conoce actualmente.

Corrección: los teoremas de jerarquía habituales se basan en clases de complejidad temporal definidas mediante TM de cinta única. Para -tape TMs, Furer demostró un resultado ajustado similar al teorema de la jerarquía espacial en 1982 (5). El factor lg no es necesario. Ver también (4).nlg

Referencias

  1. Peter van Emde Boas, "Modelos y simulación de máquinas", en Handbook of Theoretical Computer Science, 1990
    (en particular, pp. 18-21)

  2. Michael Sipser, "Introducción a la teoría de la computación", 2006
    (las clases de complejidad temporal se definen usando TM con una sola cinta infinita en ambas direcciones y un alfabeto finito arbitrario, ver páginas 140 y 341)

  3. Odifreddi, "Teoría de la recursión clásica", vol. I y II, 1989 y 1999
    (las definiciones son similares a las de Sipser, véase Def. I.4.1 en el vol. I página 48, Def. VII.4.1 en el vol. II página 67, y Thm. VII.4.15 en el vol. II página 83)

  4. Piergiorgio Odifreddi, "Teoría de la recursión clásica", vol. II, 1999
    (página 84)

  5. Martin Fürer, " La estricta jerarquía determinista del tiempo ", 1982

  6. Juris Hartmanis, " Complejidad computacional de los computadores de máquina de Turing de una cinta ", 1968

  7. FC Hennie y RE Stearns, " Simulación de dos cintas de máquinas de múltiples etapas ", 1966

  8. Otras preguntas relacionadas:

    1. Límites inferiores y separación de clases ,
    2. lgf
    3. Alfabeto de la máquina de Turing de una sola cinta ,
    4. Para el teorema de la jerarquía de tiempo, ¿cómo se traduce la entrada de manera eficiente? ,
    5. un comentario de Luca Trevisan.
Kaveh
fuente
Aún así, hay algunas cosas que aún no están del todo claras para mí, particularmente sobre 8.3 y la simulación de una sola cinta de máquinas de una sola cinta, actualizaré la respuesta si es necesario.
Kaveh
n2t(n)t(n)