La máquina de Turing (2,3) de dos estados y tres colores.
Se ha demostrado que es de tipo «Universal»
El premio sobre una pequeña Maquina de Turing (2,3) ofrecido por Stephen Wolfram ya tiene ganador oficial: Alex Smith, un estudiante de veinte años de la Universidad def Birmingham en el Reino Unido, quien ha demostrado que sí es universal. La cuantía eran 25.000 dólares pero, lo que es más importante, gana también el prestigio de haber superado el reto. Lo cuentan en:
- Simplest «universal computer» (New Scientist Tech)
- Student snags maths prize (Nature)
- College Kid Proves That Wolfram's Turing Machine is the Simplest Universal Computer (Wired)
- Simple Turing machine shown capable of solving any computational problem (Ars Technica)
(No está mal con veinte años salir en Nature, ¿eh?)
Esta demostración de que tan pequeña máquina de Turing es universal bate el récord de simplicidad de la máquina (2,5) conjeturada por el propio Wolfram y confirmada por Matthew Cook.
En la web de Wolfram se explican qué son y cómo funcionan las máquinas de Turing. Esta en concreto, capaz de emular a cualquier otro ordenador o sistema de software (si se conocen las reglas que se deben emular y se preparan las condiciones iniciales adecuadas) sería «el más pequeño sistema computacional posible, capaz de emular a cualquier otro». Como dicen en Nature, éste no era un problema especialmente relavante hoy en día, sino más bien una curiosidad del mundo «retro» de las máquinas de Turing, algo que tuvo su momento de popularidad en los 60 y los 70.
En cierto modo esta solución se ha tardado 50 años en encontrar y la ha hallado un joven en sus ratos libres durante las vacaciones, para sorpresa de todos los matemáticos (y el propio Wolfram). Apropiadamente para su edad, Alex se enteró de que daban un premio por resolver el problema… en un chat de Internet.
Actualización (30 de octubre de 2007): Surgió cierta controversia sobre si la demostración es correcta. Puede leerse el mensaje original apuntando un error elemental, la noticia en Slashdot y la posterior respuesta de Wolfram Research sobre el tema, así que el debate está abierto. (¡Gracias a Christian y Gauleng por el aviso!)
(Vía una nota de Mathpuzzle.)
