Hiperračunanje

Hiperračunanje ili super-Tjuringovo računanje se odnosi na modele računanja koji prevazilaze Tjuringovu izračunljivost. Ovo uključuje različite hipotetičke metode za izračunavanje ne-Tjuringove-izračunljive funkcije.

Termin " super-Tjuringovo računanje" pojavio se početkom 1990-ih, sa najmanje dva nezavisna izvora navedena u literaturi. Pojavio se u razgovorima, PhD teze, pa čak i raniji tehnički izveštaji Have Sigelmana od ranih 1990-ih za veoma posebnu teoriju (opisanu u nastavku) i postao je podoblast izračunavanja od njenog naučnog papira 1995. Takođe se pojavio 1990. u razgovoru  i 1991. u tehničkom izveštaju  Majka Steneta, koji je takođe objavio teorijsku diskusiju jedne X-mašine bazirane na "super-Tjuringovoj mašini" u martu 1990.

Termin "hiperračunanje" uveden je u 1999. od strane Džeka Koplenda i Dajane Praudfut.

Uslovi nisu baš sinonimi: "super-Tjuringovo izračunavanje" od Sigelmana obično podrazumeva da će predloženi model verovatno postojati u prirodi (preko biologije i / ili fizike) i stoga može da bude fizički ostvariv, dok "hiperračunanje" može biti opšta matematička ili filozofska ideja.

Istorija

Matematički model koji ide preko Tjuringovih mašina je uveo Alan Tjuring 1938. u svojoj doktorskoj disertaciji Sistemi logike bazirani na ordinalima. Ovaj rad je istraživao matematičke sisteme u kojima je proročka mašina bila dostupna, što bi moglo da izračuna jednu proizvoljnu (ne) rekurzivnu funkciju iz prirodnih brojeva u prirodne brojeve. On je koristio ovaj uređaj da dokaže da čak i u onim moćnijim sistemima, neodlučiv zadatak je i dalje prisutan. Tjuringove proročke mašine su matematičke apstrakcije, a nisu fizički ostvarive.

Hiperračunanje i Čerč–Tjuringova teza

Čerč–Tjuringova teza navodi da se svaka algoritmički izračunljiva funkcija može izračunati pomoću Tjuringove mašine. Superkompjuteri računaju funkcije koje Tjuringova mašina ne može i koji su, stoga, neizračunljivi u Čerč-Tjuringovom smislu.

Primer problema koji Tjuringova mašina ne može da reši jeste Halting problem. Tjuringova mašina ne može da odluči da li se proizvoljan program zaustavlja ili radi zauvek. Neki predlažu da bi superkompjuteri mogli da simuliraju program sa beskonačnim brojem koraka i da ukažu korisniku da li je program zaustavljen. Posebno, Sigelman je pokazala u svojoj doktorskoj disertaciji 1993, i kasnije u svojoj knjizi 1998, da Halting problem Tjuringovih mašina može da se reši sa analognim periodičnim neuronskim mrežama.

Super-Tjuringovo računanje i super-Tjuringova teza

U ranim 1990-im Hava Sigelman i Eduardo Sontag su dokazali da je njihov novi kompjuterski model, Veštačka Rekurentna Prirodna Mreža (ARNN), mogla da obavlja izvan Tjuringove granice (hiperračunanje)

Sigelman i njene kolege su otkrili hijerarhiju dobro utvrđenih računarskih klasa koje počinju od Tjuringove mašine i uzdižu se do pune super Tjuringove snage  Sigelman je opisala u raznim publikacijama koje postoje mnogo načini da se dođe do super-Tjuringovog računanja. Dok je prvo pokazala postojanje super-Tjuringovog računanja preko analogne neuronske mreže sa fiksnom (ne za učenje) i neograničenom težinom, otišla je da dokazuje super-Tjuringovu snagu u mnogim različitim ostvarivim mašinama uključujući i male precizne težine neuronske mreže koje primaju svoju moć od: učenja u analognom domenu, ili koristeći stokastiku, ili razvijanje tokom vremena, ili korišćenje podataka iz okruženja, ili sistema koji su Tjuringovi u bilo kojim izračunljivim koracima i između promena na jednu od navedenih metoda. Vidi još rad u Verifikaciji svojstava neuronskih mreža.

Sigelmanin naučni rad pokazuje prvi korak oslobađanja ovog računanja dok sadašnji napori postoje od strane fizičara i inženjera u izgradnji takvih sistema. Sigelmanino nedavno istraživanje dokazuje da je stanje prostora super-Tjuringovog računanja $2^{\aleph _{0}}$ a prostor Tjuringovih mašina samo $\aleph _{0}$, što daje novo shvatanje da je Tjuringov test - kao razdvajanje prostora različitih veličina. 

Teorija je dovela do boljeg razumevanja neuronske mreže (Fondacija dubokog učenja) i podržanih inovativnih aplikacija u tako osetljivim oblastima kao što su registracije radara i kontrola nuklearnih elektrana. Sigelman i njene kolege su otišle dalje da stvore teoriju složenosti za kontinuirano vreme i fizičke sisteme. Kao konkretan primer Sigelmanova grupa je analizirala linearno programiranje i druge kompjutersko naučne probleme koji pokazuju da analogni računari mogu da reše brže od diskretnih vremenskih računara. 

Nedavna publikacija otkriva da je Alan Tjuring bio u potrazi za super-Tjuringovim izračunavanjem zasnovanim na principima mozga, i pokazao svoje predložene pravce kako se traže da se savršeno slažu sa Sigelmanim teorijama.  Sigelman i Sontag su predložili novu računarsku hipotezu - dok analogno, učenje, i evoluirajući sistemi su bili ograničeni super-Tjuringovom računskom snagom.

Ostali predlozi super-računara

• Tjuringova mašina koja može da završi beskonačno mnogo koraka. Jednostavno biti u stanju da radi za neograničen broj koraka nije dovoljno. Jedan matematički model je Zenonova mašina (inspirisano Zenonovim paradoksima). Zenonova mašina obavlja svoj prvi korak u izračunavanju (recimo) 1 minut, drugi korak u ½ minut, treći korak u ¼ minut, itd Sumirajući 1+½+¼+... (geometrijska serija) vidimo da mašina obavlja beskonačno mnogo koraka u ukupno 2 minuta. Prema Šagriru, Zenonove mašine uvode fizičke paradokse, a njihovo stanje je logično definisano van jedne strane otvorenog perioda [0, 2), tako nedefinisana tačno u 2 minuta posle početka računanja.
• Tjuringova originalna Proročka mašina, definisana od strane Tjurninga 1939.
• Sredinom 1960-ih, E Mark Gold i Hilari Patnam nezavisno su predložili modele induktivnog zaključivanja (na "ograničavanje rekurzivnih funkcionalnosti" i "suđenje i greške predikata", ). Ovi modeli omogućavaju nekim nerekurzivnim skupovima brojeva ili jezika (uključujući sve rekurzivno brojive skupove jezika) da se "nauče u roku"; dok, po definiciji, samo rekurzivni skupovi brojeva ili jezika mogu se prepoznati po Tjuringovoj mašini. Dok će se mašina stabilizovati na tačan odgovor na bilo kom naučenom skupu u nekom konačnom vremenu, to samo može da se identifikuje kao tačno da je rekurzivna; u suprotnom, korektnost je osnovana samo kada mašina radi zauvek i ističući da nikada revidira svoj odgovor. Patnam je identifikovao ovu novu interpretaciju kao klasu "empirijskog" predikata, navodeći: "ako smo uvek" pretpostavka "generisali odgovor da je tačan, napravićemo konačan broj grešaka, ali ćemo na kraju dobiti tačan odgovor. (Napomena, međutim, da čak i ako smo stigli do tačnog odgovora (na kraju konačnog niza) nismo sigurni da imamo tačan odgovor.)" L. K. Šubertov papir 1974. "Iterativno ograničenje rekurzije i program problema minimiziranja" proučavao efekte iterativnog postupka ograničavanja; ovo omogućava svakom aritmetičkom predikatu da se izračuna. Šubert je napisao: "Intuitivno, iterativna ograničavajuća identifikacija može se smatrati višim redom induktivnog zaključka koji se izvodi kolektivno od strane sve veće zajednice nižeg reda induktivnih zaključaka mašina."
• Pravi kompjuter (neka vrsta idealizovanog analognog računara) može obavljati hiperračunanje  ako fizika priznaje opšte realne promenljive (ne samo za izračunavanje realnih brojeva), a to su na neki način "upregnute" za obračun. Ovo može zahtevati dosta bizarnih zakona fizike (na primer, merljiva fizička konstanta sa proročkom vrednošću, kao što su Čejtinova konstanta), te bi u najmanju ruku zahtevala sposobnost da izmeri stvarnu-vrednosti fizičke vrednost proizvoljne preciznosti i pored toplotne buke i kvantnih efekata.
• Predložena tehnika poznata kao fer nedeterminisana ili neograničena nedeterminisana može dozvoliti izračunavanja neizračunljivih funkcija. Postoji spor u literaturi oko toga da li je ova tehnika koherentna, i da li zaista dozvoljava neizračunljivim funkcijama da budu "izračunljive".
• Čini se da je prirodna mogućnost putovanja kroz vreme (postojanje zatvorenih vremenskih krivih (CTCs) čini hiperračunanje moguće samo po sebi. Međutim, to nije tako pošto CTC ne daje (po sebi) neograničenu količinu skladišnog kapaciteta koja bi beskonačno računanje zahtevala. Ipak, postoje vreme i prostor u kojima se CTC region može koristiti za relativističko hiperračunanje. Pristup CTC može dozvoliti brzo rešenje PSPACE-kompletnih problema, kompleksnost klase koja, dok je Tjuring-odlučiv, se generalno smatra računski složenim.
• Prema 1992 papiru, računar koji radi na Malament-Hogart prostoru i vremenu ili u orbiti oko rotirajuće crne rupe  teoretski se može obavljati bez Tjuringovog izračunavanja.
• Beskonačno vreme Tjuringove mašine je generalizacija Zenonove mašine, koja može obavljati beskrajno duge proračune čiji koraci su nabrojani potencijalno transfinitnim rednim brojevima. Njeni modeli inače obične-Tjuringove mašine zbog kojih su nezaustavljanje izračunavanja završeni unosom posebnog stanja rezervisanog za postizanje limita rednog broja i kojima su rezultati prethodno beskonačnog izračunavanja dostupni.
• Jan van Leuven i Jiri Viderman su napisali papir  sugerišući da internet treba da bude modeliran kao jedinstven nekompjuterisan sistem opremljen savetima funkcija koje predstavljaju sposobnost računara da se nadogradi.
• Simbol sekvence je izračunljiv u roku ako postoji konačan, verovatno nezaustavljiv program na univerzalnoj Tjuringovoj mašini koja postepeno izbacuje svaki simbol sekvence. Ovo uključuje diadično širenje π i svaki drugi izračunljiv realan broj, ali ipak isključuje sve neizračunljive. Tradicionalna Tjuringova mašina ne može da menja svoje ranije izlaze; generalizovana Tjuringova mašina, kao što je definisao Jirgen Šmidhuber, može. On je konstruktivno opisao simbole sekvence kao one koje imaju konačan, nezaustavljiv program koji radi na generalizovanoj Tjuringovoj mašini, tako da svaki izlaz simbola na kraju konvergira; to jest, ne menja ništa više posle nekog konačnog početnog vremenskog intervala. Zbog ograničenja prvi je izložio Kurt Gedel (1931), da može biti nemoguće predvideti samo vreme konvergencije od zaustavljanja programa, inače zaustavljanje problema bi moglo biti rešeno. Šmidhuber () koristi ovaj pristup da definiše skup formalno opisivih ili konstruktivno izračunljivih univerzuma ili konstruktivne teorije svega. Generalizovane Tjuringove mašine mogu da reše problem obustave procenom Spiker sekvence.
• Kvantnomehanički sistem koji na neki način koristi beskonačno superpozicija stanja da izračuna ne-izračunljivu funkciju. To nije moguće koristeći standardni kjubit-model kvantnog kompjutera, jer je dokazano da redovni kvantni kompjuter PSPACE-umanjen (kvantni kompjuter koji radi u polinomijalnom vremenu može da simulira klasični kompjuter koji radi u prostoru polinoma).
• 1970, E. S. Santos definisao je klasu rasplinute logike zasnovane na "nejasnom algoritmu" i "fazi Tjuringove mašine". Nakon toga, L. Biaćino i G. Gerla su pokazali da bi takva definicija omogućavala proračun nerekurzivnih jezika; oni su predložili alternativni skup definicija bez ove teškoće. Jiri Viderman je analizirao mogućnosti Santosovog prvobitnog predloga 2004. godine. 
• Dmitro Taranovski je predložio finitistički model tradicionalne nefinitističke grane analize, izgrađen oko Tjuringove mašine opremljen brzo rastućom funkcijom kao svoje proročište. Ovaj i komplikovaniji modeli su bili je u stanju da daju tumačenje drugog reda aritmetike.

Analiza mogućnosti

Mnogi predlozi hiperračunanja iznose alternativnim načinima da pročitate Proročku mašinu ili savet funkcije ugrađene u inače klasične mašine. Drugi omogućen pristup je moguć nekom višem nivou aritmetičke hijerarhije. Na primer, supertasking Tjuringove mašine, pod uobičajenim pretpostavkama, da je u stanju da izračuna bilo koji predikat u stepenu istinitosne tabele koja sadrži $\Sigma _{1}^{0}$ ili $\Pi _{1}^{0}$. Rekurzivno-ograničavanje, s druge strane, može da izračuna bilo koji predikat ili funkciju u odgovarajućoj meri stepena Tjuringa, koji je poznat da bude $\Delta _{2}^{0}$. Dosta dalje je pokazano da ograničavanje delimične rekurziju omogućava proračun upravo $\Sigma _{2}^{0}$predikatima.

Model	Izračunljivi predikati	Beleške	Reference
supertasking	tt($\Sigma _{1}^{0},\Pi _{1}^{0}$)	zavisnost na spoljašnjem posmatraču
Ograničavanje / proba i greške	$\Delta _{2}^{0}$
iterativno limitiranje (k puta)	$\Delta _{k+1}^{0}$
Blum-Shub-Smale mašina		neuporediv sa tradicionalnim izračunljivim realnim funkcijama
Malament-Hogart prostor-vreme	HT	zavisnost na prostornovremenskoj strukturi
analogno povratna neuronska mreže	$\Delta _{1}^{0}[f]$	f je savet funkcija davanje težina veze; veličina je ograničena rantajmom
beskonačno vreme Tjuringove mašine	$\geq T(\Sigma _{1}^{1})$
klasična faza Tjuringove mašine	$\Sigma _{1}^{0}\cup \Pi _{1}^{0}$	za bilo koju računljivu t-normu
rastuća funkcija Proročke mašine	$\Delta _{1}^{1}$	za jednosekventni model; $\Pi _{1}^{1}$ su r.e.

Taksonomija "super-rekurzivne" metodologije računanja

Mark Burgin je prikupio spisak onoga što on naziva "super-rekurzivni algoritmi" (od Burgina 2005: 132):

• ograničavanje rekurzivne funkcije i ograničavanje parcijalne rekurzivne funkcije (E. M. Gold)
• proba i greške predikata (Hilari Patnam )
• induktivno zaključivanje mašina  (Karl Herbert Smit)
• induktivne Tjuringove mašine (jedan od Burginovih modela)
• ograničavanje Tjuringovih mašina (jedan od drugih Burginovih modela)
• proba i greške mašina (Ja. Hintika i A. Mutanen )
• generalne Tjuringove mašine (J. Šmidhuber)
• Internet mašine (Jan van Leuven i Viderman,J.)
• evolucionarni računari, koje koriste DNK da proizvedu vrednost funkcije (Darko Roglić )
• fazni proračun (Jiri Viderman )
• evolucionarne Tjuringove mašine (Eugen Eberbah )

U istoj knjizi, on takođe predstavlja spisak "algoritamskih šema":

• Tjuringove mašine sa proizvoljnim Proročkim mašinama (Alan Tjuring)
• transrekurzivni operatori (Borodianski i Burgin )
• mašine koje računaju sa realnim brojevima (L. Blum, F Cucker M. Šub, S. Smejl)
• Statičke neuronske mreže zasnovane na stvarnim težinama ili ekvivalentno "Neuronske mreže konačne precizne težine, ali sa asinhronim ažuriranjem, stohastičke medalje, razvijanje ili učenje (težine i / ili struktura). (Hava Sigelman)

Kritika

Martin Dejvis, u svojim spisima o hiperračunanju  odnosi se na ovoj temi kao "mit" i nudi kontra-argumente za fizički ostvarivostima hiperračunanja. Što se tiče njegove teorije, tvrdi da je ovo novo polje osnovano 1990. godine. Ova tačka gledišta se oslanja na istoriju teorije izračunljivosti (stepeni nerešivosti, izračunljivost nad funkcijama, realnih brojeva i rednih brojeva), kao i gore navedeno. U svom argumentu on pravi primedbu da je sve trivijalno kao: "Ako je neizračunljivim ulazima dozvoljeno onda su neizračunljivi rezultati dostižni". Široko je prihvaćeno da se ova kritika odnosi na najranije matematičke i filozofske sugestije i ignoriše mnoge od novijih predloga koji nisu predmet kritike.

Endru Hodžes je napisao kritički komentar  na Kouplend i Praudfut članku.

Vidi još

• Računanje
• Digitalna fizika
• Super-zadatak

Literatura

• Stannett, Mike (1990). „X-machines and the halting problem: Building a super-turing machine”. Formal Aspects of Computing. 2 (1): 331—341. S2CID 7406983. doi:10.1007/BF01888233. 
• Turing, A. M. (1939). „Systems of Logic Based on Ordinals^†”. Proceedings of the London Mathematical Society: 161—228. doi:10.1112/plms/s2-45.1.161. hdl:21.11116/0000-0001-91CE-3. 
• Mike Stannett, The case for hypercomputation Arhivirano na sajtu Wayback Machine (4. mart 2016). Applied Mathematics and Computation. 178 (1): 1.  July 2006, Pages 8–24, Special Issue on Hypercomputation
• Keith Douglas. Super-Turing Computation: a Case Study Analysis (PDF), M.S. Thesis, Carnegie Mellon University, 2003.
• L. Blum, F. Cucker, M. Shub, S. Smale, Complexity and Real Computation, Springer-Verlag 1997. General development of complexity theory for abstract machines that compute on real numbers instead of bits.
• Ord, Toby (2002). „Hypercomputation: Computing more than the Turing machine can compute”. arXiv:math/0209332 . 
• Syropoulos, Apostolos (2008). Hypercomputation: Computing Beyond the Church-Turing Barrier. Springer Science & Business Media. ISBN 978-0-387-49970-3. 
• Burgin, M. S. (1983) Inductive Turing Machines, Notices of the Academy of Sciences of the USSR, v. 270, No. 6. str. 1289–1293
• Burgin, Mark (2005). Super-recursive algorithms. Springer. ISBN 978-0-387-95569-8. 
• Cockshott, P. and Michaelson, G. Are there new Models of Computation? Reply to Wegner and Eberbach, The computer Journal, 2007
• Cooper, S. Barry (2006). „Definability as hypercomputational effect”. Applied Mathematics and Computation. 178: 72—82. S2CID 1487739. doi:10.1016/j.amc.2005.09.072. 
• Cooper, S. B.; Odifreddi, P. (2003). "Incomputability in Nature". In S. B. Cooper and S. S. Goncharov. Computability and Models: Perspectives East and West (PDF). Plenum Publishers, New York, Boston, Dordrecht, London, Moscow. str. 137–160.
• Copeland, J. (2002). Hypercomputation (PDF). Minds and machines, v. Arhivirano iz originala (PDF) 14. 03. 2016. g. Pristupljeno 15. 01. 2016.  12. str. 461–502..
• Martin Davis (2006), "The Church–Turing Thesis: Consensus and opposition". Proceedings, Computability in Europe 2006. The requested URL /~simon/TEACH/28000/DavisUniversal.pdf was not found on this server. Lecture notes in computer science, 3988 pp. 125–132
• Hagar, A. and Korolev, A., Quantum Hypercomputation—Hype or Computation?, (2007)
• Rogers, H. (1987) Theory of Recursive Functions and Effective Computability, MIT Press, Cambridge Massachusetts
• Putz, Volkmar; Svozil, Karl (2010). „Can a computer be "pushed" to perform faster-than-light?”. arXiv:1003.1238 . 

Dodatna literatura

• Ord, Toby (2002). „Hypercomputation: computing more than the Turing machine”. arXiv:math/0209332 . 

Spoljašnje veze

• Hypercomputation Research Network
• Hypercomputation
• Toby Ord, The many forms of hypercomputation
• Paolo Cotogno, Hypercomputation and the Physical Church-Turing thesis
• Gualtiero Piccinini, Computation in Physical Systems
• H.T. Siegelmann's publications page at University of Massachusetts Amherst