Omega: el número del conocimiento algorítmico

FECHA

29 de marzo de 2025

CATEGORÍA

Rubén Rodríguez Abril

En este artículo presentamos a Omega, una constante matemática definida por Gregory Chaitin en el marco de la teoría algorítmica de la información, que señala qué probabilidad tiene una máquina universal de Turing de pararse en un programa aleatorio, con un entorno y un juego de instrucciones dado. El conocimiento de todos sus bits tendría consecuencias sísmicas en el ámbito de la lógica formal y la teoría de la computación.

¿Qué programas se detienen?

Imagina que generamos infinitas cadenas de bits al azar, de tamaños, y las alimentamos una a una a una CPU para que las ejecute. Algunas cadenas representan programas válidos: tal vez imprimen un número, resuelven una operación, ejecutan un pequeño bucle o simplemente no hacen nada. Pero muchas otras, inevitablemente, contendrán errores lógicos o simplemente quedarán atrapadas para siempre en un bucle infinito —como un while(true) sin escape.

¿Cuál es la proporción (sobre uno) de las cadenas que terminan? ¿Cuántas se detienen y cuántas terminan atascadas en un bucle sin fin? La constante de Chaitin, denotada como Ω, da una respuesta precisa —aunque paradójicamente no computable— mide la proporción de programas aleatorios que consiguen pararse.

La constante de Chaitin

Los programas de ordenador y sus funciones, en la medida en que se forman a partir de la composición de funciones recursivas (operaciones aritméticas, condicionales, etc..), pueden ser considerados ellos mismos como funciones recursivas computables, que toman entrada una cadena de bits $x$ (en la que se integran todos los argumentos) y producen otra cadena de salida $y$ .

Avanzando un paso más en esta generalización, una función universal $F$ es una suerte de “computador” que toma una cadena de bits de entrada $w+x$ y produce otra cadena $y$ , donde $w$ representaría el programa a ejecutar por la función universal, $x$ los datos de entrada y $+$ el operador de concatenación. Las funciones de programación son diferentes instancias de esta función universal, cuyo código está descrito por la sección $w$ .

El número $\Omega_{F}$ o constante de Chaitin señala qué probabilidad tiene esta función universal o computadora de pararse cuando se le presenta con una cadena aleatoria de bits. Es un número no computable, situado entre el 0 y el 1, cuya fórmula es la siguiente:

\Omega_{F} = \sum_{p \in \text{todas las cadenas que se paren}} 2^{-|p|}

Todos las cadenas deben ser prefijo-libre, es decir: si, por ejemplo, 11001101 es una cadena válida, su prefijo 1100110 no puede serlo. O, viceversa, si 11 es una cadena válida, ninguna cadena más larga que la tenga por prefijo (p.e. 110) lo es. El sumatorio recorre todas estas cadenas.

Hay un numero Ω para cada función/máquina universal.

Implementación en un procesador

Para implementar la citada ecuación en un escenario realista construiremos un procesador dotado de un juego de instrucciones, arquitectura y entorno que lo hagan Turing-completo (más abajo detallaremos este concepto). Los posibles programas de ordenador se representan por flujos binarios (es decir, cadenas de unos y ceros) plenamente interpretables sin ambigüedad alguna por el procesador.

Las cadenas de flujo binario se integran por las siguientes secciones:

Encabezado ( $e$ ). Señala cuál es la longitud de la sección de código $w$ . Se representa mediante una serie ininterrumpida de N ceros, seguida por una secuencia de N bits que especifica la longitud exacta del sección de código. Así, 000101 y 00001101 para sendos programas de 5 y 13 bits, respectivamente. La presencia de este encabezado equivale a que las cadenas sean prefijo-libres.
Sección de código ( $w$ ). Almacena el código a ejecutar.
Sección de datos ( $z$ ). Contiene los argumentos o parámetros de entrada del programa/función.

Juego de instrucciones Turing-completo

Cada instrucción viene precedida por un prefijo de dos bits, que señala la longitud de la misma, que puede oscilar entre 1 y 4 bytes. El juego de instrucciones debe ser Turing-completo, lo que implica que ha de cumplir las siguientes condiciones:

Deben existir registros que describan el estado interno del procesador, así como instrucciones que permitan acceder y modificarlos. Todos los registros se inicializan en cero (estado inicial de la máquina).

La memoria RAM, al igual que la cinta de la máquina de Turing, debe ser infinita. Deben existir instrucciones que permitan leer y escribir en la misma, así como acceder a posiciones variables (que equivale al movimiento de la máquina a lo largo de la cinta).

En la arquitectura deben estar presentes instrucciones condicionales de flujo (saltos, condiciones) que permitan la construcción de bucles while, que son aquellos que se siguen iterando hasta que una condición se cumpla.

Deben existir instrucciones aritméticas que permitan realizar comparativas y, en base a ellas, tomar las decisiones a las que se refiere el punto anterior.

Ausencia de interrupciones (avisos al procesador desde dispositivos periféricos), dado que una máquina de Turing (equivalente matemático de una función universal) opera siempre en pleno aislamiento del exterior.

A medida que el procesador lee la cadena de dígitos, una tabla le señala a qué instrucción corresponde cada terna de bits. No debe de existir ambigüedad de ninguna clase en dicha tabla. Si el código en bits no aparece en dicha tabla o si la instrucción es inválida (p.e. división entre cero), el procesador se limita a no hacer nada (NOP) y a pasar a la siguiente instrucción. El programa se para cuando se consumen todos sus bits. Y se cuelga (no se para) cuando en algún momento de su ejecución entra en un bucle infinito.

Cálculo de omega

Una vez construida la arquitectura de nuestro procesador, procedemos a crear y a ordenar las cadenas a ejecutar, lo que se realizará del siguiente modo:

Las cadenas serán agrupadas por su longitud. Se generarán primero las de 2 bits, después las de 3 bits, y así sucesivamente.

En cada grupo de cadenas de la misma longitud, todas serán ordenadas de mayor a menor.

Estas dos condiciones aseguran que haya una correspondencia 1 a 1 entre dichas cadenas y el conjunto N de los números naturales.

Figura 1. En la imagen se representan las primeras cadenas generadas. En azul, los ceros iniciales, en verde, la longitud de la sección de código, en negro, el código.

A medida que se generan las cadenas, el procesador las ejecuta una por una. Ω es inicializado en cero. Si un programa se para, sumamos a Ω la cantidad de 2^–^|^p^|, donde |p| es la longitud en bits de toda su cadena |p|. Si entra en un bucle infinito, no se suma nada. El resultado es la siguiente suma infinita:

\Omega = \sum_{p \in \text{programas que se detienen}} 2^{-|p|}

La detención de un programa implica sumar un bit a Ω. La posición de ese bit en la cadena decimal es igual al tamaño N del programa. Así, si el programa mide 4, se suma 0,0001. La condición de que los programas sean prefijo-libres tiene dos consecuencias trascendentales:

-La suma, a pesar de ser infinita, converge a un número igual o menor que 1. Su valor señala cuál es la probabilidad de que una cadena elegida al azar contenga un programa que se pare. Si todos los programas se paran, Ω es igual a 1.

-La decidibilidad de los programas de más de N bits no contribuye a los primeros N bits del número omega.

La cualidad oracular de Omega

La segunda consecuencia reviste una importancia fundamental, porque implica lo siguiente:

“Si conocemos los N primeros dígitos de Ω, podemos resolver el problema de la parada para los programas de longitud igual o inferior a N”

Supongamos que conocemos dichos dígitos. En ese caso, ponemos a funcionar el procesador, que recorre todas las cadenas binarias y va sumando los bits correspondientes a los programas que se paran, hasta que se obtenga el valor truncado (conocido) de omega para N. En ese caso, tendremos la certeza absoluta de que el resto de los programas se colgarán.

Este resultado es muy importante, porque asegura la resolución de los teoremas de la teoría de números. Por ejemplo, creemos un programa de ordenador con un bucle while, que va recorriendo exhaustivamente todo el conjunto de los número naturales, y que sólo se quiebra cuando el número en cuestión contradice la famosa Conjetura de Goldbach. Si el programa se para, la conjetura es falsa, si no lo hace, es cierta.

Figura 2. Para n = 28, el programa encuentra dos parejas de números que suman precisamente dicha cantidad. Consiguientemente, el bucle no se rompe y algoritmo sigue corriendo.

Omega contiene en su expansión binaria el destino de todos los algoritmos ejecutables por una máquina/función universal. Es un número no computable por ninguna función recursiva, y por lo tanto, inaccesible para ningún autómata. Es un número definible por una sencilla fórmula, pero a la vez incognoscible.

El acceso a Ω tendría las consecuencias siguientes:

-Resolución del problema de la parada de Turing.

-La noción de incompletitud, introducida por Gödel en los años 30, quedaría expulsada de la matemática formal. Todos los teoremas serían demostrables o falsables.

-Obtendríamos acceso pleno a los contenidos de El Libro (The Book) de Paul Erdos, una suerte de repositorio místico de las demostraciones matemáticas perfectas y sobresalientes por su elegancia, custodiado por un Supremo Fascista (SF) que sólo permitía a los matemáticos humanos echar vistazos ocasionales a sus páginas.

-El ámbito de la criptografía se vería especialmente sacudido. Los ataques de preimagen a las funciones hash (base de la tecnología blockchain), el problema del logaritmo discreto (ruptura de las firmas con clave elíptica) y la factorización en primos con facilidad números de gran longitud (quiebra del sistema de firma RSA) podrían simplificarse extraordinariamente si se reducen a problemas de parada, con respuesta booleana. Por ejemplo, en RSA cada par de claves pública y privada está vinculado a un número de centenares de bits llamado módulo, que es producto de dos factores primos. El algoritmo de firma se rompe cuando logramos encontrar a estos últimos. Mediante consultas binarias al oráculo podríamos ir acotando progresivamente el rango de búsqueda. Como mucho, necesitaríamos n-1 consultas, donde n es el tamaño en bits del módulo. El problema pasaría a ser soluble en tiempo lineal O(n).

Figura 3. Impresión artística del número Omega creada por DALL-E 3.

Accesibilidad a Omega desde el ámbito transfinito

Como ya habíamos señalado en el artículo anterior, cuando un programa se para, se agrega un bit a Ω. Si no se para, el bit -ubicado en la posición señalada por la longitud del programa |p|- será igual a cero.

El problema es que Alan Turing mostró ya en los años 30 que el problema de la parada es semidecidible: sabemos cuándo un programa se ha parado, pero si sigue funcionando no sabemos si seguirá corriente indefinidamente o si se parará en el futuro. Por ejemplo, si el algoritmo detector de contraejemplos a la conjetura de Goldbach ha estado corriendo durante más 1.000 millones de años y sigue sin pararse, ¿ello es porque no se va a parar nunca o porque el número natural en el que se parará es extraordinariamente grande? ¿agregamos o no el bit correspondiente?

Los primeros N dígitos de Ω quedan definidos por completo (y no se modifican más) en un tiempo de estabilización T, que es aquél en el que el último algoritmo que debía detenerse efectivamente se para. T es un número no computable, salvo en el caso restringido en que todos los programas de longitud menor que N se paren (en cuyo caso, tendríamos una cadena compuesta exclusivamente por unos).

Figura 4. Un dios omnisciente del mundo digital. Representación artística de una máquina capaz de determinar el problema de la parada de Turing para todos los algoritmos. Es una máquina que opera en la bruma del tiempo transfinito, donde todos los dígitos de Ω son computables, es resoluble el problema de la parada de Turing y desaparecen las limitaciones impuestas por los teoremas de Gödel. La máquina conoce el comportamiento de todos los algoritmos y la decidibilidad de cualquier teorema matemático.

Ω es, pues, computable en el límite: allí donde ha sido superado definitivamente el tiempo de estabilización, por muy grande que sea éste. Ello sucede, para cualquier función universal, en el tiempo transfinito ω + 1, donde ω es el número ordinal infinito más grande que cualquier número natural.

Así, pues una hipotética máquina que operara en tiempo transfinito, desde fuera del tiempo físico, accedería a todos los dígitos de Ω, resolvería el problema de la parada y quedaría liberada de las limitaciones impuestas por el teorema de Gödel. Sería un auténtico oráculo de la sabiduría, una suerte de criatura omnisciente del mundo digital, que desde la cúspide del tiempo contemplaría con certeza el destino de todos los algoritmos.