En su libro A New Kind of Science , 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 (2,3) máquina de Turing ) podría ser universal como bien. [1]
El 14 de mayo de 2007, Wolfram anunció un premio de $ 25,000 que ganaría la primera persona que probara o refutara la universalidad de la (2,3) máquina de Turing. [2] El 24 de octubre de 2007, se anunció que el premio había sido ganado por Alex Smith, un estudiante de electrónica e informática en la Universidad de Birmingham , por su prueba de que era universal, aunque la prueba fue inicialmente disputada.
Descripción
La siguiente tabla indica las acciones a realizar por 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 a imprimir, la dirección en cuál debe mover el cabezal de la cinta, y el estado subsiguiente de la máquina.
A B 0 P1, R, B P2, L, A 1 P2, L, A P2, R, B 2 P1, L, A P0, R, A
La (2,3) máquina de Turing:
- No tiene estado de parada;
- Se relaciona trivialmente con otras 23 máquinas por intercambio de estados, símbolos y direcciones.
Minsky (1967) argumentó brevemente que las máquinas estándar (2,2) no pueden ser universales y M. Margenstern (2010) proporcionó una demostración matemática [3] basada en un resultado de L. Pavlotskaya en 1973 (no publicado pero mencionado en el artículo de Margenstern) ; por 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 multiplicado por número de símbolos). Sin embargo, los resultados no son directamente comparables, porque Minsky solo considera las 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 poder, pero quizás relevantes para lo que se puede expresar usando un número dado de estados y símbolos; no existe una definición formal estándar única. La máquina (2,3) de Turing también requiere una entrada infinita no repetitiva, lo que vuelve a hacer problemática una comparación directa con las pequeñas máquinas universales de Turing 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 se ha probado estrictamente en el sentido clásico, y la afirmación está abierta a debate si se tiene en cuenta 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 formas novedosas de definir la universalidad computacional más independientes 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 determinada depende únicamente del contenido de la fila. inmediatamente encima de él.
Aunque la máquina tiene un cabezal con solo dos estados y una cinta que puede contener solo tres colores (dependiendo del contenido inicial de la cinta), la salida de la máquina puede ser notablemente compleja. [4]
Prueba de universalidad
El 24 de octubre de 2007, Wolfram Research anunció que Alex Smith, un estudiante de electrónica e informática en 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. [5] [6] [7] [8] [9] [10] [11] [12] [13] [14] [15]
La prueba mostró que la máquina es equivalente a una variante de un sistema de etiquetas que ya se sabe que es universal. Smith primero construyó una secuencia de sistemas de reglas que muestran 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 procede en dos etapas. La primera parte emula la evolución finita de cualquier sistema de etiquetas cíclicas de dos colores. La emulación es una combinación de una serie de emulaciones que involucran los sistemas de reglas indexadas del 'sistema 0' al 'sistema 5'. Cada sistema de reglas emula al siguiente de la secuencia. Smith luego mostró 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 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 . [16] Ese principio establece que si uno ve un comportamiento que no es obviamente simple, el comportamiento corresponderá a un cálculo que en cierto sentido es "máximamente sofisticado". [17] La demostración 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. [18] Por ejemplo, una máquina tan pequeña y simple puede integrarse o construirse utilizando una pequeña cantidad de partículas o moléculas. Pero el algoritmo del "compilador" de Smith implica que no produce código compacto o eficiente, al menos para cualquier cosa que no sean 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.
Disputa
El anuncio de que la prueba de Alex Smith había ganado se hizo sin la aprobación del comité de jueces, [19] como señaló Martin Davis , un miembro del comité, en una publicación en la lista de correo de FOM :
- "Hasta donde yo sé, ningún miembro del comité ha aprobado la validez de esta prueba de 40 páginas. La determinación de que la prueba de Smith es correcta parece haber sido hecha en su totalidad por la organización Wolfram. Tengo entendido que la E / S implica codificaciones complejas ". [20]
Vaughan Pratt posteriormente impugnó la exactitud de esta prueba en una publicación en la lista de correo, [21] señalando que técnicas similares permitirían que un autómata delimitado lineal (o LBA) fuera universal, lo que contradecirí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 reiniciarse 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. [22] Las discusiones sobre la prueba continuaron durante algún tiempo entre Alex Smith, Vaughan Pratt y otros. [23]
Ver también
- Completitud de Turing : la capacidad de simular cualquier máquina de Turing
- Regla 110 - un autómata celular elemental completo de Turing
Referencias
- ^ Wolfram, Stephen (2002). Un nuevo tipo de ciencia . pag. 709 . Consultado el 10 de febrero de 2009 .
- ^ "Premio de investigación Wolfram 2,3 Turing Machine" . Consultado el 10 de febrero de 2009 .
- ^ "Máquinas de Turing con dos letras y dos estados" . Sistemas complejos . 2010 . Consultado el 25 de octubre de 2017 .
- ^ "Estudiante engancha premio de matemáticas" . Natural . 2007 . Consultado el 10 de febrero de 2009 .
- ^ Keim, Brandon (24 de octubre de 2007). "College Kid demuestra que la máquina de Turing de Wolfram es la computadora universal más simple" . Cableado . Consultado el 10 de febrero de 2009 .
- ^ Geoff Brumfiel. "Nature.com" . Nature.com . Consultado el 9 de marzo de 2010 .
- ^ "Nuevo científico" . Nuevo científico . Consultado el 9 de marzo de 2010 .
- ^ "U de Birmingham" . Newscentre.bham.ac.uk . Consultado el 9 de marzo de 2010 .
- ^ "Matemáticas en las noticias de Math Society" . Ams.org . Consultado el 9 de marzo de 2010 .
- ^ Crighton, Ben (26 de noviembre de 2007). "Demostrando la computadora simple de Turing" . BBC News . Consultado el 9 de marzo de 2010 .
- ^ "Artículo de Bitwise Mag" . Artículo de Bitwise Mag. 24 de octubre de 2007 . Consultado el 9 de marzo de 2010 .
- ^ "Asociación Matemática de América" . Maa.org . Consultado el 9 de marzo de 2010 .
- ^ Minkel, JR (25 de octubre de 2007). "Un nuevo tipo de autor científico paga 25.000 dólares a los estudiantes universitarios inteligentes para identificar la computadora más simple" . Scientific American . Consultado el 9 de marzo de 2010 .
- ^ "más revista" . Plus.maths.org . Consultado el 9 de marzo de 2010 .
- ^ Stuart, Tom (29 de noviembre de 2007). "Prueba compleja de una computadora muy simple" . The Guardian . Londres . Consultado el 9 de marzo de 2010 .
- ^ "Respuesta de Stephen Wolfram en la lista FOM" . Universidad de Nueva York . Octubre de 2007.
- ^ "El premio Wolfram y la computación universal: es su problema ahora" .
- ^ "La 'computadora universal' más simple gana $ 25,000 para estudiantes" . Nuevo científico . 24 de octubre de 2007 . Consultado el 28 de enero de 2016 .
- ^ http://cs.nyu.edu/pipermail/fom/2007-October/012163.html
- ^ http://cs.nyu.edu/pipermail/fom/2007-October/012132.html
- ^ "Mensaje de Vaughan Pratt a la lista de FOM" .
- ^ "Primera respuesta de Alex Smith a Vaughan Pratt en la lista de FOM" .
- ^ "Archivo de lista de FOM para noviembre de 2007" . Cs.nyu.edu . Consultado el 9 de marzo de 2010 .
Bibliografía
- Wolfram, S (2002) Un nuevo tipo de ciencia . Wolfram Media.
- Wolfram Research, Inc., "Premio anunciado por determinar los límites de la computación de la máquina de Turing". Anuncio formal de que Alex Smith ha ganado el premio.
- -, Premio Wolfram 2,3 Turing Machine Research. Invitación a concursantes.
Lectura histórica
- Marvin Minsky (1967) Computación: máquinas finitas e infinitas . Prentice Hall.
- Turing, A (1937) "Sobre números computables con una aplicación al problema de Entscheidung ", Actas de la London Mathematical Society Series 2, 42 : 230-265.
- - (1938) "Sobre números computables, con una aplicación al problema Entscheidungs . Una corrección", Actas de la London Mathematical Society Series 2, 43 : 544-546.
enlaces externos
- " Estudiante engancha premio de matemáticas " Naturaleza . Publicado en Internet el 24 de octubre de 2007.
- " College Kid demuestra que la máquina de Turing de Wolfram es la computadora universal más simple ", Wired Science . Publicado en Internet el 24 de octubre de 2007.
- "La 'computadora universal' más simple gana $ 25,000 para los estudiantes ", New Scientist . Publicado en Internet el 24 de octubre de 2007.
- " El premio Wolfram y la computación universal: es su problema ahora ", Dr. Dobb's Journal . Publicado en Internet el 22 de octubre de 2007.
- Minkel, JR, " Un nuevo tipo de autor científico paga 25.000 dólares a los estudiantes universitarios por identificar la computadora más simple ", Scientific American , 25 de octubre de 2007.
- De los hilos de discusión de Foundations of Mathematics:
- Máquinas simples de Turing, Universalidad, Codificaciones, etc.
- La máquina de Turing universal más simple
- La máquina universal más pequeña
- La afirmación de Vaughan Pratt de que la prueba de Smith no es válida
- Respuesta de Wolfram a Pratt en el mismo foro
- Respuesta a Pratt por Todd Rowland, uno de los jueces del premio