Quién puede nombrar el mayor número? (6/8)

Viene de aquí

Pero ¿y si tu amigo también conoce las máquinas de Turing? ¿Hay un sistema notacional para grandes números más poderosos incluso que los castores atareados?

Supón que podemos dotar a una máquina de Turing con la habilidad mágica de resolver el problema de la detención. ¿Qué podríamos conseguir? Tendríamos una `super-máquina de Turing’: una con habilidades más allá de cualquier máquina ordinaria. Pero ahora, ¿cómo de difícil es decidir si una super-máquina se detiene? Hmm. Produce que incluso las super-máquinas no pueden resolver su `super-problema de la detención’, por la misma razón que las máquinas ordinarias no pueden resolver el problema ordinario de la detención. Para resolver el problema de la detención para las super-máquinas, necesitamos una máquina incluso más poderosa: una `super-hiper-máquina’. Y para resolver el problema de la detención para la super-hiper-máquina, necesitamos una `super-hiper-mega-máquina’. Y así sucesivamente sin fin. Esta jerarquía infinita fue formalizada por el lógico Stephen Kleene en 1943 (aunque él no usó el término `super-hiper-mega’).

Imagina una novela, la cual está encajada en una novela mayor, la cual está encajada en una novela incluso mayor, y así hasta el infinito. Dentro de cada novela, los personajes pueden debatir los méritos literarios de cualquier subnovela. Pero, por analogía con las categorías de máquinas que no pueden analizarse a sí mismas, los personajes nunca podrían criticar la novela en la que ellos mismos están. (Esto, pienso, hace mofa de nuestra experiencia ordinaria de las novelas.) Para entender completamente algo de la realidad, necesitamos salir de esa realidad. Esa es la esencia de la jerarquía de Kleene: que para resolver el problema de la detención para alguna categoría de máquinas, todavía necesitamos una categoría más poderosa de máquinas.

Y no hay escapatoria. Supón una máquina de Turing con una habilidad mágica de resolver el problema de la detención, y el super-problema de la detención, y el super-hiper-problema de la detención, y el super-hiper-mega-problema de la detención, y así sucesivamente sin fin. ¿Sin duda ésta será la reina de las máquinas de Turing? No realmente. Tan pronto como queramos decidir si una `reina de las máquinas de Turing’ para, necesitaremos una máquina todavía más poderosa: una `emperatriz de las máquinas de Turing’. Y la jerarquía de Kleene continúa.

Pero ¿cómo es esto relevante para los grandes números? Bueno, cada nivel de la jerarquía de Kleene genera una sucesión de castores atareados de crecimiento más rápido que todos los niveles previos. Verdaderamente, cada nivel de la sucesión crece tan rápidamente que sólo puede ser computada por una de mayor nivel. Por ejemplo, define B₂(n) como el máximo número de pasos que una super-máquina con n reglas puede hacer antes de parar. Si esta super-sucesión de castores atareados fuese computable por super-máquinas, entonces esas máquinas podrían resolver el super-problema de la detención. Así que los super-números de los castores atareados crecen demasiado rápidamente para ser computados, incluso si pudiésemos computar los números ordinarios de los castores atareados.

Podrías pensar que ahora, en el desafío del mayor número, podrías borrar del mapa incluso a un oponente que usase la sucesión del castor atareado escribiendo algo como esto:

B₂(11111)

Pero no realmente. El problema es que nunca he visto esos “castores atareados de mayor nivel” definidos en ningún lado, probablemente porque, para la gente que conoce la teoría de computabilidad, son una bastante obvia extensión de los números ordinarios del castor atareado. Así que nuestro razonable matemático moderno no sabría qué número estás nombrando. Si quieres usar los números del castor atareado de mayor nivel en el desafío del mayor número, aquí está lo que sugiero. Primero, publica un artículo formalizando el concepto en algún periódico oscuro de bajo prestigio. Entonces, durante el desafío, cita el artículo en tu tarjeta.

Para exceder los castores atareados de mayor nivel, necesitamos presumiblemente algún modelo informático superior incluso a las máquinas de Turing. No puedo imaginar a qué se parecería ese modelo. Todavía de algún modo dudo que la historia de los sistemas notacionales para los grandes números esté acabada. Quizá algún día los humanos seamos capaces de nombrar concisamente números que hagan parecer al castor atareado 100 tan pueril y divertidamente pequeño como nuestro ochenta y tres del noble. O si jamás nombramos tales números, quizás otras civilizaciones lo hagan. ¿Está en marcha un desafío del mayor número por toda la galaxia?

Continua aquí