Universalitetssannolikhet

Universalitetssannolikhet är ett abstrut sannolikhetsmått inom beräkningskomplexitetsteori som berör universella Turing-maskiner .

Bakgrund

En Turing-maskin är en grundläggande beräkningsmodell . Vissa Turing-maskiner kan vara specifika för att göra särskilda beräkningar. Till exempel kan en Turing-maskin ta indata som består av två tal och sedan producera utdata som är produkten av deras multiplikation . En annan Turing-maskin kan ta indata som är en lista med siffror och sedan ge utdata som är dessa nummer sorterade i ordning.

En Turing-maskin som har förmågan att simulera vilken annan Turing-maskin som helst kallas universell - med andra ord, en Turing-maskin (TM) sägs vara en universell Turing-maskin (eller UTM) om det, givet någon annan TM, finns en viss input (eller "header") så att den första TM givet den ingången "header" för alltid kommer att bete sig som den andra TM.

En intressant matematisk och filosofisk fråga uppstår då. Om en universell Turing-maskin ges slumpmässig inmatning (för lämplig definition av slumpmässig ), hur troligt är det att den förblir universell för alltid?

Definition

Givet en prefixfri Turing - maskin är universalitetssannolikheten för den sannolikheten att den förblir universell även när varje inmatning av den (som en binär sträng ) prefixeras av en slumpmässig binär sträng. Mer formellt är det sannolikhetsmåttet för realer (oändliga binära sekvenser) som har egenskapen att varje initialt segment av dem bevarar universaliteten hos den givna Turing-maskinen. Detta begrepp introducerades av datavetaren Chris Wallace och diskuterades först uttryckligen i tryck i en artikel av Dowe (och en efterföljande artikel). Men relevanta diskussioner förekommer också i en tidigare artikel av Wallace och Dowe.

Universalitetssannolikheter för prefixfria UTM:er är inte noll

Även om universalitetssannolikheten för en UTM (UTM) ursprungligen misstänktes vara noll, finns det relativt enkla bevis för att det högsta av uppsättningen universalitetssannolikheter är lika med 1, till exempel ett bevis baserat på slumpmässiga promenader och ett bevis i Barmpalias och Dowe (2012). När man väl har en prefixfri UTM med en universalitetssannolikhet som inte är noll, följer det omedelbart att alla prefixfria UTM :er har en universalitetssannolikhet som inte är noll. Vidare, eftersom det högsta av mängden universalitetssannolikheter är 1 och eftersom mängden { m / 2 n | 0 < n & 0 < m < 2 n } är tät i intervallet [0, 1], lämpliga konstruktioner av UTM:er (t.ex. om U är en UTM, definiera en UTM U 2 med U 2 (0 s ) stopp för alla strängar s , U 2 (1 s ) = U ( s ) för alla s) ger att mängden universalitetssannolikheter är tät i det öppna intervallet (0, 1).

Karakterisering och slumpmässighet av universalitetssannolikhet

Universalitetssannolikhet studerades noggrant och karakteriserades av Barmpalias och Dowe 2012. Sett som reella tal karakteriserades dessa sannolikheter helt i termer av begrepp inom beräkningsteori och algoritmisk informationsteori . Det visades att när den underliggande maskinen är universell, är dessa siffror mycket algoritmiskt slumpmässiga . Mer specifikt är det Martin-Löf slumpmässigt i förhållande till den tredje iterationen av stoppproblemet . Med andra ord, de är slumpmässiga i förhållande till nollmängder som kan definieras med fyra kvantifierare i Peano-aritmetik . Vice versa, givet ett sådant mycket slumpmässigt tal [ förtydligande behövs ] (med lämpliga approximationsegenskaper) finns det en Turing-maskin med universalitetssannolikhet det numret.

Relation med Chaitins konstant

Universalitetssannolikheter är mycket relaterade till Chaitin-konstanten , som är stoppsannolikheten för en universell prefixfri maskin. På sätt och vis är de komplementära till stoppsannolikheterna för universella maskiner i förhållande till den tredje iterationen av stoppproblemet . I synnerhet kan universalitetssannolikheten ses som den icke-stoppande sannolikheten för en maskin med orakel den tredje iterationen av stoppproblemet. Vice versa, den oavbrutna sannolikheten för en prefixfri maskin med detta mycket icke-beräknbara orakel är universalitetssannolikheten för någon prefixfri maskin.

Sannolikheter för maskiner som exempel på mycket slumpmässiga tal

Universalitetssannolikhet ger ett konkret och något naturligt exempel på ett mycket slumpmässigt tal (i betydelsen algoritmisk informationsteori) . På samma sätt ger Chaitins konstant ett konkret exempel på ett slumptal (men för en mycket svagare uppfattning om algoritmisk slumpmässighet).

Se även

externa länkar

Vidare läsning

  • Ming Li och Paul Vitányi (1997). En introduktion till Kolmogorovs komplexitet och dess tillämpningar . Springer. Introduktion kapitel fulltext .
  •   Cristian S. Calude (2002). Information and Randomness: An Algorithmic Perspective , andra upplagan. Springer. ISBN 3-540-43466-6
  • R. Downey och D. Hirschfeldt (2010), Algorithmic Randomness and Complexity , Springer-Verlag.
Hämtad från " https://en.wikipedia.org/w/index.php?title=Universality_probability&oldid=1122129221 "