Pravděpodobnost univerzality - Universality probability

Pozadí

A Turingův stroj je základní model výpočet. Nějaký Turingovy stroje může být specifické pro konkrétní výpočty. Například Turingův stroj může přijmout vstup, který obsahuje dvě čísla, a poté produkovat výstup, který je produktem jejich násobení. Jiný Turingův stroj může přijmout vstup, který je seznamem čísel, a poté dát výstup, který je těmito čísly tříděny v pořádku.

A Turingův stroj který má schopnost simulovat jakýkoli jiný Turingův stroj se nazývá univerzální - jinými slovy, o Turingově stroji (TM) se říká, že je univerzální Turingův stroj (nebo UTM), pokud, vzhledem k jakékoli jiné TM, existuje nějaký vstup (nebo „záhlaví“) takový, že první TM zadaná jako vstupní „záhlaví“ se bude navždy chovat jako druhá TM.

Zajímavý matematický a filozofický pak vyvstává otázka. Pokud univerzální Turingův stroj je uveden náhodný vstup (pro vhodnou definici náhodný ), jak je pravděpodobné, že navždy zůstane univerzální?

Definice

Vzhledem k bez předpony Turingův stroj, pravděpodobnost univerzality z toho je pravděpodobnost že to zůstane univerzální i když každý jeho vstup (jako a binární řetězec ) je předponou náhodným binárním řetězcem. Formálně je to míra pravděpodobnosti reals (nekonečné binární sekvence), které mají tu vlastnost, že každý jejich počáteční segment zachovává univerzálnost daného Turingova stroje. Tuto představu představil počítačový vědec Chris Wallace a byla poprvé výslovně diskutována v tisku v článku Doweho[1] (a následující článek[2]). Relevantní diskuse se však také objevují v dřívějším článku Wallace a Dowe.[3]

Pravděpodobnosti univerzality UTM bez předpony jsou nenulové

Ačkoli univerzálnost pravděpodobnost a UTM (UTM) byl původně podezřelý z nuly, existují poměrně jednoduché důkazy, že supremum množiny pravděpodobností univerzality se rovná 1, například důkaz založený na náhodné procházky[4] a důkaz v Barmpalias a Dowe (2012). Jakmile jeden takový má bez předpony UTM s nenulovou pravděpodobností univerzálnosti z toho okamžitě vyplývá bez předpony UTM mají nenulovou pravděpodobnost univerzality. Dále proto, že supremum množiny pravděpodobností univerzality je 1 a protože množina { m/ 2n | 0 < n & 0 < m < 2n} je hustý v intervalu [0, 1] vhodné konstrukce UTM (např. pokud U je UTM, definujte aUTM U2 podle U2(0s) zastaví pro všechny řetězce s, U2(1s) = U(s) pro všechna s) udává, že množina pravděpodobností univerzality jehustý v otevřeném intervalu (0, 1).

Charakterizace a náhodnost pravděpodobnosti univerzálnosti

Pravděpodobnost univerzality byla důkladně prostudována a charakterizována Barmpaliasem a Dowem v roce 2012.[5]Viděn jako reálná čísla, tyto pravděpodobnosti byly zcela charakterizovány pojmy v teorie vypočítatelnosti a teorie algoritmických informací Ukázalo se, že když je základní stroj univerzální, tato čísla jsou velmi vysoká algoritmicky náhodné. Přesněji řečeno je Martin-Löf náhodné vzhledem ke třetí iteraci zastavení problému. Jinými slovy, jsou náhodné vzhledem k nulovým množinám, které lze definovat čtyřmi kvantifikátory Peano aritmetika. Naopak, vzhledem k tak vysoce náhodnému číslu[je zapotřebí objasnění ] (s příslušnými aproximačními vlastnostmi) existuje Turingův stroj s pravděpodobností univerzálnosti tohoto čísla.

Vztah s Chaitinovou konstantou

Pravděpodobnosti univerzality velmi souvisí s Chaitinová konstanta, což je pravděpodobnost zastavení univerzálního stroje bez předpony. V jistém smyslu doplňují pravděpodobnosti zastavení univerzálních strojů ve vztahu ke třetí iteraci zastavení problému. Na pravděpodobnost univerzality lze zejména pohlížet jako na non-stop pravděpodobnost stroje s Oracle třetí iterací problému zastavení. Naopak, nezastavující se pravděpodobnost jakéhokoli stroje bez předpony s tímto vysoce nevypočitatelným věštcem je pravděpodobnost univerzálnosti nějakého stroje bez předpony.

Pravděpodobnosti strojů jako příklady vysoce náhodných čísel

Pravděpodobnost univerzality poskytuje konkrétní a poněkud přirozený příklad vysoce náhodného čísla (ve smyslu teorie algoritmických informací ). Ve stejném smyslu poskytuje Chaitinova konstanta konkrétní příklad náhodného čísla (ale pro mnohem slabší představu o algoritmické náhodnosti).

Viz také

Reference

  1. ^ *Dowe, D.L. (5. září 2008). „Předmluva k C. S. Wallaceovi“. Počítačový deník. 51 (5): 523–560. doi:10.1093 / comjnl / bxm117. (a tady )
  2. ^ * Dowe, D. L. (2011), "MML, hybridní Bayesovské síťové grafické modely, statistická konzistence, invariance a jedinečnost ", Handbook of the Philosophy of Science - (HPS Volume 7) Philosophy of Statistics, P.S. Bandyopadhyay a M.R. Forster (eds.), Elsevier, pp901-982
  3. ^ Wallace, C. S. & Dowe, D. L. 1999 Minimální délka zprávy a Kolmogorovova složitost Počítač J. 42, 270–283
  4. ^ * Hernandez-Orallo, J. & Dowe, D. L. (2013), „O potenciálních kognitivních schopnostech ve strojovém království“, Mysl a stroje, Sv. 23, vydání 2, pp179-210
  5. ^ Barmpalias, G. a Dowe D.L. (2012). "Pravděpodobnost univerzality stroje bez předpony". Filozofické transakce královské společnosti A. 370 (1): 3488–3511. Bibcode:2012RSPTA.370.3488B. CiteSeerX  10.1.1.221.6000. doi:10.1098 / rsta.2011.0319. PMID  22711870.

externí odkazy

Další čtení

  • Ming Li a Paul Vitányi (1997). Úvod do Kolmogorovovy složitosti a jejích aplikací. Springer. Úvodní kapitola fulltext.
  • Cristian S.Calude (2002). Informace a náhodnost: Algoritmická perspektiva, druhé vydání. Springer. ISBN  3-540-43466-6
  • R. Downey a D. Hirschfeldt (2010), Algoritmická náhodnost a složitost, Springer-Verlag.