En su libro Un nuevo tipo de ciencia , Stephen Wolfram describió una máquina de Turing universal de 2 estados y 5 símbolos , y conjeturó que una máquina de Turing particular de 2 estados y 3 símbolos (en adelante máquina de Turing (2,3) ) también podría ser universal. [1]
El 14 de mayo de 2007, Wolfram anunció un premio de 25.000 dólares que ganaría la primera persona que demostrara o refutara la universalidad de la máquina de Turing (2,3). [2] El 24 de octubre de 2007, se anunció que el premio lo había ganado Alex Smith, un estudiante de electrónica e informática de la Universidad de Birmingham , por su prueba de que era universal. Dado que la prueba se aplica a un modelo de máquina de Turing no estándar que permite infinitas configuraciones iniciales no periódicas, algunos la categorizan como "débilmente universal". [3]
Claude Shannon planteó por primera vez explícitamente la cuestión de encontrar la máquina de Turing universal más pequeña posible en 1956. Demostró que dos símbolos eran suficientes siempre que se utilizaran suficientes estados (o viceversa) y que siempre era posible intercambiar estados por símbolos.
La siguiente tabla indica las acciones que debe realizar la máquina de Turing dependiendo de si su estado actual es A o B , y el símbolo que se está leyendo actualmente es 0, 1 o 2. Las entradas de la tabla indican el símbolo que se debe imprimir, la dirección en la que se debe mover el cabezal de la cinta y el estado posterior de la máquina.
La máquina de Turing (2,3):
Minsky (1967) argumentó brevemente que las máquinas estándar (2,2) no pueden ser universales y M. Margenstern (2010) proporcionó una prueba matemática [4] basada en un resultado de L. Pavlotskaya en 1973 (no publicado pero mencionado en el artículo de Margenstern); por lo tanto, podría parecer que la máquina de Turing (2,3) sería la máquina de Turing universal más pequeña posible (en términos de número de estados por número de símbolos). Sin embargo, los resultados no son directamente comparables, porque Minsky solo considera máquinas que se detienen explícitamente, lo que la máquina (2,3) no hace. De manera más general, casi todas las definiciones formales de las máquinas de Turing difieren en detalles irrelevantes para su potencia, pero tal vez relevantes para lo que se puede expresar utilizando un número dado de estados y símbolos; no existe una única definición formal estándar. La máquina de Turing (2,3) también requiere una entrada infinita que no se repita, lo que nuevamente hace problemática una comparación directa con las pequeñas máquinas de Turing universales anteriores.
Por lo tanto, aunque puede ser cierto que la máquina (2,3) es en cierto sentido la "máquina de Turing universal más pequeña posible", esto no ha sido probado estrictamente en el sentido clásico, y la afirmación está abierta al debate cuando se toman en consideración las definiciones tradicionales de universalidad y si la relajación de las propiedades de la máquina de Turing utilizadas para la prueba se puede permitir en general e incluso puede sugerir nuevas formas de definir la universalidad computacional de manera más independiente de elecciones arbitrarias (como tener una configuración de detención o requerir una cinta en blanco).
El estado de la cabeza (gota hacia arriba o hacia abajo (A y B respectivamente)) y el patrón de color (blanco, amarillo y naranja (0, 1 y 2 respectivamente)) en una fila dada dependen únicamente del contenido de la fila inmediatamente superior.
Aunque la máquina tiene un cabezal con sólo dos estados y una cinta que puede contener sólo tres colores (dependiendo del contenido inicial de la cinta), la salida de la máquina aún puede ser arbitrariamente compleja. [5]
El 24 de octubre de 2007, Wolfram Research anunció que Alex Smith, un estudiante de electrónica y computación de la Universidad de Birmingham (Reino Unido), demostró que la máquina de Turing (2,3) es universal y, por lo tanto, ganó el premio Wolfram descrito anteriormente. [6] [7] [8] [9] [10] [11] [12 ] [13] [14] [15] [16]
La prueba demostró que la máquina es equivalente a una variante de un sistema de etiquetas que ya se sabía que era universal. Smith construyó primero una secuencia de sistemas de reglas que mostraban que la máquina de Turing (2,3) es capaz de realizar cálculos finitos arbitrarios. Luego empleó un enfoque novedoso para extender esa construcción a cálculos ilimitados. La prueba se desarrolla en dos etapas. La primera parte emula la evolución finita de cualquier sistema de etiquetas cíclico de dos colores. La emulación es una composición de una serie de emulaciones que involucran los sistemas de reglas indexados del "sistema 0" al "sistema 5". Cada sistema de reglas emula al siguiente en la secuencia. Smith luego demostró que, aunque la condición inicial de la máquina de Turing (2,3) no es repetitiva, la construcción de esa condición inicial no es universal. Por lo tanto, la máquina de Turing (2,3) es universal.
Wolfram afirma que la prueba de Smith es otra prueba del Principio general de equivalencia computacional (PCE) de Wolfram. [17] Ese principio establece que si uno ve un comportamiento que no es obviamente simple, el comportamiento corresponderá a un cálculo que es en cierto sentido "máximamente sofisticado". [18] La prueba de Smith ha desatado un debate sobre las condiciones operativas precisas que debe satisfacer una máquina de Turing para ser candidata a máquina universal.
Una máquina de Turing universal (2,3) tiene aplicaciones concebibles. [19] Por ejemplo, una máquina tan pequeña y simple puede ser incorporada o construida usando una pequeña cantidad de partículas o moléculas. Pero el "compilador" que implica el algoritmo de Smith no produce código compacto o eficiente, al menos para cualquier cosa que no sea los casos más simples. Por lo tanto, el código resultante tiende a ser astronómicamente grande y muy ineficiente. Si existen codificaciones más eficientes que permitan a la máquina de Turing (2,3) calcular más rápidamente es una pregunta abierta.
El anuncio de que la prueba de Alex Smith había ganado se hizo sin la aprobación del comité de evaluación, [20] como señaló Martin Davis , miembro del comité, en una publicación en la lista de correo de FOM:
Posteriormente, Vaughan Pratt cuestionó la exactitud de esta prueba en una publicación en la lista de correo, [22] señalando que técnicas similares permitirían que un autómata lineal acotado (o LBA) fuera universal, lo que contradiría un resultado conocido de no universalidad debido a Noam Chomsky . Alex Smith se unió a la lista de correo después de este mensaje y respondió al día siguiente explicando que un LBA requeriría ser reiniciado manualmente para volverse universal usando la misma configuración inicial, mientras que su construcción reinicia la máquina de Turing automáticamente sin intervención externa. [23] Las discusiones sobre la prueba continuaron durante algún tiempo entre Alex Smith, Vaughan Pratt y otros. [24]
La prueba de Smith finalmente se publicó en la revista Complex Systems de Wolfram en 2020. [25]