Constanta lui Khaitin

Versiunea actuală a paginii nu a fost încă examinată de colaboratori experimentați și poate diferi semnificativ de versiunea revizuită pe 7 martie 2020; verificările necesită 5 modificări .

În domeniul informaticii  — teoria algoritmică a informației — constanta lui Khaitin , sau probabilitatea de oprire,  este un număr real care, vorbind informal, este probabilitatea ca un program ales în mod arbitrar să se oprească . Existența unor astfel de numere a fost demonstrată de Gregory Chaitin .

Deși există un număr infinit de probabilități de oprire, este obișnuit să se folosească litera Ω pentru a le reprezenta pe toate, ca și cum ar fi un singur astfel de număr. Deoarece valoarea numerică a lui Ω depinde de limbajul de programare folosit, atunci dacă nu se referă la un limbaj specific, este adesea numită construcția Khaitin și nu constanta Khaitin .

Fiecare Ω este un număr transcendental normal , care este definibil, dar nu poate fi calculat , ceea ce înseamnă că nu există un algoritm pentru a-i enumera cifrele.

Fundal

Definiția probabilității de oprire se bazează pe existența funcțiilor calculabile universale de prefix . Astfel de funcții sunt, vizual vorbind, un limbaj de programare cu proprietatea că niciun program corect nu poate fi obținut ca extensie corespunzătoare a altui program corect.

Să presupunem că funcția F depinde de două argumente, fiecare dintre acestea fiind un șir binar final și returnează un șir binar ca ieșire. O funcție F se numește calculabilă dacă există o mașină Turing care o calculează.

O funcție F se numește universală dacă sunt îndeplinite următoarele condiții: pentru fiecare funcție calculabilă f a unei variabile x , există o constantă p , astfel încât pentru orice x F ( p , x ) = f ( x ). Adică, F poate fi folosit pentru a modela orice funcție calculabilă a unei variabile. În mod liber, p reprezintă un „program” pentru o funcție calculabilă f , iar F reprezintă un emulator care ia un program ca intrare și îl execută. De remarcat că pentru orice p fix , funcția f ( x ) = F ( p , x ) este calculabilă; astfel, proprietatea de universalitate afirmă că toate funcțiile calculabile ale unei singure variabile pot fi obținute în acest fel.

Domeniul lui F este mulțimea tuturor programelor p astfel încât pentru cel puțin o valoare x este definită valoarea F ( p , x ). O funcție se numește prefix dacă domeniul ei nu conține două elemente p , p′ astfel încât p′ este extensia corespunzătoare a lui p . Enunțul poate fi reformulat astfel: domeniul definiției este codul prefixului de pe mulțimea de șiruri binare de lungime finită. Domeniul oricărei funcții calculabile universale este o mulțime enumerabilă , dar niciodată o mulțime calculabilă . Acest domeniu are întotdeauna același grad de indecidibilitate Turing ca problema opririi .

Determinarea probabilităților de oprire

Fie P F  domeniul prefixului funcției calculabile universale F . Constanta este apoi definită ca

,

unde denotă lungimea șirului p . Aceasta este o sumă infinită peste tot p din domeniul lui F . Cerința ca domeniul să fie prefixat, împreună cu inegalitatea lui Kraft , sunt suficiente pentru ca această sumă să convergă către un număr real de la 0 la 1. Dacă F este clar din context, atunci Ω F poate fi notat simplu ca Ω, deși diferite prefixe funcțiile calculabile universale conduc la valori diferite ale lui Ω.

Aplicarea lui Ω la demonstrarea problemelor nerezolvate în teoria numerelor

Constanta lui Chaitin poate fi utilizată, în principiu, pentru a rezolva multe probleme restante din teoria numerelor , inclusiv problema lui Goldbach și ipoteza Riemann . [1] Formularea problemei lui Goldbach afirmă că orice număr par mai mare decât 2 este suma a două numere prime. Lăsați un program de calculator să caute numerele prime corespunzătoare pentru un anumit număr par. Dacă conjectura lui Goldbach este corectă, programul trece la următorul număr par și căutarea continuă. Dacă nu există două numere prime care se adună la numărul par necesar, atunci va fi găsit un contraexemplu, programul se va opri și conjectura lui Goldbach va fi respinsă. Fie lungimea acestui program de N biți. Având în vedere resurse și timp nelimitat, constanta lui Chaitin poate fi folosită pentru a demonstra conjectura Goldbach în felul următor. Să fie rulate în paralel toate programele cu lungimea N  + 1 biți sau mai puțin. Dacă un astfel de program de N - biți se oprește, atunci conjectura lui Goldbach se va dovedi greșită. Dacă, pe de altă parte, se opresc suficiente alte programe, astfel încât un alt program oprit rezultă într-un număr mai mare decât constanta lui Chaitin, atunci dacă programul nu se oprește, atunci nu se va opri niciodată și se va dovedi conjectura lui Goldbach. Pentru a aplica această metodă, avem nevoie doar de primii N biți ai constantei lui Haitin.

Aceeași constantă Chaitin poate fi folosită pentru a demonstra ipoteza Riemann și multe alte probleme nerezolvate din matematică .

Interpretare ca probabilități

Spațiul Cantor este colecția tuturor secvențelor infinite de zerouri și unu. Probabilitatea de oprire poate fi interpretată ca o măsură a unui anumit subset al spațiului Cantor sub măsura obișnuită a probabilității pe spațiul Cantor. Din această interpretare a apărut denumirea probabilităților de oprire.

O măsură de probabilitate pe un spațiu Cantor, uneori numită măsură de monedă echilibrată, este definită astfel încât pentru orice șir binar x , setul de secvențe care încep cu x are măsura 2 -| x | . Această afirmație implică faptul că pentru orice număr natural n , mulțimea de secvențe f din spațiul Cantor astfel încât f ( n ) = 1 are măsura 1/2, iar mulțimea de secvențe al căror termen al n-lea este 0 au de asemenea măsura 1/2.

Fie F  o funcție calculabilă universală prefixă. Domeniul său P constă dintr-un set infinit de șiruri binare

Fiecare dintre aceste linii p i definește o submulțime S i a spațiului Cantor; mulţimea S i conţine toate secvenţele din spaţiul Cantor care încep cu p i . Aceste mulțimi nu se intersectează, deoarece P  este o mulțime de prefix. Sumă

reprezinta masura multimii

.

Astfel Ω F reprezintă probabilitatea ca o secvență infinită aleasă aleatoriu de 0 și 1s să înceapă cu un șir de biți (de o lungime finită) care aparține domeniului lui F . Din acest motiv Ω F se numește probabilitate de oprire.

Proprietăți

Fiecare constantă Haitin Ω are următoarele proprietăți:

Nu orice mulțime care are același grad de indecidibilitate Turing ca problema de oprire este o probabilitate de oprire. O relație de echivalență mai bună, echivalența Solovay , poate fi utilizată pentru a caracteriza probabilitățile de oprire între numerele reale stânga-ce.[ clarifica ]

Incomputabilitatea probabilităților de oprire

Se spune că un număr real este calculabil dacă există un algoritm care, dat n , returnează primele n cifre ale numărului. Instrucțiunea este echivalentă cu existența unui program care enumerează cifrele unui număr real.

Nicio probabilitate de oprire nu este calculată. Dovada acestui fapt se bazează pe un algoritm care, având în vedere primele n numere, rezolvă problema opririi programelor de până la n biți. Deoarece problema opririi este indecidabilă, Ω nu poate fi calculat.

Algoritmul funcționează după cum urmează. Dacă sunt date primele n numere Ω și k ≤ n , atunci algoritmul enumerează domeniul F până când un număr suficient de elemente de domeniu găsite reprezintă o probabilitate situată în 2 -(k+1) Ω. După aceea, niciun program de lungime k nu mai poate fi în zona luată în considerare. Astfel, setul de șiruri de lungime k este exact setul de astfel de șiruri deja enumerate.

Teorema de incompletitudine pentru probabilitățile de oprire

Pentru fiecare sistem de axiome consistent suficient de bogat de numere naturale , cum ar fi axiomele lui Peano , există o constantă N astfel încât să se demonstreze dacă orice bit de Ω după N -ul este zero sau unu este imposibil în acel sistem de axiome. Constanta depinde de cât de bogat este sistemul formal dat și, prin urmare, nu reflectă în mod direct complexitatea sistemului de axiome. Rezultatul obținut este similar cu teorema de incompletitudine a lui Gödel prin aceea că nicio teorie formală a aritmeticii nu poate fi completă.

Calculul originii lui Ω Khaitin

Calude, Dinneen și Shu au calculat primii 64 de biți ai lui Haitin Ω U pentru o anumită mașină. Iată-le, în notație binară :

0,000000100000010000011000100001101000111110010111011101000010000…

și în notație zecimală :

0,0078749969978123844…

Trebuie remarcat faptul că capacitatea de a calcula corect o anumită (dar nu orice) cifră Ω diferă de conceptul de calculabilitate: orice anumită cifră a oricărui număr este calculabilă datorită faptului că pentru orice număr întreg există un program care o tipărește.

Super Omega

După cum am menționat mai sus, primii n biți ai constantei lui Khaitin Ω sunt aleatorii sau incompresibili în sensul că nu îi putem calcula cu un algoritm mai scurt decât n  - O(1) biți. Totuși, luați în considerare un algoritm scurt, dar care nu se oprește, care enumeră și execută metodic toate programele posibile; de îndată ce unul dintre ele se oprește, probabilitatea sa se adaugă rezultatului (inițial egală cu zero). După ora de sfârșit, primii n biți ai rezultatului nu se vor mai schimba (nu contează că timpul în sine nu este calculabil). Deci, există un algoritm scurt fără oprire al cărui rezultat converge (în timp finit) către primii n biți ai Ω pentru orice n . Cu alte cuvinte, enumerarea primilor n biți ai lui Ω este foarte compresibilă în sensul că ei sunt calculabili printr-un algoritm foarte scurt; nu sunt aleatorii în raport cu setul de algoritmi de enumerare. Jürgen Schmidhuber a construit în 2000 un „Super-Omega” calculat mărginit, care, într-un anumit sens, este mult mai aleatoriu decât Ω calculabil-mărginit inițial, deoarece Super-Omega nu poate fi comprimat semnificativ de niciun algoritm enumerativ fără oprire.

Vezi și

Note

  1. ↑ Thomas M. Cover și Joy A. Thomas, Elements of Information Theory, Ediția a 2-a, Wiley-Interscience, 2006.

Surse

Link -uri