Constant de Chaitin

En complexitat computacional, la constant de Chaitin o nombre Omega de Chaitin o probabilitat de parada és, de forma informal, la probabilitat de que un programa escrit al atzar aturi correctament una màquina de Turing determinista. En ser una probabilitat, ha de ser un nombre real entre 0 i 1. Aquest nombre va ser definit per Gregory Chatitin^[1][2][3]

Definició

La definició d'una probabilitat d'aturada recau en l'existència d'una funció computable universal sense prefix. Aquesta funció, intuïtivament, representa un llenguatge de programació amb la propietat de que cap programa vàlid es pot obtenir a partir d'estendre un altre programa vàlid.

Suposem que F és una funció parcial que pren un argument, una cadena finita de bits, i retorna una cadena binària com a sortida. Aquesta funció F es diu computable si hi ha una màquina de Turing que la computa, en el sentit que per cada cadena finita d'entrada x tal que F(x) = y la màquina de Turing s'atura i la seva sortida és y per l'entrada x.

Aquesta funció F s'anomena universal si compleix les següents propietats: per cada funció computable f d'una sola variable existeix una cadena w tal que per tot x es te que F(w x) = f(x), aquí w x representa la concatenació de les cadenes w i x. Això vol dir que F es pot fer servir per simular qualsevol funció computable d'una variable. Informalment, w representa el guió de la funció computable f i F representa l'intèrpret que interpreta el guió com un prefix de la seva entrada i llavors l'executa amb la resta de l'entrada.

El domini d'F és el conjunt de totes les entrades p on està definida. Per F que és universal, aquest p generalment es pot veure com la concatenació de la part de codi i de dades i com un sol programa per la funció F.

La funció F s'anomena lliure de prefix si no hi ha dos elements p,p' al seu domini tal que p' sigui una extensió de p.

Sigui P_F el conjunt de tots els programes que s'aturen, i |p| la mida en bits d'un programa p, Ω_F està definida de la següent manera:

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

És una suma infinita amb un sumand per cada p del domini d'F. El requeriment de que el domini sigui lliure de prefix, juntament amb la desigualtat de Kraft assegura que la suma és convergent cap un nombre real entre 0 i 1.

Propietats

Tota constant de Chaitin Ω te les següents propietats:^[4]

• És algorítmicament aleatòria. Això vol dir que el programa més curt que genera els primers n bits d'Ω ha de ser de la mida d'almenys n-O(1).
• És un nombre normal.
• No és un nombre computable, no hi ha una funció computable que enumeri la seva expansió binària.
• El conjunt de nombres racionals q tal que q < Ω és recursivament enumerable.
• El conjunt de nombres racionals q tal que q > Ω no és computacionalment enumerable.
• Ω és un nombre aritmètic.
• És equivalent de Turing al problema de la parada i el seu nivell dins la jerarquia aritmètica és ${\displaystyle \Delta _{2}^{0}}$.

Vegeu també

• Teorema d'incompletesa de Gödel
• Complexitat computacional

Referències

1. W., Weisstein, Eric. «Chaitin's Constant» (en anglès). [Consulta: 28 novembre 2018].
2. S. Calude, Cristian; H. Hertling, Peter; Khoussainov, Bakhadyr; Wang, Yongge «Recursively enumerable reals and Chaitin Ω numbers». Theoretical Computer Science, 255, 1-2, 3-2001, pàg. 125–149. DOI: 10.1016/s0304-3975(99)00159-0. ISSN: 0304-3975.
3. Chaitin, Gregory J. «A Theory of Program Size Formally Identical to Information Theory». Journal of the ACM (JACM), 22, 3, 01-07-1975, pàg. 329–340. DOI: 10.1145/321892.321894. ISSN: 0004-5411.
4. Barmpalias, George «Aspects of Chaitin's Omega». arXiv:1707.08109 [cs, math], 25-07-2017.