El Almuerzo No Es Gratis: Por Qué las Matemáticas Obedecen a Leyes de Conservación

 La función del castor afanoso (Busy Beaver, BB) es un interesante función no computable ideada por Tibor Radó en 1962: "On Non-Computable Functions" (Sobre funciones no computables).

Imagina una máquina (una máquina de Turing, por supuesto) que 1) lee una cinta de 0s y 1s y que 2) reescribe 0s y 1s y 3) se mueve a izquierda o derecha según lo lea en una cartilla de instrucciones. Si lee en la cinta "0", acude a la fila "0" de la cartilla, columna 1, a continuación consulta la columna 2 en donde se le dice qué tiene escribir: si 0 o 1, y se mueve, bien a izquierda o a derecha, según se lo indique (I o D) la columna tercera de la cartilla. La cartilla podría tener una cuarta columna que le indicara el número de la próxima cartilla a donde leer las instrucciones. Donde empezaría de nuevo posicionándose en la fila "0" o "1" de la primera columna y así sucesivamente.

En puridad, cada "cartilla" representa un estado de la máquina. La colección completa de todas las cartillas (o filas dentro de una gran cartilla) es la tabla de transiciones de la máquina.

Todavía solo definí el funcionamiento de la Máquina de Turing.

Ahora te pregunto, ¿cuántos "1"s como mucho podría escribir una Máquina de Turing si solo tiene una cartilla de instrucciones?

Hay un número que responde a esta pregunta: 1.

¿Y con dos cartillas?

Me vas a dar otro número y quiero decirte que sepas que me estás dando los valores de BB (Busy Beaver, castor afanoso) de, ahora, para n=2, antes n=1.

Vale reformular:

BB mide la competencia para ver qué máquina de Turing (al cabo: el modelo matemático de una computadora) con un número dado de estados, que comienza con una cinta en blanco, puede:

Ejecutarse durante la mayor cantidad de pasos posible.

Escribir la mayor cantidad de símbolos '1' posible.
... antes de finalmente detenerse.

La función del Castor Afanoso, denotada como BB(n), es el número máximo de pasos que una máquina de Turing con n estados (y, por convención, 2 símbolos: 0 y 1) puede realizar antes de detenerse, cuando se inicia en una cinta en blanco.

Por cierto, existen dos variantes de la función Busy Beaver: una que cuenta el número máximo de pasos antes de parar [Σ(n)], y otra que cuenta el número máximo de símbolos '1' escritos en la cinta [S(n)]. Por plasticidad, aquí me referiré a la función de pasos, BB(n).

Imagina que tienes un conjunto de máquinas de Turing con n estados.

Filtro 1: Sólo las que se detienen. De todas las máquinas posibles, la gran mayoría se ejecutan para siempre (son "bucles infinitos"). Descartamos todas estas. Solo nos interesan las máquinas que eventualmente se detienen.

Filtro 2: El "máximo". Entre todas las máquinas que se detienen, observamos cuántos pasos dio cada una antes de parar.

El Ganador: BB(n). El valor BB(n) es el número más alto de pasos que logró dar alguna de estas máquinas antes de detenerse.

Crucial: No se permite hacer trampa. Una máquina no puede simplemente imprimir un '1' y luego entrar en un bucle infinito. Debe detenerse. El "castor" es "afanoso" porque trabaja mucho (muchos pasos, muchos '1's) pero al final del día, siempre termina su trabajo y se va a casa (se detiene).

Ahora viene el asunto: sabemos que BB (744) nos ayudaría a resolver la Hipotesis de Riemann. Otro tanto con BB (27) la conjetura de Goldbach. 

¿Por qué? Porque yo puedo ejecutar una Máquina de Turing (MT) de 744 cartillas o una MT (27) para que me busque contraejemplos que falseen, respectivamente, la Hipótesis de Riemann y la Conjetura de Goldbach, y si yo tengo que MR_T (744) +1 paso más y no encontró un contraejemplo entonces sé que nunca se parará y por tanto que NO existen contraejemplos que refuten la HR. Otro tanto con Goldbach.

Obviamente si se para y encontró un contraejemplo, pues se resolvió igualmente pero para disgusto eterno de la comunidad matemática, sobre todo a propósito de Riemann.

¿Y podríamos tener una solución a la función BB que nos permitiera dado un número n saber de inmediato su valor?

Eso, como has podido ver, nos permitiría saber que Riemann es verdadero, entre otros teoremas, sin mayor explicación de su porqué. Tendríamos un conocimiento de la verdad de Riemann sin conocimiento de causa.

Me parece terrible y en breve espero explicar por qué.

No obstante: BB no es una función computable, o dicho de otro modo, su existencia es contraria al Problema de la Parada demostrado por reducción al absurdo gracias a Turing. O dicho de otro modo, nunca podremos generar un procedimiento mecánico y efectivo que nos permita saber cuánto vale BB en el término n-simo. ¿Quieres saber cuánto vale BB(744)? Te toca coger lapiz y papel y tal vez esperar a ver unos cuantos Big Bangs y sus respectivos Big Crunchs, y la suerte de contemplarlos de manera superviviente, vaya.

Pero el Entscheidungsproblem que preguntaba Hilbert en 1928 aspiraba a un oráculo aún más poderoso que simplemente calcular BB(n). El algoritmo que soñaba sería  un oráculo de validez lógica. Le darías cualquier enunciado de primer orden, por ejemplo:

∃x (x > 0 ∧ x + 1 = 0) (Una afirmación claramente falsa en los números naturales)

Y el oráculo de Hilbert respondería directamente "VÁLIDO" O "NO VÁLIDO", sin necesidad de ejecutar ninguna máquina, sin esperar a ver si se encuentra un contraejemplo. 

Sería una evaluación puramente lógica y sintáctica. 

Este es el oráculo que Gödel demostró que no puede existir. Que Turing después demostró que no puede existir. Que Church otro tanto. ¿Dije Tarski? Pues ahora lo digo: Tarski.

¿Y por qué este excurso matemático-logicista? ¿Y por qué no? ¿No es interesante per se?

Pero volviendo a la metafísica , quiero señalar que el "almuerzo gratuito" al que el formalismo de Hilbert aspiraba choca con la concepción de compuertas de Hempel que había comentado antes.

Si las matemáticas fueran un mero juego de lenguaje, su aplicabilidad sería un milagro. Si, por el contrario, son una realidad estructurada que obedece a leyes de conservación (como la ausencia de almuerzo gratis), entonces su eficacia es racional: la física y las matemáticas son dos caras de la misma moneda estructural, ambas sujetas a las mismas leyes fundamentales de la información y la complejidad.

En aforismo: el costo de la coherencia es la prueba de la realidad. 

Voy a ver si lo puedo desgranar.

El costo de la coherencia y la imposibilidad del almuerzo gratis en matemáticas

Punto de partida: La convergencia concurrente.
Cuando un teorema profundo (Fermat, Poincaré, Riemann si se resolviera) es demostrado, observamos un fenómeno masivo de convergencia concurrente: matemáticos de distintas áreas, tradiciones y prioridades reajustan sus sistemas de creencias de forma coordinada. No es solo aceptar una cadena de símbolos, es reorganizar el conocimiento para mantener la coherencia global a la manera del Cuervo Negro de Hempel.

Movimiento 1: El Entscheidungsproblem como anhelo del free lunch
En los años 30, Hilbert preguntó: ¿podría existir un algoritmo que decidiera la verdad o falsedad de cualquier enunciado matemático?

• Esto sería el free lunch máximo: una máquina universal que resuelve cualquier problema sin el costo de la creatividad, la intuición o la reorganización comunitaria. Un móvil perpetuo de demostración infinita que viola la 2ªLey de la Termodinámica.
• La respuesta de Turing/Gödel fue un golpe a la fantasía magicista: el mundo matemático tiene una estructura que resiste la automatización total del free lunch.
• La no computabilidad de BB(n) es la expresión moderna de lo mismo: no puedes comprimir todo el conocimiento matemático en un algoritmo finito.

Movimiento 2: Los teoremas NFL (1997) como ley de conservación en la búsqueda
Wolpert y MacReady demostraron que, promediado sobre todos los problemas posibles, todo algoritmo de búsqueda y optimización se desempeña igual.

• No hay free lunch: si un algoritmo es mejor en una clase de problemas, será peor en otra.
• En matemáticas: si un método demuestra Fermat eficientemente, no puede ser óptimo para todos los teoremas.
• La especialización de Wiles (formas modulares, curvas elípticas) fue un lunch caro: años de trabajo concentrado en una dirección, que no sirve para demostrar la conjetura de Goldbach.

Movimiento 3: El costo informacional de la integración concurrente
Cuando Wiles demostró Fermat, el costo no fue solo el suyo, sino el de la comunidad:

• Verificación, generalización, recontextualización en teoría de números.
• Reajuste en geometría algebraica y formas modulares.
• Esto es análogo a actualizar una base de conocimiento distribuido manteniendo consistencia fuerte: requiere comunicación masiva y recomputación.
• Si las matemáticas fueran solo juegos de lenguaje separados (inmiscibles) como propone el nominalismo, este costo de sincronización a lo Hempel sería inexplicable.

Movimiento 4: La no-computabilidad de BB y la resistencia de Lo Real
Imagina que BB(n) fuera computable. Entonces:

• Podrías decidir muchas conjeturas (como Riemann para n=744) de manera casi gratuita.
• Pero justamente BB(n) no es computable: la información profunda sobre la estructura de los números enteros no se puede comprimir sin pérdida.
• Esto es una ley de conservación de la complejidad: el trabajo para conocer una verdad profunda es proporcional a su complejidad mínima de descripción (Kolmogorov).
• El Entscheidungsproblem y los teoremas NFL son dos caras de lo mismo: no hay atajos gratuitos para el conocimiento.

Movimiento 5: El realismo matemático como la única explicación de la coherencia costosa
Si las matemáticas son una estructura real:

1. Cualquier nueva verdad exige un reajuste global para mantener la coherencia.
2. Ese reajuste tiene un costo informacional medible (complejidad computacional, esfuerzo colaborativo).
3. Los límites formales (Entscheidungsproblem, NFL, Incompletitud) son leyes de conservación que impiden el free lunch.

Los nominalistas no pueden explicar por qué:

• Las áreas matemáticas distantes deben sincronizarse cuando se descubre una nueva verdad.
• El costo de integración es proporcional a la profundidad del resultado: conocemos con conocimiento de causa (no de manera oracular como nos regalaría BB si fuera computable).
• No podemos elegir arbitrariamente "juegos de lenguaje" incompatibles sin perder contacto con la eficacia aplicada de las matemáticas.

Conclusión: Las matemáticas como realidad estructurada
La concurrencia observada en la aceptación de teoremas profundos —junto con los límites formales que impiden el free lunch (Entscheidungsproblem, NFL, Incomputabilidad de BB)— apunta a una conclusión:
Las matemáticas son una estructura objetiva que fuerza coherencia global, y acceder a ella exige un costo proporcional a la profundidad de la verdad descubierta.

Cualquier marco filosófico que intente eludir esta realidad (constructivismo radical, nominalismo, en breve: correlacionismo) choca contra el hecho de que la información no es gratis —y las matemáticas, en su esencia, obedecen a las mismas leyes de conservación que el mundo físico.