Chaitinovo číslo: Porovnání verzí
mBez shrnutí editace |
mBez shrnutí editace značka: editace z Vizuálního editoru |
||
Řádek 6: | Řádek 6: | ||
Z [[Kraftova nerovnost| Kraftovy nerovnosti]] plyne, že suma je omezená a tedy dokazatelně konverguje k reálnému číslu, pro nějž platí <math> 0< \Omega <1 </math>. Toto reálné číslo však nelze žádným [[Algoritmus | algoritmem]] spočítat s přesností vyšší než striktně daný počet [[ Dvojková soustava| binárních]] míst; speciálně pak neexistuje algoritmus schopný hodnotu Chaitinova čísla libovolně aproximovat. Znalost hodnoty <math> \Omega </math> 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ý. |
Z [[Kraftova nerovnost| Kraftovy nerovnosti]] plyne, že suma je omezená a tedy dokazatelně konverguje k reálnému číslu, pro nějž platí <math> 0< \Omega <1 </math>. Toto reálné číslo však nelze žádným [[Algoritmus | algoritmem]] spočítat s přesností vyšší než striktně daný počet [[ Dvojková soustava| binárních]] míst; speciálně pak neexistuje algoritmus schopný hodnotu Chaitinova čísla libovolně aproximovat. Znalost hodnoty <math> \Omega </math> 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. |
Chaitinovo číslo je tedy reálné číslo, pro nějž je [[Matematický důkaz|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== |
==Vlastnosti== |
Verze z 29. 5. 2019, 11:04
Chaitinovo číslo, Ω, někdy také Chaitinova konstanta, je matematická konstanta definovaná
Součet je veden přes všechny konečné posloupnosti 0 a 1 takové, že univerzální Turingův stroj pro danou posloupnost na vstupu zastaví; je délka . Z Kraftovy nerovnosti plyne, že suma je omezená a tedy dokazatelně konverguje k reálnému číslu, pro nějž platí . 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 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 je rovno limitě pravděpodobnosti, že univerzální Turingův stroj zastaví pro náhodně generovanou posloupnost délky nul a jedniček na vstupu, je-li tato generována jako iid z alternativního rozdělení s parametrem
- Ve dvojkovém zápisu prvních znaků hodnoty se poměr 0 a 1 blíží . Odpovídající vlastnost platí rovněž pro zápis v soustavě s libovolným základem.
- Obecněji jakákoli předem dané binární slovo se ve dvojkovém zápise vyskytuje s četností odpovídající jeho pravděpodobnosti při iid generování z alternativního rozdělení s parametrem . Vlastnost rovněž zůstává zachována také pro zápis v soustavě s libovolným základem ; pravděpodobnost je nutno přepočítat pro diskrétní rovnoměrné rozdělení s parametrem
- Chaitinovo číslo je transcendentní reálné číslo a je tedy i iracionální.