Super-Turing Computing

Calculele Super-Turing (sau hipercalculările ( de exemplu hipercalcul )  ) sunt astfel de calcule care nu pot fi făcute pe o mașină Turing . Acestea includ o varietate de metode ipotetice bazate pe algoritmi superrecursivi , precum și alte tipuri de calcule - de exemplu, calcule interactive. . Termenul de hipercomputație a fost introdus pentru prima dată de Jack Copeland și Diana Proudfoot .  [1] Posibilitatea implementării fizice a unor astfel de calcule este discutată activ.

Istorie

Modele mai puternice decât o mașină Turing au fost introduse de Alan Turing în lucrarea sa din 1939 Systems of Logics Based on Ordinals . Această lucrare a explorat sisteme matematice care au un oracol care ar putea calcula o singură funcție arbitrară nerecursivă pe mulțimea numerelor naturale . El a folosit acest model pentru a arăta că, chiar și într-un sistem atât de puternic, există încă funcții necalculabile (de exemplu, problema opririi mașinii oracol). În lucrarea sa, Turing a arătat clar că un astfel de model nu este altceva decât o abstractizare matematică și nu poate fi implementat în lumea reală. [2]

Modalități preconizate de calcul super-Turing

• O mașină Turing care poate face un număr infinit de pași într-un timp finit (pur și simplu a putea rula o mașină Turing pentru un timp infinit (adică infinit potențial ) nu este suficientă). O modalitate pretinsă de a realiza acest lucru este utilizarea dilatației timpului pentru a permite computerului să finalizeze un număr infinit de cicluri într-un timp finit, conform ceasului observatorului extern (un astfel de calcul ar necesita energie infinită - vezi spațiu-timp Malamet-Hogarth ). Un alt mod, pur matematic, este așa-numita mașină Zeno , bazată pe paradoxul lui Zeno . Mașina Zeno își finalizează primul pas de calcul în timp, să zicem 1 minut, următorul în ½ minut, al treilea în ¼ minut și așa mai departe. Însumând această progresie geometrică infinită , obținem că mașina efectuează un număr infinit de pași în 2 minute. Cu toate acestea, conform unui raționament similar cu paradoxul clasic al lui Zenon, o astfel de mașină este imposibilă nu numai fizic, ci și logic. [3]

• O mașină Turing perpetuă este o generalizare a unei mașini Zeno care poate efectua un calcul lung nelimitat ai cărui pași sunt renumerotați de ordinale potențial transfinite . Modelează o mașină Turing altfel obișnuită, pentru care calculele fără oprire se termină prin atingerea unei stări speciale rezervate pentru atingerea ordinalului limită și pentru care sunt disponibile rezultatele tuturor calculelor infinite anterioare. [patru]
• Un computer real (o subspecie a computerului analogic idealizat ) poate fi capabil să efectueze hipercalcul [5] cu condiția ca fizica să permită existența unor numere reale reale . Acest lucru necesită probabil existența unor legi foarte ciudate ale fizicii (de exemplu, prezența unei constante fizice măsurabile care poate fi folosită ca un oracol - vezi, de exemplu, constanta lui Khaitin ) și ar trebui, cel puțin, să necesite capacitatea de a Măsurați constantele fizice cu o precizie arbitrară, în ciuda zgomotului termic și a efectelor mecanice cuantice .
• Sisteme mecanice cuantice , care folosesc cumva, de exemplu, o suprapunere infinită de stări pentru a calcula funcții necalculabile. [6] Acest lucru nu este posibil folosind un computer cuantic standard , deoarece s-a dovedit că un computer cuantic obișnuit este reducabil prin PSPACE (un computer cuantic care rulează timp polinomial poate fi simulat pe un computer clasic folosind spațiu polinomial ). [7]
• O tehnică cunoscută sub numele de determinism nerestricționat poate permite evaluarea funcțiilor necalculabile. Această problemă este subiectul dezbaterii în literatură.
• Utilizarea curbelor închise asemănătoare timpului , contrar credinței populare, nu permite efectuarea de calcule super-Turing, deoarece nu există o cantitate infinită de memorie.
• La începutul anilor 1990, Chava Siegelmann [8] a propus un model bazat pe evoluția infinită a rețelelor neuronale capabile de hipercalculatură. [9]
• Sub ipotezele unui univers newtonian continuu (când timpul și spațiul sunt infinit divizibile), este posibil să se construiască un lanț de module de calcul , fiecare dintre ele fiind de 2 ori mai mic și de 2 ori mai rapid decât precedentul [10] . În acest caz, nu este nevoie să se recurgă la mase, forțe, viteze nelimitate, deoarece o dimensiune mai mică implică în mod evident o capacitate de calcul mai rapidă la o viteză fizică fixă ​​a procesului, . Mașina are memorie infinită, chiar dacă fiecare modul are doar memorie finită, deoarece există infinit de module. În plus, mașina este capabilă să efectueze un număr infinit de operații într-un timp finit, ca și mașina Zeno, deoarece operațiile următorului modul sunt finalizate în timp de 2 ori mai puțin decât cel anterior și obținem o progresie geometrică convergentă. a intervalelor de timp. Diferența esențială dintre mașina Zeno și mașină este că nu poate funcționa cu celula de memorie finită alocată de un număr infinit de ori într-un timp finit. Acest lucru eliberează de așa-numitul paradox al lui Thomson [11] , a cărui esență este imprevizibilitatea rezultatului final al execuției unei succesiuni infinite de scriere alternativă 0,1,0,1,... într-o celulă de memorie fixă. .

Vezi și

• teza Church-Turing
• Oracle (computer)
• Mașină Zeno
• Tehnica de calcul
• Paradoxul lui Zenon

Note

1. ↑ Ideile uitate ale lui Alan Turing în informatică Arhivat 11 noiembrie 2013 la Wayback Machine . Scientific American , aprilie 1999.
2. ↑ „Să presupunem că avem o modalitate de a rezolva probleme în teoria numerelor, un oracol care dă soluții la astfel de probleme. Nu trebuie să mergem mai departe în natura oracolului, cu excepția faptului că nu poate fi o mașină.” (Undecidable p. 167, o retipărire a lucrării lui Turing Systems of Logic Based On Ordinals )
3. ↑ Vezi de exemplu Shagrir, O. Super-tasks, accelerating Turing machines and uncomputability  //  Theor. Calculator. sci. 317, 1-3: jurnal. - 2004. - iunie ( vol. 317 ). - P. 105-114 . - doi : 10.1016/j.tcs.2003.12.007 . Arhivat din original pe 21 iulie 2011.
4. ↑ Joel David Hemkins și Andy Lewis, Infinite time Turing machines Arhivat 5 octombrie 2011. , Journal of Symbolic Logic , 65(2):567-604, 2000.
5. ↑ Arnold Schönhage, „Despre puterea mașinilor cu acces aleatoriu”, în Proc. Intl. Colocvium on Automata, Languages, and Programming (ICALP), paginile 520-529, 1979. Sursa de citare: Scott Aaronson , „NP-complete Problems and Physical Reality” Arhivat la 15 ianuarie 2010, la Wayback Machine p. 12
6. ↑ Există pretenții în favoarea acestui lucru; vezi de exemplu Tien Kieu. Algoritmul cuantic pentru a zecea problemă a lui Hilbert   // Int . J. Theor. Fiz. : jurnal. - 2003. - Vol. 42 . - P. 1461-1478 . - doi : 10.1023/A:1025780028846 . iar literatura citată acolo. Erorile în abordarea lui Kieu au fost subliniate de Warren D. Smith în Trei contraexemple care resping planul lui Kieu pentru „hipercalcul adiabatic cuantic”; și câteva sarcini de mecanică cuantică necalculabile Arhivat 6 martie 2010 la Wayback Machine
7. ↑ Bernstein și Vazirani, Teoria complexității cuantice Arhivat la 11 martie 2016 la Wayback Machine , SIAM Journal on Computing, 26(5):1411-1473, 1997.
8. ↑ : BINDS lab : HAVA'S BIO : . Preluat la 7 iunie 2011. Arhivat din original la 4 octombrie 2011. (nedefinit)
9. ↑ Verificarea proprietăților rețelelor neuronale Arhivat 4 martie 2016 la Wayback Machine p.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.

Literatură

• Martin Davis, De ce nu există o astfel de disciplină precum hipercalculația , Matematică aplicată și calcul, volumul 178, numărul 1, 1 iulie 2006, paginile 4-7, numărul special privind hipercalcularea
• Mike Stannett, The case for hypercomputation Arhivat la 4 martie 2016 la Wayback Machine , Applied Mathematics and Computation, Volumul 178, Numărul 1, 1 iulie 2006, Paginile 8-24, Numărul special privind hipercalcularea
• Alan Turing, Sisteme de logică bazate pe ordinale , Proc. matematica londoneză. soc., 45 , 1939
• Hava Siegelmann. Rețele neuronale și calcul analogic: dincolo de limita Turing Boston: Birkhäuser.
• Hava Siegelmann. Dinamica simplă a teoriilor super Turing ; Teoretică Informatică Volumul 168, Numărul 2, 20 noiembrie 1996, Paginile 461-472.
• Keith Douglas. Calcul Super-Turing: o analiză de studiu de caz ( PDF ), teză de master, Universitatea Carnegie Mellon, 2003.
• L. Blum, F. Cucker, M. Shub, S. Smale, Complexity and Real Computation , Springer-Verlag 1997. Dezvoltarea generală a teoriei complexității pentru mașini abstracte care calculează pe numere reale în loc de biți.
• Despre puterea de calcul a rețelelor neuronale  (link indisponibil)
• Toby Ord. Hypercomputation: calculează mai mult decât poate calcula mașina Turing : un articol de studiu despre diferite forme de hipercalculare.
• 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, pp. 1289-1293
• Mark Burgin (2005), Algoritmi super-recursivi , Monografii în informatică, Springer. ISBN 0-387-95569-0
• Cockshott, P. și Michaelson, G. Există noi modele de calcul? Răspuns la Wegner și Eberbach, The computer Journal , 2007
• Copeland, J. (2002) Hypercomputation , Minds and machines, v. 12, pp. 461-502
• Martin Davis (2006), „ Teza Church-Turing: Consens și opoziție ”. Proceedings, Computability in Europe 2006. Note de curs în informatică, 3988 p. 125-132
• Hagar, A. și Korolev, A. (2007) Quantum Hypercomputation - Hype or Computation? http://philsci-archive.pitt.edu/archive/00003180/
• Rogers, H. (1987) Theory of Recursive Functions and Effective Computability, MIT Press, Cambridge Massachusetts

Link -uri

•  Rețeaua de cercetare a hipercalculației
• Toby Ord, Hypercomputation: calculul mai mult decât   mașina Turing
• Toby Ord, Multe forme de   hipercalculație
• Paolo Cotogno, Hypercomputation and  the Physical Church-Turing teza