¿Quién puede nombrar el mayor número? (5/8)
Viene de aquí
“Muy bien”, dices (o quizá dices “no muy bien”). “¿Pero qué tiene todo esto que ver con los grandes números?” ¡Ajá! La conexión no fue publicada hasta mayo de 1962. Entonces, en el Bell System Technical Journal, acurrucado entre artículos dispuestos pragmáticamente sobre “Estructuras multipuerto” y “Sellos de presión dirigidos por ondas”, aparecía el modestamente titulado “Sobre funciones no computables” por Tibor Rado. En este artículo, Rado presentaba los mayores números que nadie jamás había imaginado.
Su idea era simple. Como nosotros clasificamos las palabras según cuantas letras contengan, podemos clasificar las máquinas de Turing mediante cuántas reglas tienen en su cabezal. Algunas máquinas tienen sólo una regla, otras tienen dos reglas, todavía otras tienen tres reglas, y así sucesivamente. Pero por cada número entero fijo n, así como hay sólo un número finito de palabras con n letras, así también hay sólo un número finito de máquinas con n reglas. Entre estas máquinas, algunas pararán y otras funcionarán por siempre cuando comiencen con una cinta en blanco. De las que paran, pregunta Rado, ¿cuál es el máximo número de pasos que cualquier máquina hace antes de que pare? (Realmente, Rado preguntaba principalmente sobre el máximo número de símbolos que cualquier máquina puede escribir en la cinta antes de pararse. Pero el máximo número de pasos, que Rado llamaba S(n), tiene la mismas propiedades básicas y es más fácil razonar sobre él.)
Rado llamó a este máximo el n-ésimo número del “castor atareado”. (Ah sí, los tempranos 1960 eran una edad más inocente.) Él visualizó cada máquina de Turing como un castor bullendo ocupadamente a lo largo de la cinta, escribiendo y borrando símbolos. El desafío, entonces, es encontrar el castor más ocupado con exactamente n reglas, aunque no uno infinitamente ocupado. Podemos interpretar este desafío como la búsqueda del “más complicado” programa de ordenador de n bits de tamaño: el que hace la mayor cantidad de material, pero no una infinita cantidad.
Ahora, supón que conocemos el n-ésimo número del castor ocupado, que llamaremos B(n). Entonces podríamos decidir si cualquier máquina de Turing con n reglas se para partiendo una cinta en blanco. Sólo tenemos que ejecutar la máquina: si se para, bien; pero si no se para en B(n) pasos, entonces sabemos que nunca se parará, puesto que B(n) es el máximo número de pasos que podría hacer antes de parar. De igual manera, si sabes que todos los mortales murieron antes de cumplir 200 años, entonces si Sally vivió para cumplir 200, podrías concluir que Sally era inmortal. Así que ninguna máquina de Turing puede listar los números del castor atareado... porque si pudiese, podría resolver el problema de la detención, que ya sabemos que es imposible.
Pero hay un hecho curioso. Supón que podemos nombrar un número mayor que el n-ésimo castor atareado B(n). Llamémosle a este número d de dique, ya que como un dique de castor, es un techo para el castor atareado que está debajo. Con d en mano, computar el propio B(n) se vuelve fácil: sólo necesitamos simular todas las máquinas de Turing con n reglas. Las que no se hayan parado en d pasos (las que quiebran el tejado del dique) nunca pararán. Así que podemos listar exactamente qué máquinas paran, y entre ellas, el máximo número de pasos que cualquier máquina emplea antes de parar es B(n).
¿Conclusión? La secuencia de números del castor atareado, B(1), B(2), y sucesivos, crece más rápido que cualquier secuencia computable. Más rápido que los exponenciales, los exponenciales apilados, y la sucesión de Ackermann, ya que la nombras. Porque si una máquina de Turing pudiese computar una sucesión que crece más rápido que el castor atareado, entonces podríamos usar esa secuencia para obtener las d, el dique del castor. Y con esas d, se podría listar los números del castor atareado, lo cual (¿te suena familiar?) ya sabemos que es imposible. La sucesión del castor atareado es no computable, exclusivamente porque crece estupendamente rápido ...demasiado rápido para que cualquier ordenador pueda seguir con ella, incluso en principio.
Esto significa que ningún programa de ordenador puede listar todos los castores atareados uno por uno. Esto no significa que castores atareados específicos necesiten permanecer eternamente desconocidos. Y de hecho, fijarlos ha sido un pasatiempo de la informática desde que Rado publicó entonces su artículo. Es fácil verificar que B(1), el primer número del castor atareado, es 1. Eso es porque si una máquina de Turing de una regla no para después del primer paso, continuará moviéndose a lo largo de la cinta interminablemente. No hay lugar para cualquier otro comportamiento más complejo. Con dos reglas podemos hacer más, y un pequeño trabajo determinó que B(2) es 6. Seis pasos. ¿Y sobre el tercer castor atareado? En 1965 Rado, junto con Shen Lin, provó que B(3) es 21. La tarea fue ardua, requiriendo análisis humano de muchas máquinas para probar que no paraban... ya que, recuérdese, no hay algoritmo para listar los número del castor atareado. Después, en 1983, Allan Brady probó que B(4) es 107. ¿Poco impresionante hasta ahora? Bueno, como con la sucesión de Ackermann, no nos dejemos engañar por los primeros números.
En 1984, A. K. Dewdney, dedicó una columna de Scientific American a los castores atareados, los cuales inspiraron al matemático aficionado George Uhing a construir un dispositivo especial para simular las máquinas de Turing. El dispositivo, que le costó a Uhing menos de 100$, encontró una máquina de cinco reglas que ejecutaba 2 133 492 de pasos antes de parar... estableciendo que B(5) debe ser al menos tan grande. Entonces, en 1989, Heiner Marxen y Jürgen Buntrock descubrieron que B(5) es al menos 47 176 870. Hasta hoy, B(5) no ha sido fijado con precisión, y podría resultar ser todavía mucho mayor. Para B(6), Marxen y Buntrock establecieron otro récord en 1997 probando que es al menos 8 690 333 381 690 951. Una conclusión formidable, todavía Marxen, Buntrock, y los otros cazadores de castores atareados meramente vadean en las orillas de lo desconocido. La humanidad nunca podrá saber el valor de B(6) con certeza, dejemos en paz a B(7) o cualquier otro número mayor de la sucesión.
Verdaderamente, ya los primeros competidores de cinco y seis reglas nos eluden: no podemos explicar como `trabajan’ en términos humanos. Si la creatividad imbuye su diseño, no es porque los humanos la pusieran ahí. Una manera de entender esto es que incluso pequeñas máquinas de Turing pueden codificar profundos problemas matemáticos. Tomemos la conjetura de Goldbach, de que todo número par mayor o igual a 4 es la suma de dos números primos: 10=7+3, 18=13+5. La conjetura ha resistido demostración desde 1742. Todavía podríamos diseñar una máquina de Turing con, oh, digamos 100 reglas, que prueben cada número par para ver si es una suma de dos primos, y parase sólo si encuentra un contraejemplo a la conjetura. Entonces conociendo B(100), podríamos en principio ejecutar este máquina durante B(100) pasos, viendo si para, y así resolver la conjetura de Goldbach. No necesitamos aventurarnos lejos en la sucesión para entrar en la guarida del basilisco.
Pero como Rado acentúa, incluso si no podemos listar los números del castor atareado, ellos están perfectamente bien definidos matemáticamente. Si alguna vez retas a un amigo al desafío del mayor número, te sugiero que escribas algo como esto:
B(11111), suc. castor atareado, 1, 6, 21, etc.
Si tu amigo no conoce las máquinas de Turing o similares, pero sólo conoce, digamos, los números de Ackermann, entonces tú ganas el desafío. Tu incluso ganarías si concedes a tu amigo un handicap, y le permites todo el tiempo de existencia del universo para escribir su número. La clave al desafío del mayor número es un potente paradigma, y la teoría de Turing de computación es en verdad potente.
2 comentarios
oso96_2000 -
daniel -