Un juego de niños que se tuerce
Imagina una regla sencilla: toma 1, multiplícalo por 2, suma 1, multiplícalo por 2, suma 1… Repite. Al cabo de diez pasos, obtienes un número razonable. Al cabo de cien, tu calculadora muestra un error. Al cabo de mil, ningún ordenador del mundo puede almacenar el resultado. Sin embargo, la regla es de una banalidad desconcertante. ¿Qué ocurre en realidad?
Este tipo de vértigo aritmético no es una simple curiosidad de recreo matemático. Afecta a algo profundo: los límites de lo que las matemáticas pueden conocer de sí mismas. Y en el centro de esta historia hay un objeto tan fascinante como inquietante: la función Busy Beaver.
Cuando la tortuga adelanta al cohete
Para entender por qué algunos números son «demasiado grandes» para las matemáticas, primero hay que comprender qué significa calculable. Se dice que una función es calculable si una máquina —un ordenador, teóricamente infinito en memoria y tiempo— puede producir su resultado en un número finito de pasos. La suma es calculable. La multiplicación también. Incluso funciones que crecen a una velocidad prodigiosa, como la función de Ackermann —que apila exponenciales sobre exponenciales—, siguen siendo calculables: lentas de calcular, desde luego, pero accesibles en principio.
La función Busy Beaver, en cambio, juega en otra categoría. Introducida por el matemático Tibor Radó en 1962, plantea una pregunta aparentemente inocente: entre todas las máquinas de cálculo (llamadas máquinas de Turing) que tienen exactamente n estados internos, ¿cuál se detiene tras haber escrito el mayor número de símbolos en su cinta? Ese máximo, denotado BB(n), es el valor de la función Busy Beaver para n.
Una máquina de Turing, para quienes no estén familiarizados con ella, es un modelo teórico de ordenador: lee y escribe símbolos en una cinta infinita siguiendo reglas precisas según su estado interno. Es el modelo abstracto en el que se basa toda la informática moderna. Cuantos más estados tiene una máquina, más cosas complejas puede hacer.
Resultado: BB(1) = 1. BB(2) = 6. BB(3) = 21. BB(4) = 107. ¿Y BB(5)? Aún no se conoce con certeza: las estimaciones actuales lo sitúan en torno a 47 millones. BB(6) supera 10 elevado a 18 267, es decir, un 1 seguido de más de dieciocho mil ceros. ¿Y BB(7)? Nadie lo sabe. Nadie puede saberlo.
La velocidad límite de la aritmética
No es una cuestión de potencia de cálculo insuficiente. Es un límite fundamental, de la misma naturaleza que la velocidad de la luz en física. La función Busy Beaver crece más rápido que cualquier función calculable. Sea cual sea el algoritmo que inventes, por retorcido que sea, BB(n) lo supera a partir de cierto índice. Está demostrado matemáticamente.
Y la consecuencia es asombrosa: calcular BB(n) para valores siquiera modestos de n es imposible en principio. No «difícil». No «largo». Imposible. Ninguna máquina, ningún algoritmo, ningún método sistemático puede producir esos valores. La función Busy Beaver es lo que se denomina no calculable: existe matemáticamente, pero escapa a cualquier procedimiento mecánico.
«La función Busy Beaver es como un horizonte: sabes que existe, pero nunca puedes alcanzarlo.»
—
Gödel ya lo advirtió
Para entender por qué este límite es tan profundo, hay que remontarse a los años treinta y a los trabajos de Kurt Gödel. En 1931, este lógico austriaco demostró dos teoremas que sacudieron los fundamentos de las matemáticas. El primero dice, simplificando, que todo sistema lógico suficientemente potente contiene enunciados verdaderos que no puede demostrar. El segundo: un sistema así no puede demostrar su propia coherencia.
Estos teoremas de incompletitud significan que existe una frontera entre lo verdadero y lo demostrable. Y la función Busy Beaver se encuentra precisamente en esa frontera, o más bien al otro lado. Determinar el valor de BB(n) para valores de n suficientemente grandes equivale a resolver problemas que las matemáticas estándar —las que usamos a diario, basadas en los axiomas de Zermelo-Fraenkel— sencillamente no pueden decidir.
Investigadores han mostrado recientemente que ciertos valores de BB están vinculados a cuestiones indecidibles en sistemas lógicos concretos. Por ejemplo, BB(748) —un número de magnitud inconcebible— está conectado directamente con la coherencia de la aritmética de Peano, el sistema formal que describe los números enteros. Dicho de otro modo: para conocer BB(748), haría falta un sistema lógico más potente que la propia aritmética.
Niveles de lógica apilados como muñecas rusas
Ante estos límites, los matemáticos no se quedan de brazos cruzados. Inventan nuevos marcos lógicos —sistemas de axiomas más fuertes, capaces de demostrar más cosas—. Pero cada nuevo sistema se topa con las limitaciones que impone Gödel. Entonces hay que inventar otro, aún más potente. Y así sucesivamente, hasta el infinito.
Es una imagen vertiginosa: las matemáticas no son un edificio finito, sino una torre cuya cima nunca podemos ver. Cada piso permite ver más lejos y darse cuenta de que todavía queda más por construir.
Lo que revela la función Busy Beaver es que esta jerarquía no es abstracta. Está codificada en números concretos, surgidos de reglas aritméticas infantiles. Sumas, multiplicaciones, máquinas de estados finitos. Y, sin embargo, estos números contienen toda la complejidad de los fundamentos de las matemáticas.
Ideas clave
Para los amantes de las matemáticas
La función Busy Beaver BB(n) se define como el máximo número de «1» que escribe una máquina de Turing de n estados antes de detenerse, partiendo de una cinta vacía. Una máquina de Turing de n estados es un autómata finito con un alfabeto binario {0, 1}, una cinta infinita y una tabla de transición: a cada par (estado, símbolo leído) le asigna un símbolo que escribir, una dirección de desplazamiento (izquierda o derecha) y un nuevo estado (o la detención).
La no calculabilidad de BB se demuestra por reducción al problema de la detención: si BB fuera calculable, se podría decidir si una máquina de Turing cualquiera se detiene; bastaría con simular todas las máquinas de n estados hasta el umbral BB(n). Ahora bien, el problema de la detención es indecidible (Turing, 1936), por lo que BB tampoco es calculable.
Con mayor precisión, BB crece más rápido que cualquier función recursiva total: para toda función calculable f : ℕ → ℕ, existe un índice n₀ tal que para todo n ≥ n₀, BB(n) > f(n). Esta propiedad sitúa a BB estrictamente más allá de toda jerarquía constructiva de crecimiento (jerarquía de Grzegorczyk, función de Ackermann, etc.).
El vínculo con la incompletitud de Gödel es formal: para un sistema axiomático recursivamente enumerable T suficientemente expresivo, existe un entero n_T tal que T no puede demostrar el valor exacto de BB(n) para n ≥ n_T. Trabajos recientes han precisado estos umbrales para sistemas como la aritmética de Peano (PA) o ZFC.
