Ha egy statisztikust megkérnénk, hogy empirikus úton számolja ki a Chaitin-konstans értékét amilyen pontosan csak tudja, akkor milyen értéket kapnánk és ez hol fordul elő?

Nevezik Chaitin-Ω-nak, Ω-nak, Chaitin-konstansnak, mondják meglállási valószínűségnek is, mintha csak egy konstans lenne, pedig valójában függvény képelemei. Nem egy Chaitin-Ω omega van, hanem végtelen sok.

Bizonyított, hogy az értékük nem számítható ki.

Az algoritmikus információelmélet számítástechnika részterületén a Chaitin-konstans vagy leállási valószínűség egy valós szám, amely kvázi azt a valószínűséget jelenti, hogy egy véletlenszerűen megszerkesztett program leáll.

Igen lehetetlen helyzetbe lenne az a statisztikus aki csak empirikus úton számolhat, bár ha nem csak empirikus úton akkor is, de mégis jobban meghatározhatná az utóbbi esetben.

Hol fordul elő?

Az algoritmikus információelmélet számítástechnika részterületén, közvetve pedig gyakorlatban programozás során.

Az hogy milyen értéket kapnánk?

0-1 közötti értékú minden Chaitin Ω. Egy adott konstrukcióhoz egy adott Chaitin Ω tartozik.

A Chaitin Ω első N bitjének ismeretében kiszámítható a leállítási probléma minden N méretig terjedő programra . Legyen N méretű az a p program , amelyre a leállítási feladatot meg kell oldani . A program lefut mindaddig, amíg meg nem áll addig amíg elegendő valószínűséggel járul hozzá az első N bithez . Ha a p program ekkor még nem állt meg, akkor soha nem is fog, mivel a leállási valószínűséghez való hozzájárulása az első N bitet érintené. Mivel a leállási probléma általában nem oldható meg ezért a Chaitin konstans első néhány bitjét kivéve nem számítható.

Minden leállási valószínűség normális, transzcendens és valós szám. Minden leállási valószínűség Martin-Löf véletlenszerű , vagyis nincs olyan algoritmus, amely megbízhatóan kitalálná a számjegyeit (kiévéve esetleg az első néhány számjegyét). Minden kiszámítható függvény eleme a kiszámíthatóan felsorolható függvények halmazának, ami viszont nem számítható halmaz. Ezen halmaz elemei kiszámításának nehézsége egyenértékű a leállási problémával.

A leállási valószínűség kiszámítási nehézségének demonstrálására az elméleti informatikában van egy játék. A játék neve busy beaver magyarul elfoglalt hód. A játék célja, egy adott méretű befejező program megtalálása, ami a lehető legtöbb kimenetet produkálja. Mivel könnyen lehet végtelen ciklust csinálni, így örökké futó programot írni, ezért ezen programok ki vannak zárva a versenyből. A részletekbe nem belemenve megemlítem, hogy mindössze csak 5 állapotú

gép esetében már nem ismert melyik program a hódbajnok. jelöljük Σ(n)-el az n állapotú gép hódbajnok amennyi kimenetet produkált. Ekkor ez a Σ(n) függvény létező függvény, de matemaitai értelemben is kiszámíthatatlan és aszimptotikusan gyorsabban nő bármely kiszámítható függvénynél.

Például 4 állapotú 3 szimbolumú esetre bizonyított hogy több mint 14 ezer jegyű szám a bajnok (persze nem ismert melyik a bajnok). Ezt empirikus úton nem fogja senki bizonyítani, nem lenne elég hozzá a világ összes ideje a világ összes anyaga (legalábbis a belátható univerzumon belül). Ennek ellenére ezt matematikai úton bizonyították.

A Chaitin-konstans egy olyan szám, amely matematikailag nem kiszámítható, vagyis nincs algoritmusa annak meghatározására. Ez azt jelenti, hogy egy statisztikus sem képes lenne meghatározni az értékét empirikus úton.

A Chaitin-konstans definíciója szerint az értéke véletlenszerűen és egyenletesen oszlik el az [0,1] intervallumon. Azonban a konstans értékét csak bizonyos módon lehet megközelíteni, például véletlenszerű számok generálásával. Ez azt jelenti, hogy véletlenszerűen generált számokkal közelíthetjük meg a Chaitin-konstans értékét, de sosem érhetjük el az érték pontos meghatározását.

Ez a korlát a konstans definíciójából ered, és matematikailag bizonyították, hogy a Chaitin-konstans értéke nem számítható ki véges idő alatt. Tehát a Chaitin-konstans értéke nem áll rendelkezésre empirikus számításokhoz, és nem lehet pontosan meghatározni.

@14:47

Nem egy számot jelent mint ahogy fentebb írtam, egy adott konstrukcióhoz egy adott Chaitin konstans tartozik.

"A Chaitin-konstans definíciója szerint az értéke véletlenszerűen és egyenletesen oszlik el az [0,1] intervallumon."

Konstasként magyarázod, eloszlása függvénynek van, nem konstansnak. Egyébként én olyat nem olvastam hogy egyenletesen oszlana el, de ha az én hiányosságom lenne, akkor erre forrást kérek!

"Azonban a konstans értékét csak bizonyos módon lehet megközelíteni, például véletlenszerű számok generálásával. Ez azt jelenti, hogy véletlenszerűen generált számokkal közelíthetjük meg a Chaitin-konstans értékét, de sosem érhetjük el az érték pontos meghatározását."

Annál azért jóval bonyolultabb. Egyrészt nem véletlenszerű, mármint nem pszeudorandom, hanem true random kell. Csupán véletlen számok generálásával nem tudod közelíteni sem. Ha már így próbálod akkor véletlenszám generálást felhasználva konkrét véletlen programok generálása kell, olyanok melyekben ciklusok vannak kigenerálva és ezeket futtatni kell. Irtó bonyolult különben, megoldhatatlanul nehéz. Lehet segíteni statikus kódellemzéssel stb. Bizonyos esetekre megmondható, ha végtelen ciklus, persze az sem empirikusan. Már ha empirikus alatt azt értem, hogy fekete dobozként kezelem a programot, nem nézhetek bele mit csinál, csak azt látom hogy milyen kimenetet ad és hogy megállt e.