Chaitinovo číslo

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

:: \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 U pro danou posloupnost x na vstupu zastaví; l(x) je délka x . Z Kraftovy nerovnosti plyne, že suma je omezená a tedy dokazatelně konverguje k reálnému číslu, pro nějž platí 0. +more 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 \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 \Omega je rovno limitě pravděpodobnosti, že univerzální Turingův stroj zastaví pro náhodně generovanou posloupnost délky n nul a jedniček na vstupu, je-li tato generována jako iid z alternativního rozdělení s parametrem p=1/2

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

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

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

Kategorie:Teorie informace Kategorie:Teorie algoritmů Kategorie:Matematické konstanty Kategorie:Transcendentní čísla