Super-Turing Computing

Super-Turing-beräkningar (eller hyperberäkningar ( eng.  hypercomputation )) är sådana beräkningar som inte kan göras på en Turing-maskin . De inkluderar en mängd olika hypotetiska metoder baserade på superrekursiva algoritmer , såväl som några andra typer av beräkningar - till exempel interaktiva beräkningar. . Termen hypercomputation introducerades först av Jack Copeland och Diana Proudfoot .  [1] Möjligheten till fysisk implementering av sådana beräkningar diskuteras aktivt.

Historik

Modeller som är kraftfullare än en Turing-maskin introducerades av Alan Turing i hans 1939 arbete Systems of Logics Based on Ordinals . Detta arbete utforskade matematiska system som hade ett orakel som kunde beräkna en enda godtycklig icke-rekursiv funktion på uppsättningen naturliga tal . Han använde denna modell för att visa att även i ett så kraftfullare system finns det fortfarande icke beräkningsbara funktioner (till exempel problemet med att stoppa orakelmaskinen). I sitt arbete gjorde Turing det klart att en sådan modell inte är något annat än en matematisk abstraktion och inte kan implementeras i den verkliga världen. [2]

Avsedda sätt för super-Turing-beräkning

• En Turing-maskin som kan ta ett oändligt antal steg på en ändlig tid (det räcker inte att helt enkelt köra en Turing-maskin under en oändlig tid (d.v.s. potentiell oändlighet ). Ett påstått sätt att uppnå detta är att använda tidsdilatation för att låta datorn slutföra ett oändligt antal cykler på en ändlig tid enligt den externa observatörens klocka (en sådan beräkning skulle kräva oändlig energi - se Malamet-Hogarth rum-tid ). Ett annat, rent matematiskt, sätt är den så kallade Zeno-maskinen , baserad på Zenos paradox . Zeno-maskinen slutför sitt första beräkningssteg i tid, säg 1 minut, nästa på ½ minut, det tredje på ¼ minut osv. När vi summerar denna oändliga geometriska progression får vi att maskinen utför ett oändligt antal steg i 2 minuter. Men enligt resonemang som liknar Zenos klassiska paradox är en sådan maskin omöjlig inte bara fysiskt utan också logiskt. [3]

• En evig Turing-maskin är en generalisering av en Zeno-maskin som kan utföra en obestämd lång beräkning vars steg numreras om av potentiellt transfinita ordningstal . Den modellerar en annars vanlig Turing-maskin, för vilken oavbrutna beräkningar avslutas genom att nå ett speciellt tillstånd som är reserverat för att nå gränsordningen , och för vilken resultaten från alla tidigare oändliga beräkningar är tillgängliga. [fyra]
• En riktig dator (en underart av den idealiserade analoga datorn ) kanske kan utföra hyperberäkning [5] förutsatt att fysiken tillåter existensen av verkliga reella tal . Detta kräver förmodligen att det finns några mycket märkliga fysiklagar (till exempel närvaron av en mätbar fysisk konstant som kan användas som ett orakel - se t.ex. Khaitins konstant ) och bör som minimum kräva förmågan att mäta fysiska konstanter med godtycklig noggrannhet, trots termiskt brus och kvantmekaniska effekter .
• Kvantmekaniska system , som på något sätt använder till exempel en oändlig överlagring av tillstånd för att beräkna icke-beräknbara funktioner. [6] Detta är inte möjligt med en standardkvantdator , eftersom det har bevisats att en vanlig kvantdator är PSPACE-reducerbar (en kvantdator som kör polynomtid kan simuleras på en klassisk dator med polynomrymd ). [7]
• En teknik som kallas obegränsad determinism kan tillåta utvärdering av icke-beräknebara funktioner. Denna fråga är föremål för diskussion i litteraturen.
• Användningen av stängda tidsliknande kurvor tillåter, i motsats till vad många tror, ​​inte att utföra super-Turing-beräkningar, eftersom det inte finns någon oändlig mängd minne.
• I början av 1990-talet föreslog Chava Siegelmann [8] en modell baserad på den oändliga utvecklingen av neurala nätverk som är kapabla till hyperdatorer. [9]
• Under antaganden om ett kontinuerligt Newtonskt universum (när tid och rum är oändligt delbara) är det möjligt att bygga en kedja av beräkningsmoduler , som var och en är 2 gånger mindre och 2 gånger snabbare än den föregående [10] . I det här fallet finns det inget behov av att tillgripa obegränsade massor, krafter, hastigheter, eftersom en mindre storlek uppenbarligen innebär en snabbare beräkningsförmåga vid en fast fysisk hastighet av processen, . Maskinen har oändligt minne även om varje modul bara har ändligt minne, eftersom det finns oändligt många moduler. Dessutom är maskinen kapabel att utföra ett oändligt antal operationer på en ändlig tid, som Zeno-maskinen, eftersom operationerna för nästa modul slutförs på 2 gånger kortare tid än den föregående, och vi får en konvergent geometrisk progression av tidsintervall. Den väsentliga skillnaden mellan Zeno-maskinen och maskinen är att den inte kan arbeta med den tilldelade ändliga minnescellen ett oändligt antal gånger under en ändlig tid. Detta frigör från den så kallade Thomsons paradox [11] , vars essens är oförutsägbarheten av det slutliga resultatet av exekveringen av en oändlig sekvens av växelvis 0,1,0,1,... in i en fast minnescell .

Se även

• Church-Turing-uppsats
• Oracle (dator)
• Zeno maskin
• Datoranvändning
• Zenons paradox

Anteckningar

1. ↑ Alan Turings bortglömda idéer inom datavetenskap Arkiverad 11 november 2013 på Wayback Machine . Scientific American , april 1999.
2. ↑ "Anta att vi har något sätt att lösa problem i talteorin, ett orakel som ger lösningar på sådana problem. Vi får inte gå längre in på oraklets natur, förutom att det inte kan vara en maskin." (Undecidable s. 167, en nytryckning av Turings papper Systems of Logic Based On Ordinals )
3. ↑ Se till exempel Shagrir, O. Super-tasks, accelerating Turing machines and uncomputability  //  Theor. Comput. sci. 317, 1-3: journal. - 2004. - Juni ( vol. 317 ). - S. 105-114 . - doi : 10.1016/j.tcs.2003.12.007 . Arkiverad från originalet den 21 juli 2011.
4. ↑ Joel David Hemkins och Andy Lewis, Infinite time Turing machines Arkiverad 5 oktober 2011. , Journal of Symbolic Logic , 65(2):567-604, 2000.
5. ↑ Arnold Schönhage, "Om kraften hos direktåtkomstmaskiner", i Proc. Intl. Colloquium on Automata, Languages, and Programming (ICALP), sidorna 520-529, 1979. Källa för citat: Scott Aaronson , "NP-complete Problems and Physical Reality" Arkiverad 15 januari 2010, på Wayback Machine sid. 12
6. ↑ Det finns anspråk på detta; se till exempel Tien Kieu. Kvantalgoritm för Hilberts tionde problem   // Int . J. Theor. Phys. : journal. - 2003. - Vol. 42 . - P. 1461-1478 . - doi : 10.1023/A:1025780028846 . och den där citerade litteraturen. Felen i Kieus tillvägagångssätt påpekades av Warren D. Smith i Tre motexempel som motbevisar Kieus plan för "quantum adiabatic hypercomputation"; och några oberäkningsbara kvantmekaniska uppgifter Arkiverade 6 mars 2010 på Wayback Machine
7. ↑ Bernstein och Vazirani, Quantum complexity theory Arkiverad 11 mars 2016 på Wayback Machine , SIAM Journal on Computing, 26(5):1411-1473, 1997.
8. ↑ : BINDAR lab : HAVA'S BIO : . Hämtad 7 juni 2011. Arkiverad från originalet 4 oktober 2011. (obestämd)
9. ↑ Verifiering av egenskaper hos neurala nätverk Arkiverad 4 mars 2016 på Wayback Machine s.6
10. ↑ E.B. Davies, Building infinite machines , The British Journal for the Philosophy of Science , 52:671-682, 2001.
11. ↑ J. Thomson, Tasks and Super-Tasks , Analysis , 15:1-13, 1954.

Litteratur

• Martin Davis, Why there is no such discipline as hypercomputation , Applied Mathematics and Computation, Volym 178, Issue 1, 1 juli 2006, Sidorna 4-7, Special Issue on Hypercomputation
• Mike Stannett, Fallet för hypercomputation Arkiverad 4 mars 2016 på Wayback Machine , Applied Mathematics and Computation, Volym 178, Issue 1, 1 juli 2006, Sidorna 8-24, Special Issue on Hypercomputation
• Alan Turing, Systems of logic based on ordinals , Proc. London matematik. soc., 45 , 1939
• Hava Siegelmann. Neurala nätverk och analoga beräkningar: bortom Turing-gränsen Boston: Birkhäuser.
• Hava Siegelmann. Super Turing-teoriernas enkla dynamik ; Teoretisk datavetenskap volym 168, nummer 2, 20 november 1996, sid 461-472.
• Keith Douglas. Super-Turing Computation: a Case Study Analysis ( PDF ), MS Thesis, Carnegie Mellon University, 2003.
• L. Blum, F. Cucker, M. Shub, S. Smale, Complexity and Real Computation , Springer-Verlag 1997. Allmän utveckling av komplexitetsteori för abstrakta maskiner som beräknar på reella tal istället för bitar.
• Om beräkningskraften hos neurala nät  (otillgänglig länk)
• Toby Ord. Hyperberäkning: Beräknar mer än Turing-maskinen kan beräkna : En enkätartikel om olika former av hyperberäkning.
• Apostolos Syropoulos (2008), Hypercomputation: Computing Beyond the Church-Turing Barrier , Springer. ISBN 978-0-387-30886-9
• Burgin, MS (1983) Inductive Turing Machines, Notices of the Academy of Sciences of the USSR , v. 270, nr. 6, sid. 1289-1293
• Mark Burgin (2005), Superrekursiva algoritmer , Monografier i datavetenskap, Springer. ISBN 0-387-95569-0
• Cockshott, P. och Michaelson, G. Finns det nya beräkningsmodeller? Svar till Wegner och Eberbach, The computer Journal , 2007
• Copeland, J. (2002) Hypercomputation , Minds and machines, v. 12, sid. 461-502
• Martin Davis (2006), " The Church-Turing Thesis: Consensus and opposition ". Proceedings, Computability in Europe 2006. Föreläsningsanteckningar i datavetenskap, 3988 s. 125-132
• Hagar, A. och Korolev, A. (2007) Quantum Hypercomputation - Hype eller Computation? http://philsci-archive.pitt.edu/archive/00003180/
• Rogers, H. (1987) Teori om rekursiva funktioner och effektiv beräkningsbarhet, MIT Press, Cambridge Massachusetts

Länkar

• Hypercomputation Research  Network
• Toby Ord, Hypercomputation: datorer mer än Turing   -maskinen
• Toby Ord, De många formerna av   hyperberäkning
• Paolo Cotogno, Hypercomputation and  the Physical Church-Turing-uppsats