¿Cuál es la máquina Turing universal de 2 estados no controvertida más simple?

31

Quiero codificar una máquina simple de Turing en las reglas de un juego de cartas. Me gustaría convertirlo en una máquina universal de Turing para demostrar su integridad.

Hasta ahora, he creado un estado de juego que codifica la máquina Turing de 2 estados y 3 símbolos de Alex Smith . Sin embargo, parece (sin duda basado en Wikipedia) que existe cierta controversia sobre si la máquina (2, 3) es realmente universal.

Por el bien del rigor, me gustaría que mi prueba presentara un UTM "no controvertido". Entonces mis preguntas son:

  1. ¿La máquina (2,3) generalmente se considera universal, no universal o controvertida? No sé dónde serían lugares acreditados para buscar la respuesta a esto.

  2. Si la máquina (2,3) no es ampliamente aceptada como universal, ¿cuál es la N más pequeña de tal manera que una máquina (2, N) no sea polémica como universal?

Editado para agregar: También sería útil conocer cualquier requisito para la cinta infinita para las máquinas mencionadas, si las conoce. Parece que la máquina (2,3) requiere un estado inicial de cinta que no sea periódico, lo que será un poco difícil de simular dentro de las reglas de un juego de cartas.

AlexC
fuente
3
Por cierto, no puedo decir si las preguntas de la máquina de Turing se publicarían mejor aquí o en MathOverflow. Estoy intentando aquí primero porque cs tiene una etiqueta de "máquinas de turing" y MO no. No estoy haciendo una simulación cruzada según la política, pero estoy feliz de que esta pregunta se migre si ese fuera un mejor lugar para ello.
AlexC
12
Creo que este es un lugar razonable para esta pregunta.
Suresh Venkat
44
Se agregó "universal" al título. (La máquina de Turing de 2 estados más simple se detiene desde cualquier estado al leer cualquier símbolo.)
Jeffε
1
Hace años, busqué una encuesta sobre el tema de la universalidad de los autómatas celulares en vano. parece no haberse integrado mucho en la literatura. El concepto está bastante extendido en el "folklore" en este punto, pero no se basa mucho en las definiciones / pruebas / teoría formales. Wolfram ha hecho mucho en el campo, pero como muchos han notado, gran parte de su estilo es más experimental.
vzn
2
Je Compañero de trabajo pone el documento ( arxiv.org/abs/1904.09828 ) en Slack y nerd-snipes me, busco en Google "2,18 máquina de torneado universal", y aquí estamos. ¡Felicidades!
Cian

Respuestas:

12

Ha habido algunos resultados nuevos desde el trabajo citado en las respuestas anteriores. Esta encuesta describe el estado del arte (ver Figura 1). El tamaño de la máquina Turing universal más pequeña conocida depende de los detalles del modelo y aquí hay dos resultados que son relevantes para esta discusión:

  • Hay una máquina universal estándar de 2 estados y 18 símbolos (Rogozhin 1996. TCS, 168 (2): 215–240). Aquí tenemos la noción habitual de símbolo en blanco en una o ambas direcciones de una sola cinta.
  • Hay una máquina débilmente universal de 2 estados y 4 símbolos (Neary, Woods 2009. FCT. Springer LNCS 5699: 262-273). Aquí tenemos una sola cinta que contiene la entrada finita, y una palabra constante (independiente de la entrada) repetida infinitamente a la derecha, con otra palabra constante l repetida infinitamente a la izquierda. Esto mejora en la máquina débilmente universal mencionada por David Eppstein.rl

Parece que el (2,18) es más útil para usted.

MwtMwt

Neary, Woods SOFSEM 2012, las máquinas Turing universales más pequeñas conocidas

La figura muestra las máquinas universales más pequeñas conocidas para una variedad de modelos de máquinas de Turing (tomadas de Neary, Woods SOFSEM 2012), las referencias se pueden encontrar aquí .

Niall Murphy
fuente
13

Esta no es una respuesta real a su pregunta (no sé mucho sobre el debate de la máquina (2,3)); pero le sugiero el artículo " Pequeñas máquinas de Turing y competencia generalizada de castores ocupados ". Lo leí rápidamente hace algún tiempo, y tiene un bonito gráfico con los límites entre los 4 tipos de TM pequeñas:

  • decidible
  • Abra el problema de Collatz
  • 3x+1
  • universal

foto del periódico

(Quizás se hayan mejorado algunos resultados).

La noción de TM utilizada en el documento es la definición estándar de TM utilizada en documentos en pequeñas máquinas Turing universales:

... Tienen una cinta unidimensional única infinita en ambas direcciones, y un cabezal único de lectura y escritura de dos vías. Hay un símbolo en blanco denotado por 0. Inicialmente, una palabra finita, la entrada, se escribe en la cinta, otras celdas contienen el símbolo en blanco, la cabeza lee el símbolo más a la izquierda de la entrada y el estado es el estado inicial. En cada paso, de acuerdo con el estado actual de la máquina y el símbolo leído por la cabeza, el símbolo se modifica, la cabeza se mueve hacia la izquierda o hacia la derecha (y no puede permanecer leyendo la misma celda), y el estado se modifica. El cálculo se detiene cuando se alcanza un estado de detención especial. ...

Marzio De Biasi
fuente
1
El enlace va al papel de Alex Smith, no al papel que creo que pretendías.
Jeffε
Muy útil enlace. Gracias. Parece que puedo ser mejor para una máquina (2, 18).
AlexC
Al leer ese documento, dice que las máquinas de Turing de 2 estados 3 símbolos tienen un problema de detención decidible, por lo que la máquina de Turing de 2 estados 3 símbolos Wolfram no puede ser universal.
Craig Feinstein
1
@CraigFeinstein: Wolfram (2,3) TM es ligeramente diferente de las TM habituales: no tiene un estado de detención y requiere un soporte infinito de cinta no repetitiva. Ni siquiera puede considerarse débilmente universal (una TM débilmente universal requiere un patrón repetido infinito en ambas direcciones)
Marzio De Biasi
11

También es posible lograr la universalidad con 7 estados y 2 símbolos, aunque se aplican muchas de las mismas objeciones (condiciones iniciales no uniformes en la cinta infinita y condiciones de terminación inusuales). Consulte http://11011110.livejournal.com/104656.html y http://www.complex-systems.com/abstracts/v15_i01_a01.html

Estos se basan en la simulación del autómata celular de la Regla 110, demostrado universal por Matthew Cook, y Cook también encontró una simulación de 2 estados y 5 símbolos de la Regla 110, si está casado con la restricción de que solo haya dos estados.

David Eppstein
fuente
La restricción de 2 estados será muchísimo más fácil de simular que las TM con más estados. Por el momento, creo que será más fácil para mí hacer un TM de 2 estados y 18 colores que uno con 3 estados e incluso una pequeña cantidad de colores.
AlexC
El (2, 5) es interesante y puede ser un paso intermedio útil para mí. Pero parece que desde estos enlaces tendré que subir a (2, 18) para encontrar uno que me permita comenzar con solo finitamente muchas celdas no negras en la cinta inicial. ¡Gracias!
AlexC
5

S0s<SC0c<C2LRC+4SC

En todo momento, solo la celda actual, o las dos celdas involucradas en una transición, pueden tener colores mejorados: todas las otras celdas tienen su color verdadero. Queremos que nuestra máquina se comporte de la siguiente manera: verifique qué transición real debe realizar, mueva la información del "estado verdadero" de la celda que queremos dejar a la celda objetivo (esto implica un montón de ida y vuelta), limpie el celda que dejamos (dándole un color verdadero), repite

(c,s)LR(cnew,snew,emit)L

cLc(c,0,L,receive)R

cc(c,s,emit)(c,0,L,receive)cc
ss0L

Aquí están las transiciones para implementar eso. En casi todos los casos, muévase en la dirección especificada por el estado actual, luego voltee el estado

  1. c(c,0,dir,receive)dir

  2. (c,s)(cnew,snew,emit)

  3. (c,s,emit)(c,s1,emit)s>0

  4. (c,0,emit)c

  5. (c,s,dir,receive)(c,s+1,dir,receive)dir

  6. (c,s,dir,receive)(c,s)dir

C+3SC

Bruno Le Floch
fuente
0

a menos que defina cuidadosamente "no controvertido" de alguna manera técnica, no hay una respuesta precisa. Aquí hay otra máquina pequeña basada en la regla 110 que demostró ser universal en cierto sentido, pero entiendo que requiere infinitas formulaciones periódicas de cintas de entrada (y también extracción al final cuando la máquina se detiene). no he visto el tema de la cinta "periódica versus no periódica" descrita en la literatura, aunque se ha discutido en, por ejemplo, listas de correo de matemáticas [Lista de correo de Fundamentos de Matemáticas]

vzn
fuente
-3

La prueba de universalidad de Turing de Alex Smith de la conjeturada máquina de Turing de 2 estados y 3 símbolos de Wolfram definitivamente no es controvertida. La prueba de universalidad dada (no la máquina) requiere un patrón infinito en la cinta de Turing, y la pregunta era si uno debería permitir tales configuraciones (puede pensar en la cinta generalmente en blanco como un patrón repetitivo infinito de símbolos en blanco también). La conclusión fue que, siempre y cuando la configuración en la cinta de la máquina sea fija (es decir, no cambie después de que comience su cómputo y permanezca igual para cualquier cómputo), la máquina de Turing realizará el cómputo universal. Tenga en cuenta que esto NO es controvertido para la regla 110 del autómata celular elemental de Wolfram que Wolfram y Cook demostraron ser universales. La prueba de universalidad de la regla 110 también requiere un patrón infinito en la configuración inicial, uno que sea diferente en ambos lados, por lo que es de la misma naturaleza para la máquina Turing de 2 estados y 3 símbolos. Otra preocupación era que tal relajación del requisito de la condición inicial (en blanco) haría que algunos autómatas universales no Turing aceptados sean universales, como los autómatas de estado finito, acotado lineal o hacia abajo para mencionar algunos ejemplos, pero no lo hace respeta la jerarquía de Chomsky. Por lo tanto, definitivamente no es controvertido si la máquina de Turing de 2 estados y 3 símbolos es universal, pero su prueba de universalidad requirió una variación de lo que generalmente se consideran los potentes de una cinta de máquina de Turing normal. Esto no implica directamente, por cierto, que el estado 2,

usuario2230103
fuente
Intentando analizar este largo argumento, concluyo que Smith (2,3) -TM es claramente solo universal en un sentido débil. Sin embargo, varias de las otras respuestas ya han discutido esto en detalle, con referencias a documentos con clasificaciones que intentan hacer que esta narrativa sea matemáticamente precisa. También tenga en cuenta que no todos los modelos TM suponen una cinta en blanco infinita para empezar.
András Salamon
Su comentario solo demuestra que ignora el área. No utilicé ningún concepto difícil para alguien con conocimientos básicos de las máquinas de Turing (por ejemplo, configuración inicial, símbolo en blanco, etc.). Una vez más, la única diferencia, y ya aceptada para otro tipo de autómatas, es que la máquina Smith-Wolfram Turing no parte de una cinta en blanco. Que la respuesta correcta tiene -3 muestra claramente cómo la democracia y la popularidad no significan verdad, un realización más relevante que cualquier otra cosa, dado el tipo de payasos que ahora gobiernan el mundo bajo el paraguas de la democracia.
user2230103