Khaitin állandó

Az oldal jelenlegi verzióját még nem ellenőrizték tapasztalt közreműködők, és jelentősen eltérhet a 2020. március 7-én felülvizsgált verziótól ; az ellenőrzések 5 szerkesztést igényelnek .

A számítástechnika területén  – az algoritmikus információelmélet – Khaitin állandója vagy leállási valószínűsége  egy valós szám , amely informálisan annak a valószínűsége , hogy egy önkényesen kiválasztott program leáll . Az ilyen számok létezését Gregory Chaitin bizonyította .

Bár végtelen számú leállási valószínűség létezik, általános az Ω betű használata mindegyik ábrázolására, mintha csak egy ilyen szám lenne. Mivel az Ω számértéke a használt programozási nyelvtől függ, ezért ha nem egy adott nyelvre vonatkozik, gyakran Khaitin konstrukciónak nevezik , és nem Khaitin konstansnak .

Minden Ω egy normál transzcendentális szám , amely definiálható, de nem számítható , ami azt jelenti, hogy nincs algoritmus a számjegyeinek megszámlálására.

Háttér

A leállási valószínűség definíciója az univerzális kiszámítható függvények előtagján alapul . Az ilyen függvények vizuálisan egy olyan programozási nyelv, amely azzal a tulajdonsággal rendelkezik, hogy egyetlen megfelelő program sem érhető el egy másik helyes program megfelelő kiterjesztéseként.

Tegyük fel, hogy az F függvény két argumentumtól függ, amelyek mindegyike egy végső bináris karakterlánc, és egy bináris karakterláncot ad vissza kimenetként. Egy F függvényt kiszámíthatónak nevezünk, ha létezik egy Turing-gép , amely kiszámolja.

Egy F függvényt univerzálisnak nevezünk, ha a következő feltételek teljesülnek: egy x változó minden f kiszámítható függvényére létezik egy p konstans , így bármely x esetén F ( p , x ) = f ( x ). Azaz F felhasználható egy változó bármely kiszámítható függvényének modellezésére. Lazán p egy "programot" jelöl egy f kiszámolható függvényhez , F pedig egy emulátort, amely bemenetként vesz egy programot és végrehajtja azt. Meg kell jegyezni, hogy bármely rögzített p esetén az f ( x ) = F ( p , x ) függvény kiszámítható; így az univerzalitási tulajdonság kimondja, hogy egyetlen változó összes kiszámítható függvénye így megkapható.

F tartománya az összes p program halmaza úgy, hogy legalább egy x értékre az F ( p , x ) érték definiálva van. Egy függvényt prefixnek nevezünk, ha a tartománya nem tartalmaz két p , p′ elemet úgy, hogy p′ a p megfelelő kiterjesztése . Az állítás a következőképpen fogalmazható meg: a definíciós tartomány a véges hosszúságú bináris karakterláncok halmazán lévő előtag kódja . Minden univerzális kiszámítható függvény tartománya egy felsorolható halmaz , de soha nem számítható halmaz . Ennek a tartománynak mindig ugyanolyan mértékű a Turing-féle eldönthetetlensége, mint a megállási problémának .

Megállási valószínűségek meghatározása

Legyen P F az F  előtag univerzális kiszámítható függvény tartománya . Az állandót ezután a következőképpen definiáljuk

,

ahol a p karakterlánc hosszát jelöli . Ez az F tartományából származó összes p végtelen összege . Az a követelmény, hogy a tartomány előtagként szerepeljen, a Kraft-egyenlőtlenséggel együtt elegendő ahhoz, hogy ez az összeg egy 0-tól 1- ig tartó valós számhoz konvergáljon . Ha F világos a szövegkörnyezetből, akkor Ω F egyszerűen Ω-ként jelölhető, bár különböző előtagok az univerzális kiszámítható függvények különböző Ω-értékekhez vezetnek.

Ω alkalmazása megoldatlan számelméleti problémák bizonyítására

A Chaitin-állandó elvileg számos kiemelkedő számelméleti probléma megoldására használható , beleértve a Goldbach -problémát és a Riemann-hipotézist . [1] A Goldbach-probléma megfogalmazása szerint minden 2-nél nagyobb páros szám két prímszám összege. Hagyja, hogy egy számítógépes program megkeresse egy adott páros szám megfelelő prímszámait. Ha Goldbach sejtése helyes, a program a következő páros számra lép, és a keresés folytatódik. Ha nincs két prím, amely összeadja a szükséges páros számot, akkor ellenpéldát találunk, a program leáll, és Goldbach sejtését megcáfoljuk. Legyen ennek a programnak a hossza N bit. Ha van korlátlan erőforrás és idő, a Chaitin-állandó a következő módon használható a Goldbach-sejtés bizonyítására. Legyen minden N + 1 bit hosszúságú program  párhuzamosan futva. Ha egy ilyen N bites program leáll, akkor Goldbach sejtése hibásnak bizonyul. Ha viszont elég más program áll le, így egy másik leállított program Chaitin konstansánál nagyobb számot eredményez, akkor ha a program nem áll le, akkor soha nem áll le, és Goldbach sejtése beigazolódik. A módszer alkalmazásához csak a Haitin-állandó első N bitjére van szükségünk.

Ugyanez a Chaitin-állandó használható a Riemann-hipotézis és sok más megoldatlan matematikai probléma bizonyítására .

Az értelmezés mint valószínűség

A Cantor-tér a nullák és egyesek végtelen sorozatának gyűjteménye. A leállási valószínűség a Cantor- tér egy bizonyos részhalmazának mértékeként értelmezhető a Cantor-tér szokásos valószínűségi mértéke alatt . Ebből az értelmezésből származik a leállási valószínűségek neve.

A Cantor-tér valószínűségi mértéke, amelyet néha kiegyensúlyozott érmemértéknek is neveznek, úgy van meghatározva, hogy bármely x bináris karakterlánc esetén az x -szel kezdődő sorozatok 2 -| x | . Ez az állítás azt jelenti, hogy bármely n természetes szám esetén a Cantor-térben lévő f sorozatok halmazának, ahol f ( n ) = 1-nek van mértéke 1/2, és azoknak a sorozatoknak a halmazának, amelyek n- edik tagja 0, szintén 1/2-e van.

Legyen F  előtag univerzális kiszámítható függvény. P tartománya bináris karakterláncok végtelen halmazából áll

A p i sorok mindegyike meghatározza a Cantor-tér egy S i részhalmazát ; az S i halmaz tartalmazza a Cantor-tér összes p i -vel kezdődő sorozatát . Ezek a halmazok nem metszik egymást, mivel P  egy előtaghalmaz. Összeg

a halmaz mértékét jelenti

.

Így Ω F azt a valószínűséget jelenti, hogy egy véletlenszerűen kiválasztott 0-ból és 1-ből álló végtelen sorozat egy (valamilyen véges hosszúságú) bitsorral kezdődik, amely F tartományába tartozik . Emiatt Ω F -et leállási valószínűségnek nevezzük.

Tulajdonságok

Minden Ω Haitin állandó a következő tulajdonságokkal rendelkezik:

Nem minden halmaz, amelynek Turing-féle eldönthetetlensége ugyanolyan fokú, mint a megállítási probléma , megállási valószínűség. Egy jobb ekvivalencia reláció, a Solovay ekvivalencia használható a bal ce valós számok megállási valószínűségének jellemzésére.[ tiszta ]

A leállítási valószínűségek kiszámíthatatlansága

Egy valós számot kiszámíthatónak mondunk, ha van olyan algoritmus, amely n adott esetben a szám első n számjegyét adja vissza. Az állítás egyenértékű egy olyan program létezésével, amely egy valós szám számjegyeit számba veszi.

A leállás valószínűsége nem számítható ki. Ennek a ténynek a bizonyítása egy olyan algoritmuson alapul, amely az első n szám ismeretében megoldja a legfeljebb n bites programok leállításának problémáját . Mivel a leállítási probléma eldönthetetlen, Ω nem számítható ki.

Az algoritmus a következőképpen működik. Ha az első n szám Ω és k ≤ n adott , akkor az algoritmus addig számba veszi az F tartományt , amíg elegendő számú talált tartományelem 2- (k+1) Ω-ban rejlő valószínűséget nem jelent. Ezt követően a vizsgált területen nem lehet k hosszúságú program . Így a k hosszúságú karakterláncok halmaza pontosan a már felsorolt ​​ilyen karakterláncok halmaza.

A befejezetlenségi tétel a valószínűségek megállítására

Minden konzisztens, kellően gazdag természetes számrendszerhez , például Peano -axiómákhoz , létezik olyan N konstans, amely lehetővé teszi annak bizonyítását, hogy az N- edik utáni Ω bármely bitje nulla vagy egy ebben az axiómarendszerben. A konstans attól függ, hogy az adott formális rendszer mennyire gazdag, így nem tükrözi közvetlenül az axiómarendszer összetettségét. A kapott eredmény hasonló Gödel befejezetlenségi tételéhez , mivel egyetlen formális aritmetikai elmélet sem lehet teljes.

Ω Khaitin eredetének kiszámítása

Calude, Dinneen és Shu kiszámolta a Haitin-féle Ω U első 64 bitjét egy adott géphez. Itt vannak, bináris jelöléssel :

0,0000001000000100000110001000011010001111110010111011101000010000…

és decimális jelöléssel :

0,0078749969978123844…

Meg kell jegyezni, hogy egy bizonyos (de nem bármelyik) Ω számjegy helyes kiszámításának képessége eltér a kiszámíthatóság fogalmától: bármely szám bármely számjegye kiszámítható, mivel bármely egész számra van egy program, amely kiírja azt.

Super Omega

Mint fentebb említettük, Khaitin Ω konstansának első n bitje véletlenszerű vagy összenyomhatatlan abban az értelemben, hogy nem tudjuk kiszámítani őket n  − O(1) bitnél rövidebb algoritmussal . Vegyünk azonban egy rövid, de soha meg nem álló algoritmust, amely módszeresen felsorolja és végrehajtja az összes lehetséges programot; amint az egyik leáll, a valószínűsége hozzáadódik az eredményhez (kezdetben nullával egyenlő). A befejezési idő után az eredmény első n bitje már nem változik (nem számít, hogy maga az idő nem számítható). Tehát van egy rövid, nem leállító algoritmus, amelynek eredménye (véges idő alatt) bármely n esetén Ω első n bitjéhez konvergál . Más szóval, Ω első n bitjének felsorolása erősen tömöríthető abban az értelemben, hogy egy nagyon rövid algoritmussal kiszámíthatók; a felsoroló algoritmusok halmazát tekintve nem véletlenszerűek . Jürgen Schmidhuber 2000-ben megszerkesztett egy korlátos, kiszámítható "Super-Omegát", amely bizonyos értelemben sokkal véletlenszerűbb, mint az eredeti korlátos-számítható Ω, mivel a Super-Omegát nem lehet jelentősen tömöríteni semmilyen felsoroló, nem leállító algoritmussal.

Lásd még

Jegyzetek

  1. ↑ Thomas M. Cover és Joy A. Thomas, Elements of Information Theory, 2. kiadás, Wiley-Interscience, 2006.

Források

Linkek