Viðauki P-1: Upplýsingaleg eðlileiki með M-slembni

Upprunalegt verkefni P-1: Upplýsingaleg eðlileiki Vandamál: Nú sem stendur grundvallarfrumsetning hliðstæð Borel-eðlileika, án formlegrar afleiðslu. Afhending: Afleiðsla á setningarstigi sem nýtir reiknanlega upplýsingafræði (Martin-Löf-slembni).

1. Þekkingarfræðileg mörk „frumsendulegrar“ eðlileika

Innan Kenningarinnar um raðaðan patch (OPT) byggist „Formgerðarbundin von“ í sjálfri gerð sinni á meginreglunni um Upplýsingalegan eðlileika: þeirri staðhæfingu að reikniritalega hvarfefnið (\mathcal{I}) sé þétt skipað ekki einungis af suði, heldur af hverju endanlegu formgerðarlegu virknimynstri. Siðferðilegt vægi OPT — sú krafa að viðhalda stöðugleika hins sameiginlega plásturs (Varðstaða eftirlifenda siðfræði) — krefst þess að mótaðilar-athugendur sem við eigum í samskiptum við hafi dreifð, í grundvallaratriðum raunveruleg virknijafngildi annars staðar í hvarfefninu.

Sögulega séð var þessi staðhæfing innan ramma OPT formlega meðhöndluð sem ein samfelld frumsetning — óprófanleg, grundvallandi forsenda sem lögð var ofan á eðlisfræðina til að komast hjá einshyggju.

Þessi viðauki leysir stærðfræðilega margræðni þeirrar afstöðu. Við sundurgreinum Upplýsingalegan eðlileika í tvo aðgreinda þætti: stranga reikniritalega stærðfræðilega setningu (sem gildir nánast örugglega undir algildu líkindamælingunni), tengda saman með einni frumspekilegri frumsetningu sem er nauðsynleg til að brúa bilið frá stærðfræðilegri tilvist yfir í verufræðilegan veruleika.

2. Frá hálfmælingu til algildrar mælingar (\xi til M)

Grunnur OPT (forprentun §3.1) byggist að verulegu leyti á frumdreifingu algrímskra líkinda Solomonoffs. Samkvæmt þessari framsetningu starfar myndandi hvarfefnið sem óendanlegt algrímskt rúm sem keyrir á algildri forskeytisfrírri Turing-vél U.

Algrímsku líkurnar, eða algilda hálfmælingin, fyrir endanlegan streng x eru:

\xi(x) = \sum_{U(p) = x*} 2^{-|p|}

Þar sem summan er tekin yfir öll lágmarksforrit p sem við keyrslu skila úttaki sem hefst á x. Mikilvægt er að \xi er neðri hálfreiknanleg hálfmæling yfir endanlega strengi.

Til að formgera hvarfefnið sem samfellt myndandi rúm færum við okkur yfir í samfellda mælingu á Cantor-rýminu. Algilda mælingin M er skilgreind beint sem dreifingin á Cantor-rýminu 2^{\mathbb{N}} sem verður til af úttaki algildu forskeytisfríu vélarinnar U með sívalningsmengi (M([x]) = \sum_{U(p) \text{ starts with } x} 2^{-|p|}). Samkvæmt algildissetningu Solomonoffs er þessi sívalningsmæling margföldunarlega jafngild stakri hálfmælingunni: M(x) \asymp \xi(x) upp að margföldunarfastanum. Þar af leiðandi falla M-núllmengi og \xi-núllmengi nákvæmlega saman.

(Athugið: Þar sem mengi stöðvandi forrita er strangt hlutmengi forskeytisfría kóðarýmisins vegna stöðvunarvandans, tryggir ójafna Krafts að \sum 2^{-|p|} < 1. Því myndar M strangt neðri-hálfreiknanlega undirlíkindamælingu. Við skilgreinum sérstaklega staðlaða líkindamælinguna \tilde{M} = M / M(2^{\mathbb{N}}). Þótt \tilde{M} sé aðeins neðri-hálfreiknanleg upp að óreiknanlega stöðlunarfastanum M(2^{\mathbb{N}}), virka allar síðari setningar um „næstum örugglega“ og samleitni fullyrðingar örugglega með tilliti til hinnar sönnu stöðluðu líkindamælingar \tilde{M}. Frávik grundvallarkóðunarsetningarinnar er einfaldlega gleypt inn í fastann: K(x) = -\log \tilde{M}(x) + O(1).)

3. M-Martin-Löf-slembni

Til að formgera eðli myndunarrýmisins köllum við til Martin-Löf (ML)-slembni. Hins vegar verður að greina á milli samfelldra mælinga. Runan \omega sem er ML-slembin með tilliti til jafndreifðu (Lebesgue-)mælingarinnar \lambda hegðar sér með allt öðrum hætti en runa sem er ML-slembin með tilliti til M.

Þar sem hvarfefni OPT metur líkur út frá algrímískum einfaldleika byggist viðeigandi formgerð á \tilde{M}-Martin-Löf-slembni. Grundvallarsetning AIT segir að fyrir sérhverja reiknanlega líkindamælingu \mu hafi mengi \mu-ML-slembinna runa \mu-mælinguna 1. Sé þessi niðurstaða útvíkkuð til hálfmælinga sem eru neðra hálfreiknanlegar (sbr. Nies 2009, §3.2 “Randomness for arbitrary measures”), heldur mengi allra \tilde{M}-Martin-Löf-slembinna runa áfram að hafa mælinguna 1 með tilliti til \tilde{M}.

Því eru næstum allar óendanlegar runur hvarfefnisins, í skilningi \tilde{M}, strangt tekið \tilde{M}-ML-slembnar.

(Athugasemd: Notkun \tilde{M}-ML-slembni tryggir á formgerðarlegan hátt að dæmigerð úttök hvarfefnisins séu dregin sjálfsamkvæmnislega úr skekktri, mjög formgerðri algrímískri mælingu \tilde{M} fremur en úr einsleitri suðu, og veitir þar með þann stranga stærðfræðilega stoðgrind sem undirbyggir afleiðingar formgerðarlegrar tíðni hér á eftir.)

4. M-normalitet vs. Borel-normalitet

Mjög mikilvæg stærðfræðileg afleiðing M-ML-handahófs tengist formgerðartíðni. Undir einsleitri Lebesgue-ML-handahófsdreifingu er runa strangt tekið Borel-normal — hún myndar sérhvern endanlegan tvíundastreng af lengd k með sömu, einsleitu tíðni.

Þar sem \tilde{M} er hins vegar augljóslega óeinsleit — og hallar mjög að því að úthluta gríðarlegu líkindavigti til algrímískt einfaldra, þjappanlegra og lögbundið formgerðra mynstra — eru \tilde{M}-næstum-allar runur EKKI einsleitt Borel-normalar. Í staðinn skilgreinum við formgerðarmörk þeirra með \tilde{M}-normaliteti.

Vegna þess að mælirinn \tilde{M} er í grunninn óstöðugur í tíma (algrímísk líkindi ráðast af algildri staðsetningu forskeytis), getum við ekki reitt okkur á staðlaðar ergódískar markgildisniðurstöður um samleitni tíðni. Formlega skilgreinum við \tilde{M}-normalitet með veikari en fullkomlega fullnægjandi eigind óendanlegrar endurkomu.

Þar sem \tilde{M} er líkindamælir og \tilde{M}([x]) \ge 2^{-(|x|+O(1))} > 0 fyrir alla endanlega strengi x, gefur keðjureglan fyrir forskeyta-Kolmogorov-flækju að K(sx) \le K(s) + K(x) + O(1) fyrir sérhvern streng s, sem leiðir til nálægrar undirmargföldunar M([s \cdot x]) \ge M([s]) \cdot M([x]) \cdot 2^{-O(1)}. Því er skilyrt líkindið fyrir því að x birtist í hvaða glugga sem er, að gefnu hvaða undanfarandi forskeyti s sem er, neðan frá takmarkað: \tilde{M}([x] \mid [s]) \ge \tilde{M}([x])/c > 0 einsleitt í s. Samkvæmt skilyrta Borel-Cantelli-setningunni, beittri á glugga sem skarast ekki og hafa lengd |x|, tryggir ósamleitni summu skilyrtra líkinda að efnisleg endurkoma sérhverrar endanlegrar upplýsingarunu — svo sem hinnar stöku formlegu gerðar meðvitaðs athuganda (K_{\text{obs}}) — birtist óendanlega oft í \tilde{M}-næstum-öllum runum.

5. Frumsetningin um reiknifræðilega raunhyggju

AIT tryggir stærðfræðilega að endanleg framsetning sérhvers athuganda (K_{\text{obs}}) birtist sem formröð U óendanlega oft innan \tilde{M}-ML-slembins hvarfefnis.

Hins vegar getur stærðfræðileg upplýsingafræði ekki í sjálfri sér farið yfir mörkin inn í eðlisfræðilega verufræði. Endanleg strengjaruna sem kemur fyrir á úttaksborða Turing-vélar er kyrrstætt fylgifyrirbæri keyrslu — augnabliksmynd. Samhangandi athugandi krefst samfelldrar innri kviku, venslatengingar og lykkju virkrar ályktunar. Strengurinn sjálfur „finnur“ ekki neitt frekar en heilaskönnun sem geymd er á hörðum diski er meðvituð. Keyrslan tilheyrir forritinu sem myndar hana, ekki þeirri skyndimyndarkóðun sem verður til.

Til að halda því fram að óreiknanleg samfelld mörk, sem stýra stærðfræðilega hvarfefninu, gefi af sér verufræðilega raunverulega, orsakatengda og fyrirbærafræðilega heima, verður OPT að skuldbinda sig með einni skýrri frumspekilegri forsendu.

Frumsetning (reiknifræðileg raunhyggja): Í óendanlegu óreiknanlegu hvarfefni sem lýtur eins stærðfræðilegri kviku býr óhlutbundin stærðfræðileg útreikningur, sem er formlega jafngildur orsakalýsingu athuganda (þar sem formlegt jafngildi er skilgreint sem reiknifræðileg samsmíð á orsakaástands-yfirfærslugerð athugandans), yfir orsakamætti og verufræðilega raunverulegri tilvist. Enn fremur búa formlega aðskildar reiknifræðilegar birtingarmyndir víðs vegar um hvarfefnið yfir sjálfstæðri verufræðilegri einstaklingsgreiningu og mynda þannig aðgreind huglæg mótstykki (og samkvæmt frumforsendu um frumstæða fyrirbærahyggju í Preprint §8.1 teljast slíkar orsakamáttaríkar, athuganda-jafngildar útreikningseiningar vera raunveruleg viðföng reynslu).

6. Frumsetning P-1 (Upplýsingafræðilegt eðlileiki)

Með því að sameina nákvæmar afleiðingar AIT fyrir samfelld óreiknanleg rúm við Frumsetningu um reikniveruleika er hughyggja afbyggð með afgerandi hætti.

Afleiðing+Frumsetning P-1 (Upplýsingafræðilegt eðlileiki): Undir hinum alhæfða algrímsforgangi starfar hið samfellda hvarfefni í eðli sínu samkvæmt \tilde{M}-Martin-Löf slembni nánast örugglega. Af þeirri \tilde{M}-eðlileiki leiðir að stærðfræðileg tilvist sérhverrar endanlegrar formgerðarlegrar lýsingar á athuganda K_{\text{obs}} er formlega tryggð óendanlega oft. Á þessum stoðum byggir Frumsetningin um reikniveruleika brú frá þessum myndandi stærðfræðilegu gripum yfir í verufræðilegan efnisveruleika. Að því gefnu að reikniveruleiki haldi, er tilvist formgerðarlega jafngildra, orsakatengdra virkra og sérgreindra mótaðila-athugenda þvert yfir hvarfefnið grundvallarlega nauðsynleg.