La constante de Chaitin

En el subcampo de la teoría de la información algorítmica de la informática , una constante de Chaitin ( número omega de Chaitin ) ^{[ 1 ]} o probabilidad de parada es un número real que, en términos informales, representa la probabilidad de que un programa construido aleatoriamente se detenga . Estos números se forman a partir de una construcción debida a Gregory Chaitin .

Aunque existen infinitas probabilidades de parada, una para cada método de codificación de programas (universal, véase más abajo), es común usar la letra Ω para referirse a ellas como si solo hubiera una. Dado que Ω depende de la codificación del programa utilizada, a veces se la denomina construcción de Chaitin cuando no se hace referencia a ninguna codificación específica.

Cada probabilidad de parada es un número real normal y trascendental que no es computable , lo que significa que no existe ningún algoritmo para calcular sus dígitos. Cada probabilidad de parada es aleatoria según el criterio de Martin-Löf , lo que significa que ni siquiera existe un algoritmo que pueda adivinar sus dígitos de forma fiable.

La definición de probabilidad de parada se basa en la existencia de una función universal computable sin prefijos. Intuitivamente, dicha función representa un programa en un lenguaje de programación con la propiedad de que ningún programa válido puede obtenerse como una extensión propia de otro programa válido.

Supongamos que F es una función parcial que toma un argumento, una cadena binaria finita, y posiblemente devuelve una única cadena binaria como salida. La función F se llama computable si hay una máquina de Turing que la calcula, en el sentido de que para cualesquiera cadenas binarias finitas x e y , F ( x ) = y si y solo si la máquina de Turing se detiene con y en su cinta cuando se le da la entrada x .

La función F se denomina universal si para cada función computable f de una sola variable existe una cadena w tal que para todo x , F ( w x ) = f ( x )  ; donde w x  representa la concatenación de las dos cadenas w y x . Esto significa que F puede utilizarse para simular cualquier función computable de una variable. De manera informal, w representa un "script" para la función computable f , y F representa un "intérprete" que analiza el script como un prefijo de su entrada y luego lo ejecuta sobre el resto de la entrada.

El dominio de F es el conjunto de todas las entradas p sobre las que está definida. Para F que son universales, tal p puede verse generalmente tanto como la concatenación de una parte de programa y una parte de datos, como un único programa para la función F.

La función F se denomina libre de prefijos si no existen dos elementos p y p ' en su dominio tales que p ' sea una extensión propia de p . Esto puede reformularse como: el dominio de F es un código libre de prefijos (código instantáneo) en el conjunto de cadenas binarias finitas. Una forma sencilla de garantizar la ausencia de prefijos es utilizar máquinas cuya entrada sea un flujo binario del que se puedan leer bits uno a uno. No existe un marcador de fin de flujo; el final de la entrada se determina cuando la máquina universal decide dejar de leer bits, y los bits restantes no se consideran parte de la cadena aceptada. Aquí, la diferencia entre las dos nociones de programa mencionadas en el párrafo anterior se hace evidente: una se reconoce fácilmente mediante alguna gramática formal , mientras que la otra requiere un cálculo arbitrario para su reconocimiento.

El dominio de cualquier función universal computable es un conjunto enumerable computable , pero nunca un conjunto computable . El dominio siempre es Turing equivalente al problema de la parada .

Sea P _F el dominio de una función universal computable sin prefijos F . La constante Ω _F se define entonces como

$${\displaystyle \Omega _{F}=\sum _{p\in P_{F}}2^{-|p|},}$$

donde | p | denota la longitud de una cadena p . Esta es una suma infinita que tiene un sumando para cada p en el dominio de F. El requisito de que el dominio sea libre de prefijos, junto con la desigualdad de Kraft , asegura que esta suma converge a un número real entre 0 y 1. Si F es claro por el contexto, entonces _ΩF puede denotarse simplemente Ω , aunque diferentes funciones universales computables libres de prefijos conducen a diferentes valores de Ω .

Conociendo los primeros N bits de Ω , se podría calcular el problema de parada para todos los programas de tamaño hasta N. Sea p el programa para el cual se va a resolver el problema de parada, de longitud N bits. De forma secuencial , se ejecutan todos los programas de todas las longitudes hasta que suficientes se hayan detenido para contribuir conjuntamente con la probabilidad suficiente para coincidir con estos primeros N bits. Si el programa p aún no se ha detenido, entonces nunca lo hará, ya que su contribución a la probabilidad de parada afectaría a los primeros N bits. Por lo tanto, el problema de parada se resolvería para p .

Dado que muchos problemas importantes de la teoría de números , como la conjetura de Goldbach , equivalen a resolver el problema de la parada para programas especiales (que básicamente buscarían contraejemplos y se detendrían si encontraran uno), conocer suficientes bits de la constante de Chaitin implicaría también conocer la respuesta a estos problemas. Pero como el problema de la parada no tiene solución general, calcular más que los primeros bits de la constante de Chaitin es imposible para un lenguaje universal. Esto reduce los problemas difíciles a problemas imposibles, de forma similar a como lo sería intentar construir una máquina oráculo para el problema de la parada .

El espacio de Cantor es el conjunto de todas las secuencias infinitas de 0 y 1. Una probabilidad de parada puede interpretarse como la medida de un subconjunto del espacio de Cantor bajo la medida de probabilidad usual en dicho espacio. Es de esta interpretación que las probabilidades de parada toman su nombre.

La medida de probabilidad en el espacio de Cantor, a veces llamada medida de moneda justa, se define de modo que para cualquier cadena binaria x el conjunto de secuencias que comienzan con x tiene medida 2 ^{− | x |} . Esto implica que para cada número natural n , el conjunto de secuencias f en el espacio de Cantor tales que f ( n ) = 1 tiene medida ⁠ 1 / 2 ⁠ , y el conjunto de secuencias cuyo n th elemento es 0 también tiene medida ⁠ 1 / 2 ⁠ .

Sea F una función universal computable sin prefijos. El dominio P de F consiste en un conjunto infinito de cadenas binarias.

$${\displaystyle P=\{p_{1},p_{2},\ldots \}.}$$

Cada una de estas cadenas p _i determina un subconjunto S _i del espacio de Cantor; el conjunto S _i contiene todas las secuencias en el espacio de Cantor que comienzan con p _i . Estos conjuntos son disjuntos porque P es un conjunto libre de prefijos. La suma

$${\displaystyle \sum _{p\in P}2^{-|p|}}$$

representa la medida del conjunto

$${\displaystyle \bigcup _{i\in \mathbb {N} }S_{i}.}$$

De esta forma, Ω _F representa la probabilidad de que una secuencia infinita de 0s y 1s seleccionada al azar comience con una cadena de bits (de longitud finita) que pertenezca al dominio de F. Por esta razón, Ω _F se denomina probabilidad de parada.

Cada constante de Chaitin Ω tiene las siguientes propiedades:

• Es algorítmicamente aleatorio (también conocido como aleatorio de Martin-Löf o 1-aleatorio). ^{[ 2 ]} Esto significa que el programa más corto para generar los primeros n bits de Ω debe tener un tamaño de al menos n − O(1) . Esto se debe a que, como en el ejemplo de Goldbach, esos n bits nos permiten averiguar exactamente qué programas se detienen entre todos los de longitud como máximo n .
• En consecuencia, es un número normal , lo que significa que sus dígitos están distribuidos equitativamente como si se hubieran generado lanzando una moneda justa .
• No es un número computable ; no existe ninguna función computable que enumere su expansión binaria, como se explica más adelante.
• El conjunto de números racionales q tales que q < Ω es computablemente enumerable ; ^{[ 3 ]} un número real con tal propiedad se llama número real izquierda-ce en la teoría de la recursión .
• El conjunto de números racionales q tales que q > Ω no es computacionalmente enumerable. (Razón: todo número real izquierdo con esta propiedad es computable, lo cual no ocurre con Ω ).
• Es un número aritmético .
• Es Turing equivalente al problema de la parada y, por lo tanto, se encuentra en el nivel Δ 0 2   de la jerarquía aritmética .

No todo conjunto que sea Turing equivalente al problema de la parada es una probabilidad de parada. Una relación de equivalencia más fina , la equivalencia de Solovay, puede usarse para caracterizar las probabilidades de parada entre los reales izquierda-ce. ^{[ 4 ]} Se puede demostrar que un número real en [0,1] es una constante de Chaitin (es decir, la probabilidad de parada de alguna función universal computable sin prefijo) si y solo si es izquierda-ce y algorítmicamente aleatorio. ^{[ 4 ]} Ω está entre los pocos números algorítmicamente aleatorios definibles y es el número algorítmicamente aleatorio mejor conocido, pero no es en absoluto típico de todos los números algorítmicamente aleatorios. ^{[ 5 ]}

Un número real se considera computable si existe un algoritmo que, dado n , devuelve los primeros n dígitos del número. Esto equivale a la existencia de un programa que enumera los dígitos del número real.

No se puede calcular la probabilidad de parada. La prueba de este hecho se basa en un algoritmo que, dados los primeros n dígitos de Ω , resuelve el problema de parada de Turing para programas de longitud hasta n . Dado que el problema de parada es indecidible , Ω no se puede calcular.

El algoritmo procede de la siguiente manera: dados los primeros n dígitos de Ω y un k ≤ n , el algoritmo enumera el dominio de F hasta que se hayan encontrado suficientes elementos del dominio de modo que la probabilidad que representan esté dentro de 2 ^{− ( k + 1)} de Ω . A partir de este punto, no puede haber ningún programa adicional de longitud k en el dominio, porque cada uno de ellos añadiría 2 ^{− k} a la medida, lo cual es imposible. Por lo tanto, el conjunto de cadenas de longitud k en el dominio es exactamente el conjunto de dichas cadenas ya enumeradas.

Un número real es aleatorio si la secuencia binaria que lo representa es una secuencia aleatoria algorítmica . Calude, Hertling, Khoussainov y Wang demostraron ^{[ 6 ]} que un número real recursivamente enumerable es una secuencia aleatoria algorítmica si y solo si es un número Ω de Chaitin .

Para cada sistema axiomático específico, consistente y efectivamente representado para los números naturales , como la aritmética de Peano , existe una constante N tal que ningún bit de Ω posterior al N -ésimo puede demostrarse que sea 1 o 0 dentro de ese sistema. La constante N depende de cómo se representa efectivamente el sistema formal y, por lo tanto, no refleja directamente la complejidad del sistema axiomático. Este resultado de incompletitud es similar al teorema de incompletitud de Gödel, ya que demuestra que ninguna teoría formal consistente para la aritmética puede ser completa.

Los primeros n bits de la constante Ω de Gregory Chaitin son aleatorios o incompresibles en el sentido de que no pueden ser calculados por un algoritmo de parada con menos de n − O(1) bits. Sin embargo, consideremos el algoritmo corto pero nunca detenible que enumera y ejecuta sistemáticamente todos los programas posibles; cuando uno de ellos se detiene, su probabilidad se suma a la salida (inicializada en cero). Después de un tiempo finito, los primeros n bits de la salida nunca cambiarán más (no importa que este tiempo en sí mismo no sea computable por un programa de parada). Por lo tanto, existe un algoritmo corto no detenible cuya salida converge (después de un tiempo finito) a los primeros n bits de Ω . En otras palabras, los primeros n bits enumerables de Ω son altamente compresibles en el sentido de que son computables límite por un algoritmo muy corto; no son aleatorios con respecto al conjunto de algoritmos de enumeración. Jürgen Schmidhuber construyó un "Super Ω " incomputable por límite que, en cierto sentido, es mucho más aleatorio que el Ω original computable por límite , ya que no se puede comprimir significativamente el Super Ω mediante ningún algoritmo enumerativo que no se detenga. ^{[ 7 ]}

Para una "Super Ω " alternativa, la probabilidad de universalidad de una máquina de Turing universal (MTU) sin prefijo —es decir, la probabilidad de que siga siendo universal incluso cuando cada una de sus entradas (como una cadena binaria ) está precedida por una cadena binaria aleatoria— puede verse como la probabilidad de no parada de una máquina con oráculo en la tercera iteración del problema de parada (es decir, O ⁽³⁾ usando la notación de salto de Turing ). ^{[ 8 ]}  

• Teoremas de incompletitud de Gödel
• complejidad de Kolmogorov

• Aspectos del artículo de la encuesta Omega de Chaitin que analiza los avances recientes en el estudio del Ω de Chaitin .
• Omega y por qué las matemáticas no tienen una Teoría de la Evolución (TOE): artículo basado en uno escrito por Gregory Chaitin que apareció en la edición de agosto de 2004 de Mathematics Today , con motivo del 50 aniversario de la muerte de Alan Turing.
• El artículo «Los límites de la razón» , de Gregory Chaitin, se publicó originalmente en Scientific American en marzo de 2006.
• Super Omega computable por límites, más aleatorio que Omega y generalizaciones de la información algorítmica, por Jürgen Schmidhuber