Constant de Chaitin

La constant de Chaitin (o número omega de Chaitin o provabilitat de parada) és la provabilitat de que un programa elegit al encert detinga correctament una màquina de Turing determinada. En ser una provabilitat ha de ser un número entre 0 i 1.

Siga P el conjunt de tots els programes que es detenen, i |p| el tamany en bits d'un programa p, Ω està definida de la següent manera:

Història

Gregory Chaitin, en els anys 1960 i casi al mateix temps que Andréi Kolmogórov, va establir la següent definició d'objecte algorítmicamente aleatori: aquell impossible de ser generat per un programa més curt que sí mateix. També va demostrar que tot número algorítmicamente aleatori era normal (siga com siga la base elegida, tots els dígits apareixen en igual freqüència, com si hagueren segut generats per mig de successius llançaments d'un dau).

Recordem que una màquina de Turing és un ordenador simple, pero que en ella es poden computar totes les tasques computables.

Propietats

• Esta constant no és computable. És possible conéixer o obtindre els primers dígits, pero a partir de cert decimal (que depén de la codificació elegida) no és possible conéixer o obtindre més.
• És un número real b-normal i algorítmicamente incompresible, o en una terminologia equivalent és un número i algorítmicamente aleatori. Açò és dir prou més de lo que sembla a simple vista. Supon que no pot comprimir-se en un programa més breu que ell mateixa. Un número irracional com π o i, a pesar de tindre infinits decimals no periòdics, pot ser generat correctament fins al decimal enèsim per un programa de molt poques llínees que, eixecutat en un ordenador, vaja escrivint els successius decimals. Per lo tant és comprimible, i no és algorítmicamente aleatori.

No solament no es pot calcular este número, sino que mai es poden saber quins són els seus bits, perque eixa informació, com va dir Chaitin, "és matemàticament incompresible i incomprensible, les paraules són molt semblants. Per a obtindre els n primers bits de Ω es necessita una teoria de n bits, de complexitat igual al fenomen que es vol estudiar. Això significa que no es guanya res raonant".

Existixen programes molt curts que generen $\pi$ en els seus infinits decimals, després la complexitat intrínseca (inherent i pròpia de l'element) de π és menuda; no és algorítmicamente aleatori. El conjunt de Mandelbrot, en els seus recovecos infinits i volutes bellíssimes és generable també per programes molt curts, per lo tant posseïx molt poca complexitat en el sentit de Kolmogórov.

El nostre Ω no té estructura: és pur encert a pesar d'estar perfectament definit.

Kolmogórov ha ideat el concepte de complexitat (cantitat d'informació) d'un objecte com el número de bits del programa més conciso capaç de generar-ho.

Vore també

• [[Archiu:{{#switch:Matemàtica|20px|Vore el portal sobre Matemàtica]] Portal:Matemàtica. Contingut relacionat en Matemàtica.
• Teoria de la computabilidad
• Complexitat computacional
• Màquina de Turing