Una máquina de Turing que para si existe un contraejemplo de la hipótesis de Riemann

Dibujo20160622 printer turing machine

La hipótesis de Riemann es un enunciado Π1, es decir, la hipótesis de Riemann es equivalente al problema de la parada de cierta máquina de Turing. Se sabe desde el año 1974. ¿Cuál es el número mínimo de estados para esta máquina de Turing? Matiyasevich, O’Rear y Aaronson han probado que bastan 744 estados (aquí puedes ver dicha máquina de Turing escrita en el lenguaje NQL (Not-Quite-Laconic) una versión del lenguaje Laconic de Yedidia).

Esta máquina de Turing de 744 estados es la versión optimizada de la máquina de 5372 estados desarrollada por Yedidia y Aaronson. Se basa en una expresión matemática de Davis, Matijasevic y Robinson (1974) que es válida sólo si se cumple la hipótesis de Riemann. Por comparar, la conjetura de Goldbach es equivalente al problema de la parada de una máquina de Turing de 43 estados.

El artículo que presenta la máquina de 5372 estados e inspira la de 744 es Adam Yedidia, Scott Aaronson, “A Relatively Small Turing Machine Whose Behavior Is Independent of Set Theory,” arXiv:1605.04343 [cs.FL]. La expresión matemática equivalente a la hipótesis de Riemann que se usa en el algoritmo aparece en su página 11 y fue publicada en la página 335 de Martin Davis, Yuri Matijasevic, Julia Robinson, “Hilbert’s Tenth Problem. Diophantine Equations: Positive Aspects of a Negative Solution,” in “Mathematical developments arising from Hilbert problems. Volume II”, Proceedings of Symposium of Pure Mathematics”, XXVIII: 323-378, AMS (1974). Por supuesto, me enteré de los resultados de Aaranson en su blog, “Three announcements,” Shtetl-Optimized, 09 May 2016.

Dibujo20160622 a turing machine equivalent to riemann hypothesis 1974

La búsqueda de máquinas de Turing con pocos estados que implementen algoritmos complicados es un campo muy activo entre los buenos aficionados a la informática teórica. Nació gracias al trabajo de Rado en 1962 con su famosa función Castor Afanoso (Busy Beaver). Desde entonces se han buscado máquinas de Turing mínimas para muchas funciones interesantes y para muchos problemas metamatemáticos, como la consistencia de la axiomática ZFC (la axiomática para la teoría de conjuntos de Zermelo y Fraenkel con axioma de elección). Para esta última Yedidia y Aaronson han construido una máquina de Turing con 5349 estados, que O’Rear ha reducido a sólo 1919 estados. ¡Todo un récord!

Dibujo20160622 a turing machine equivalent to riemann hypothesis

Hace años los jóvenes informáticos competíamos entre nosotros por lograr la máquina de Turing más eficiente para resolver un problema. Incluso había seminarios en los que tratábamos de mejorar las mejores implementaciones de la función Castor Afanoso de Rado. No sé si hoy en día, en un época en la que pocos estudiantes de informática estudian las máquinas de Turing, este tipo de retos tendrán interés para alguien. Pero para los que tenemos cierta edad los nuevos resultados de Aaronson y sus colegas nos retrotraen a la juventud.

1 Comentario

Participa Suscríbete

Deja un comentario

Tu email nunca será mostrado o compartido. No olvides rellenar los campos obligatorios.

Obligatorio
Obligatorio
Obligatorio

Puedes usar las siguientes etiquetas y atributos HTML: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>