Khaitin er konstant

Den aktuelle version af siden er endnu ikke blevet gennemgået af erfarne bidragydere og kan afvige væsentligt fra den version , der blev gennemgået den 7. marts 2020; checks kræver 5 redigeringer .

Inden for datalogi - algoritmisk informationsteori - er Khaitins konstante , eller stopsandsynlighed , et reelt tal , der uformelt set er sandsynligheden for , at et vilkårligt valgt program vil stoppe . Eksistensen af sådanne tal blev demonstreret af Gregory Chaitin .

Selvom der er et uendeligt antal stopsandsynligheder, er det almindeligt at bruge bogstavet Ω til at repræsentere dem alle, som om der kun var et sådant tal. Da den numeriske værdi af Ω afhænger af det anvendte programmeringssprog, kaldes det ofte Khaitin-konstruktionen , hvis det ikke refererer til noget specifikt sprog, og ikke Khaitin-konstanten .

Hver Ω er et normalt transcendentalt tal , som kan defineres, men ikke beregnes , hvilket betyder, at der ikke er nogen algoritme til at opregne dets cifre.

Baggrund

Definitionen af stopsandsynligheden er baseret på eksistensen af præfiks universelle beregnelige funktioner . Sådanne funktioner er visuelt set et programmeringssprog med den egenskab, at der ikke kan opnås et korrekt program som en tilsvarende udvidelse af et andet korrekt program.

Antag, at funktionen F afhænger af to argumenter, som hver er en endelig binær streng, og returnerer en binær streng som output. En funktion F kaldes beregnelig , hvis der er en Turing-maskine , der beregner den.

En funktion F kaldes universel , hvis følgende betingelser gælder: for hver beregnelig funktion f af en variabel x eksisterer der en konstant p , sådan at for enhver x F ( p , x ) = f ( x ). Det vil sige, F kan bruges til at modellere enhver beregnelig funktion af en variabel. Løst repræsenterer p et "program" for en beregnelig funktion f , og F repræsenterer en emulator, der tager et program som input og udfører det. Det skal bemærkes, at for enhver fast p , kan funktionen f ( x ) = F ( p , x ) beregnes; således angiver universalitetsegenskaben, at alle beregnelige funktioner af en enkelt variabel kan opnås på denne måde.

Domænet af F er sættet af alle programmer p sådan, at for mindst én værdi x er værdien F ( p , x ) defineret. En funktion kaldes præfiks, hvis dens domæne ikke indeholder to elementer p , p′ sådan at p′ er den tilsvarende udvidelse af p . Udsagnet kan omformuleres som følger: definitionsdomænet er præfikskoden på sættet af binære strenge af endelig længde. Domænet for enhver universel beregnelig funktion er et talrige sæt , men aldrig et beregneligt sæt . Dette domæne har altid samme grad af Turing-uafgørlighed som det stoppende problem .

Bestemmelse af stopsandsynligheder

Lad P F være domænet for præfikset universel beregnelig funktion F . Konstanten defineres så som $\Omega _{F}$

\Omega _{F}=\sum _{{p\in P_{F}}}2^{{-|p|}}

hvor angiver længden af strengen p . Dette er en uendelig sum over alle p fra domænet af F . Kravet om, at domænet skal have præfiks, sammen med Krafts ulighed , er tilstrækkeligt til, at denne sum kan konvergere til et reelt tal fra 0 til 1. Hvis F er klart fra konteksten, kan Ω F blot betegnes som Ω, selvom forskellige præfikser universelle beregnelige funktioner fører til forskellige værdier af Ω. $|p|$

Anvendelse af Ω til beviset for uløste problemer i talteori

Chaitins konstant kan i princippet bruges til at løse mange udestående problemer inden for talteori , herunder Goldbachs problem og Riemann-hypotesen . [1] Formuleringen af Goldbachs problem siger, at ethvert lige tal større end 2 er summen af to primtal. Lad et computerprogram søge efter de tilsvarende primtal for et givet lige tal. Hvis Goldbachs formodning er korrekt, går programmet videre til det næste lige tal, og søgningen fortsætter. Hvis der ikke er to primtal, der summerer til det krævede lige tal, så vil et modeksempel blive fundet, programmet stopper, og Goldbachs formodning vil blive tilbagevist. Lad længden af dette program være N bit. Givet ubegrænsede ressourcer og tid, kan Chaitins konstant bruges til at bevise Goldbach-formodningen på følgende måde. Lad alle programmer med længden N + 1 bit eller mindre køre parallelt. Hvis et sådant N -bit program stopper, så vil Goldbachs formodning blive bevist forkert. Hvis der derimod stopper nok andre programmer, så et andet stoppet program resulterer i et tal større end Chaitins konstant, så stopper programmet ikke, så stopper det aldrig, og Goldbachs formodning vil blive bevist. For at anvende denne metode behøver vi kun de første N bits af Haitins konstant.

Den samme Chaitin-konstant kan bruges til at bevise Riemann-hypotesen og mange andre uløste problemer i matematik .

Fortolkning som sandsynligheder

Cantor-rummet er samlingen af alle uendelige sekvenser af nuller og enere. Stopsandsynligheden kan fortolkes som et mål for en bestemt delmængde af Cantor-rummet under det sædvanlige sandsynlighedsmål på Cantor-rummet. Det er ud fra denne fortolkning, at navnet på standsningssandsynlighederne opstod.

Et sandsynlighedsmål på et Cantor-rum, nogle gange kaldet et balanceret møntmål, er defineret således, at for enhver binær streng x , har sættet af sekvenser, der starter med x , mål 2 -| x | . Dette udsagn indebærer, at for ethvert naturligt tal n har mængden af sekvenser f i Cantor-rummet, således at f ( n ) = 1 har mål 1/2, og mængden af sekvenser, hvis n'te led er 0, har også mål 1/2.

Lad F være et præfiks, universel beregnelig funktion. Dens domæne P består af et uendeligt sæt binære strenge

P=\{p_{1},p_{2},\ldots \}

Hver af disse linjer pi definerer en delmængde Si af Cantor -rummet; sættet S i indeholder alle sekvenser i Cantor-rummet, der starter med p i . Disse mængder skærer ikke hinanden, da P er et præfikssæt. Sum

\sum _{{p\in P}}2^{{-|p|}}

repræsenterer sættets mål

\bigcup _{{i\in {\mathbb {N))))S_{i}

Således repræsenterer Ω F sandsynligheden for, at en tilfældigt valgt uendelig sekvens af 0'er og 1'er starter med en bitstreng (af en vis endelig længde), der hører til domænet af F . Det er af denne grund, at Ω F kaldes stopsandsynligheden.

Egenskaber

Hver Haitin-konstant Ω har følgende egenskaber:

Ω er algoritmisk tilfældig . Det vil sige, at for hvert enkelt programmeringssprog er der en konstant C , således at for hver n må ethvert stopprogram på det sprog, der udsender de første n bit af Ω, ikke være kortere end ( n - C ) bit.
Ω er et normalt tal , hvilket betyder, at dets cifre er ligeligt fordelt, som om de blev opnået ved at kaste en balanceret mønt.
Ω er et uberegneligt tal ; der er ingen beregnelig funktion, der opregner dens binære ekspansion, som beskrevet nedenfor.
Sættet af rationelle tal q således at q < Ω kan tælles ; et reelt tal med denne egenskab kaldes et venstre-ce reelt tal i rekursionsteori .
Sættet af rationelle tal q således, at q > Ω er ikke-tælleligt.
Ω er et aritmetisk tal .
Ω har samme grad af Turing-uafgørlighed som standsningsproblemet og er således på niveau med det aritmetiske hierarki. $\Sigma _{1}^{0}$

Ikke alle sæt, der har samme grad af Turing-uafgørlighed som standsningsproblemet, er en standsningssandsynlighed. En bedre ækvivalensrelation, Solovay ækvivalens , kan bruges til at karakterisere sandsynligheden for at stoppe blandt venstre-ce reelle tal.[ ryd op ]

Ikke-beregnelighed for stopsandsynligheder

Et reelt tal siges at kunne beregnes, hvis der er en algoritme, der givet n returnerer de første n cifre i tallet. Udsagnet svarer til eksistensen af et program, der opregner cifrene i et reelt tal.

Ingen stopsandsynlighed kan beregnes. Beviset for dette faktum er baseret på en algoritme, der givet de første n tal, løser problemet med at stoppe programmer op til n bit lange. Da stopproblemet ikke kan afgøres, kan Ω ikke beregnes.

Algoritmen fungerer som følger. Hvis de første n tal Ω og k ≤ n er givet , så opregner algoritmen domænet F , indtil et tilstrækkeligt antal fundne domæneelementer repræsenterer en sandsynlighed, der ligger i 2 -(k+1) Ω. Derefter kan intet program af længden k være i det pågældende område. Således er sættet af strenge med længden k præcis det sæt af sådanne strenge, der allerede er opført.

Ufuldstændighedssætningen for at stoppe sandsynligheder

For hvert konsistent tilstrækkeligt rige aksiomsystem af naturlige tal , såsom Peanos aksiomer , eksisterer der en konstant N , som beviser, om en hvilken som helst bit af Ω efter N'et er nul eller en er umulig i det aksiomsystem. Konstanten afhænger af, hvor rigt det givne formelle system er, og afspejler således ikke direkte kompleksiteten af aksiomsystemet. Det opnåede resultat ligner Gödels ufuldstændighedssætning , idet ingen formel aritmetikteori kan være fuldstændig.

Beregning af oprindelsen af Ω Khaitin

Calude, Dinneen og Shu beregnede de første 64 bits af Haitins Ω U for en bestemt maskine. Her er de, i binær notation :

0,00000010000001000001100010000110100011111110010111011101000010000…

og i decimalnotation :

0,0078749969978123844…

Det skal bemærkes, at evnen til korrekt at beregne et bestemt (men ikke et hvilket som helst) ciffer Ω adskiller sig fra begrebet beregnelighed: ethvert bestemt ciffer af et hvilket som helst tal kan beregnes på grund af det faktum, at der for ethvert heltal er et program, der udskriver det.

Super Omega

Som nævnt ovenfor er de første n bit af Khaitins konstant Ω tilfældige eller inkompressible i den forstand, at vi ikke kan beregne dem med en algoritme, der er kortere end n − O(1) bit. Overvej dog en kort, men aldrig standsende algoritme, der metodisk opregner og udfører alle mulige programmer; så snart en af dem stopper, tilføjes dens sandsynlighed til resultatet (i første omgang lig med nul). Efter sluttidspunktet vil de første n bit af resultatet ikke længere ændre sig (det gør ikke noget, at selve tiden ikke kan beregnes). Så der er en kort ikke-standsende algoritme, hvis resultat konvergerer (i begrænset tid) til de første n bit af Ω for enhver n . Med andre ord er opregningen af de første n bit af Ω meget komprimerbar i den forstand, at de kan beregnes med en meget kort algoritme; de er ikke tilfældige med hensyn til sættet af opregningsalgoritmer. Jürgen Schmidhuber konstruerede i 2000 en afgrænset beregningsbar "Super-Omega", som i en vis forstand er meget mere tilfældig end den oprindelige afgrænsede beregnelige Ω, da Super-Omega'en ikke kan komprimeres væsentligt af nogen opregnende ikke-stoppende algoritme.

Se også

Noter

↑ Thomas M. Cover og Joy A. Thomas, Elements of Information Theory, 2. udgave, Wiley-Interscience, 2006.

Kilder

Christian S. Calude (2002). Information and Randomness: An Algorithmic Perspective , anden udgave. Springer. ISBN 3-5404-3466-6
Christian S. Calude, Michael J. Dinneen og Chi-Kou Shu. Beregning af et glimt af tilfældighed .
R. Downey og D. Hirschfeldt (200?), Algorithmic Randomness and Complexity , monografi under forberedelse, Springer-Verlag. Foreløbig version kan findes online .
Ming Li og Paul Vitányi (1997). En introduktion til Kolmogorovs kompleksitet og dens anvendelser . Springer. Introduktionskapitlet i fuld tekst .
Jürgen Schmidhuber (2000). Algoritmiske teorier om alting (arXiv: quant-ph/0011122). Tidsskriftsreference: J. Schmidhuber (2002). Hierarkier af generaliserede Kolmogorov-kompleksiteter og utallige universelle mål, der kan beregnes i grænsen. International Journal of Foundations of Computer Science 13(4):587-612.