Esta máquina de Turing tiene dos estados y tres colores.
¿Es universal o no? La demostración se paga a 25.000 dólares
Seguramente ni el propio Stephen Wolfram ni su equipo han podido resolver este problema durante los últimos años, de modo que ahora lo abren al público con «premio», y ofrecen 25.000 dólares a quien pueda demostrar si cierta Máquina de Turing es universal o no. Se trata de una máquina de Turing de tipo (2,3) –dos estados, tres colores– que si se demostrara que es universal batiría el récord de simplicidad de la máquina (2,5) conjeturada por el propio Wolfram y confirmada por Matthew Cook. Para ganar el concurso hay que presentar una demostración válida de que es universal, aunque también se puede ganar demostrando que no es universal… Y tal vez suceda que no existen dichas demostraciones (¿valdría demostrar eso? seguramente también) Esa máquina (2,5) es la actual campeona entre todas las máquinas universales por su simplicidad; está creada a partir del autómata celular denominado Regla 110: tiene tan sólo dos estados y cinco colores, pero no se sabe si es la más «pequeña» posible de todas ellas (ver en la propia web de Wolfram qué son y cómo funcionan las máquinas de Turing). Este tipo de máquinas de Turing universales son capaces 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 – lo cual está lejos de ser realmente práctico, pero no por ello las hace menos universales. La «universalidad» de esta pequeña máquina de Turing (2,3) sería un gran descubrimiento de resultar ser realmente «el más pequeño sistema computacional posible, capaz de emular a cualquier otro». Este tipo de autómatas y máquinas forman parte importante de A New Kind of Science, uno de los más impresionantes, y también polémicos, trabajos de Stephen Wolfram, creador también del conocido software Mathematica.
(Vía Slashdot.)
