Chaitinovo číslo

Chaitinovo číslo, Ω, někdy také Chaitinova konstanta, je matematická konstanta definovaná

${\displaystyle \Omega =\sum _{x\in \{0,1\}^{*}:U(x)\rightarrow STOP}2^{-l(x)}}$

Součet je veden přes všechny konečné posloupnosti 0 a 1 takové, že univerzální Turingův stroj ${\displaystyle U}$ pro danou posloupnost ${\displaystyle x}$ na vstupu zastaví; ${\displaystyle l(x)}$ je délka ${\displaystyle x}$. Z Kraftovy nerovnosti plyne, že suma je omezená a tedy dokazatelně konverguje k reálnému číslu, pro nějž platí ${\displaystyle 0<\Omega <1}$. Toto reálné číslo však nelze žádným algoritmem spočítat s přesností vyšší než striktně daný počet binárních míst; speciálně pak neexistuje algoritmus schopný hodnotu Chaitinova čísla libovolně aproximovat. Znalost hodnoty ${\displaystyle \Omega }$ s dostatečnou přesností by totiž řešila problém zastavení, o němž Alan Turing dokázal, že je algoritmicky neřešitelný.

Chaitinovo číslo je tedy reálné číslo, pro nějž je matematicky dokazatelné, že jej nebudeme umět nikdy spočítat ani se k jeho hodnotě přiblížit nad určitou mez přesnosti.

Vlastnosti

• Chaitinovo číslo ${\displaystyle \Omega }$ je rovno limitě pravděpodobnosti, že univerzální Turingův stroj zastaví pro náhodně generovanou posloupnost délky ${\displaystyle n}$ nul a jedniček na vstupu, je-li tato generována jako iid z alternativního rozdělení s parametrem ${\displaystyle p=1/2}$

• Ve dvojkovém zápisu prvních ${\displaystyle n}$ znaků hodnoty ${\displaystyle \Omega }$ se poměr 0 a 1 blíží ${\displaystyle 1/2}$. Odpovídající vlastnost platí rovněž pro zápis ${\displaystyle \Omega }$ v soustavě s libovolným základem.

• Obecněji jakákoli předem dané binární slovo se ve dvojkovém zápise ${\displaystyle \Omega }$ vyskytuje s četností odpovídající jeho pravděpodobnosti při iid generování z alternativního rozdělení s parametrem ${\displaystyle p=1/2}$. Vlastnost rovněž zůstává zachována také pro zápis ${\displaystyle \Omega }$ v soustavě s libovolným základem ${\displaystyle d}$; pravděpodobnost je nutno přepočítat pro diskrétní rovnoměrné rozdělení s parametrem ${\displaystyle d}$

• Chaitinovo číslo je transcendentní reálné číslo a je tedy i iracionální.