Khaitinova konstanta

Aktuální verze stránky ještě nebyla zkontrolována zkušenými přispěvateli a může se výrazně lišit od verze recenzované 7. března 2020; kontroly vyžadují 5 úprav .

V oblasti informatiky  — algoritmické informační teorie — je Khaitinova konstanta neboli pravděpodobnost zastavení reálné číslo , které, neformálně řečeno, je  pravděpodobnost , že se libovolně zvolený program zastaví . Existenci takových čísel demonstroval Gregory Chaitin .

I když existuje nekonečný počet pravděpodobností zastavení, je běžné používat písmeno Ω k reprezentaci všech, jako by takové číslo bylo jen jedno. Vzhledem k tomu, že číselná hodnota Ω závisí na použitém programovacím jazyce, pak pokud se nejedná o žádný konkrétní jazyk, často se nazývá Khaitinská konstrukce , a ne Khaitin konstanta .

Každé Ω je normální transcendentální číslo , které je definovatelné, ale nevypočitatelné , což znamená, že neexistuje žádný algoritmus pro výčet jeho číslic.

Pozadí

Definice pravděpodobnosti zastavení je založena na existenci předponových univerzálních vyčíslitelných funkcí . Takové funkce jsou vizuálně řečeno programovacím jazykem s tou vlastností, že žádný správný program nelze získat jako odpovídající rozšíření jiného správného programu.

Předpokládejme, že funkce F závisí na dvou argumentech, z nichž každý je konečným binárním řetězcem, a vrací jeden binární řetězec jako výstup. Funkce F se nazývá vyčíslitelná , pokud existuje Turingův stroj , který ji vypočítá.

Funkce F se nazývá univerzální , platí-li následující podmínky: pro každou vyčíslitelnou funkci f jedné proměnné x existuje konstanta p , taková, že pro libovolné x F ( p , x ) = f ( x ). To znamená, že F lze použít k modelování jakékoli vyčíslitelné funkce jedné proměnné. Volně, p představuje "program" pro vyčíslitelnou funkci f a F představuje emulátor, který přijímá program jako vstup a provádí jej. Je třeba poznamenat, že pro jakékoli pevné p je funkce f ( x ) = F ( p , x ) vyčíslitelná; vlastnost univerzálnosti tedy říká, že tímto způsobem lze získat všechny vyčíslitelné funkce jedné proměnné.

Oblast F je množina všech programů p tak, že alespoň pro jednu hodnotu x je definována hodnota F ( p , x ). Funkce se nazývá prefix, pokud její definiční obor neobsahuje dva prvky p , p′ tak, že p′ je odpovídající rozšíření p . Příkaz lze přeformulovat následovně: doménou definice je kód předpony na množině binárních řetězců konečné délky. Oblastí jakékoli univerzální vyčíslitelné funkce je vyčíslitelná množina , ale nikdy nevyčíslitelná množina . Tato doména má vždy stejný stupeň Turingovy nerozhodnutelnosti jako problém zastavení .

Stanovení pravděpodobností zastavení

Nechť P F  je definičním oborem předponové univerzální vyčíslitelné funkce F . Konstanta je pak definována jako

,

kde označuje délku řetězce p . Toto je nekonečný součet přes všechna p z definičního oboru F . Požadavek na předponu definičního oboru spolu s Kraftovou nerovností postačuje k tomu, aby tento součet konvergoval k reálnému číslu od 0 do 1. Pokud je F z kontextu jasné, pak Ω F můžeme označit jednoduše jako Ω, i když různé předpony univerzální vyčíslitelné funkce vedou k různým hodnotám Ω.

Aplikace Ω k důkazu nevyřešených problémů v teorii čísel

Chaitinova konstanta může v zásadě být použita k vyřešení mnoha význačných problémů v teorii čísel , včetně Goldbachova problému a Riemannovy hypotézy . [1] Formulace Goldbachova problému říká, že každé sudé číslo větší než 2 je součtem dvou prvočísel. Nechte počítačový program vyhledat odpovídající prvočísla pro dané sudé číslo. Pokud je Goldbachova domněnka správná, program přejde na další sudé číslo a hledání pokračuje. Pokud neexistují žádná dvě prvočísla, která by odpovídala požadovanému sudému číslu, pak bude nalezen protipříklad, program se zastaví a Goldbachova domněnka bude vyvrácena. Nechť délka tohoto programu je N bitů. Vzhledem k neomezeným zdrojům a času lze Chaitinovu konstantu použít k prokázání Goldbachovy domněnky následujícím způsobem. Všechny programy o délce N  + 1 bitů nebo méně nechť běží paralelně. Pokud se takový N - bitový program zastaví, Goldbachova domněnka se ukáže jako mylná. Pokud se naopak zastaví dostatek jiných programů, takže dalším zastaveným programem bude číslo větší, než je Chaitinova konstanta, pak pokud se program nezastaví, pak se nikdy nezastaví a Goldbachova domněnka se prokáže. K aplikaci této metody potřebujeme pouze prvních N bitů Haitinovy ​​konstanty.

Stejná Chaitin konstanta může být použita k prokázání Riemannovy hypotézy a mnoha dalších nevyřešených problémů v matematice .

Interpretace jako pravděpodobnosti

Cantorův prostor je souborem všech nekonečných posloupností nul a jedniček. Pravděpodobnost zastavení může být interpretována jako míra určité podmnožiny Cantorova prostoru pod obvyklou pravděpodobnostní mírou na Cantorově prostoru. Právě z tohoto výkladu vzešel název pravděpodobností zastavení.

Pravděpodobnostní míra na Cantorově prostoru, někdy nazývaná vyvážená míra mince, je definována tak, že pro jakýkoli binární řetězec x má množina sekvencí začínajících x míru 2 -| x | . Toto tvrzení implikuje, že pro libovolné přirozené číslo n má množina posloupností f v Cantorově prostoru takovou, že f ( n ) = 1 míru 1/2, a množina posloupností, jejichž n-tý člen je 0, má také míru 1/2.

Nechť F  je předpona univerzální vyčíslitelné funkce. Jeho doména P se skládá z nekonečné množiny binárních řetězců

Každá z těchto čar p i definuje podmnožinu Si Cantorova prostoru; množina S i obsahuje všechny posloupnosti v Cantorově prostoru, které začínají p i . Tyto množiny se neprotínají, protože P  je množina prefixů. Součet

představuje míru množiny

.

Ω F tedy představuje pravděpodobnost, že náhodně vybraná nekonečná sekvence 0s a 1s začíná bitovým řetězcem (nějaké konečné délky), který patří do domény F . Z tohoto důvodu se Ω F nazývá pravděpodobnost zastavení.

Vlastnosti

Každá haitinská konstanta Ω má následující vlastnosti:

Ne každá množina, která má stejný stupeň Turingovy nerozhodnutelnosti jako problém zastavení, je pravděpodobnost zastavení. Lepší vztah ekvivalence, Solovayova ekvivalence , lze použít k charakterizaci pravděpodobností zastavení mezi reálnými čísly vlevo.[ vyčistit ]

Nevyčíslitelnost pravděpodobností zastavení

O reálném čísle se říká, že je vypočitatelné, pokud existuje algoritmus, který při daném n vrací prvních n číslic čísla. Příkaz je ekvivalentní existenci programu, který vypočítává číslice reálného čísla.

Žádná pravděpodobnost zastavení není vyčíslitelná. Důkaz této skutečnosti je založen na algoritmu, který při daných prvních n číslech řeší problém zastavování programů o délce až n bitů. Protože problém zastavení je nerozhodnutelný, Ω nelze vypočítat.

Algoritmus funguje následovně. Pokud je dáno prvních n čísel Ω ak ≤ n , pak algoritmus vyčísluje doménu F tak dlouho, dokud dostatečný počet nalezených doménových prvků nepředstavuje pravděpodobnost ležící v 2 -(k+1) Ω. Poté již v uvažované oblasti nemůže být žádný program délky k . Množina řetězců délky k je tedy přesně tou množinou již uvedených řetězců.

Věta o neúplnosti pro pravděpodobnosti zastavení

Pro každý souhlasný dostatečně bohatý axiómový systém přirozených čísel , takový jako Peanoovy axiómy , tam existuje konstanta N takový to dokazovat zda nějaký kousek? po Nth je nula nebo jeden je nemožný v tomto systému axiómů. Konstanta závisí na tom, jak bohatý je daný formální systém, a tedy přímo neodráží složitost systému axiomů. Získaný výsledek je podobný Gödelově větě o neúplnosti v tom, že žádná formální teorie aritmetiky nemůže být úplná.

Výpočet původu Ω Khaitin

Calude, Dinneen a Shu vypočítali prvních 64 bitů Haitinova Ω U pro konkrétní stroj. Zde jsou v binárním zápisu :

0,000000100000010000110001000011010001111110010111011101000010000…

a v desítkovém zápisu :

0,0078749969978123844…

Je třeba poznamenat, že schopnost správně vypočítat určitou (nikoli však jakoukoli) číslici Ω se liší od konceptu vyčíslitelnosti: jakákoli určitá číslice jakéhokoli čísla je vypočitatelná díky skutečnosti, že pro jakékoli celé číslo existuje program, který ji vypíše.

Super Omega

Jak bylo uvedeno výše, prvních n bitů Khaitinovy ​​konstanty Ω je náhodných nebo nestlačitelných v tom smyslu, že je nemůžeme spočítat pomocí algoritmu kratšího než n  − O(1) bitů. Zvažte však krátký, ale nikdy nezastavující algoritmus, který metodicky vyjmenovává a provádí všechny možné programy; jakmile se jeden z nich zastaví, jeho pravděpodobnost se přičte k výsledku (zpočátku rovna nule). Po čase ukončení se již prvních n bitů výsledku nezmění (nezáleží na tom, že samotný čas není vyčíslitelný). Existuje tedy krátký nezastavující algoritmus, jehož výsledek konverguje (v konečném čase) k prvním n bitům Ω pro libovolné n . Jinými slovy, výčet prvních n bitů Ω je vysoce komprimovatelný v tom smyslu, že jsou vypočitatelné pomocí velmi krátkého algoritmu; nejsou náhodné s ohledem na sadu výčtových algoritmů. Jürgen Schmidhuber v roce 2000 zkonstruoval omezenou vyčíslitelnou "Super-Omegu", která je v určitém smyslu mnohem náhodnější než původní omezeně vyčíslitelná Ω, protože Super-Omega nemůže být významně komprimována žádným výčtovým nezastavujícím algoritmem.

Viz také

Poznámky

  1. ↑ Thomas M. Cover a Joy A. Thomas, Elements of Information Theory, 2. vydání, Wiley-Interscience, 2006.

Zdroje

Odkazy