Hipercomputere

Termenul de hipercomputare desemnează diferitele metode propuse pentru calcularea funcțiilor care nu pot fi calculate . A fost introdus inițial de Jack Copeland . Se folosește și termenul de calcul super-Turing , deși termenul de hipercomputare poate fi conotat de posibilitatea atrăgătoare că o astfel de mașină este fezabilă din punct de vedere fizic. Au fost propuse unele modele, cum ar fi rețelele neuronale cu numere reale ca pondere, capacitatea de a efectua simultan un număr infinit de calcule sau capacitatea de a efectua operații care nu pot fi calculate de Turing, precum limite sau integrări.

Istorie

Un model mai puternic decât mașinile Turing a fost introdus de Alan Turing în articolul său „ Sisteme de logică bazate pe ordinali ” în 1939. Acest articol a examinat sistemele matematice în care avem un oracol capabil să calculeze o singură funcție arbitrară. (Non-recursiv) de la natural la natural. El a folosit această mașină pentru a demonstra că chiar și în aceste sisteme mai puternice este prezentă indecidabilitatea . Acest text al lui Turing a evidențiat faptul că mașinile oraculare erau doar abstracții matematice și nu puteau fi realizate fizic.

Provocarea hipercomputării

Astăzi, teoria informației algoritmice ne permite să înțelegem mai bine ce necesită hipercomputarea. Semnul distinctiv al unui hipercomputer este abilitatea sa de a rezolva problema de închidere , pentru programele sale de ceea ce este incapabil un computer obișnuit (o mașină Turing). Cu toate acestea, un computer convențional poate determina dacă vreun program se oprește dacă știe numărul $\Omega$ , care este un număr aleatoriu - și, prin urmare, conține informații infinite. este, prin urmare, un oracol pentru problema închiderii. Reprezentarea acestei mărimi necesită o secvență infinită de biți și nu există un program care să o calculeze exhaustiv. Astfel, un hipercomputer ar trebui să poată obține prin alte mijloace decât printr-un calcul în sensul mașinilor Turing. $\Omega$ $\Omega$

Există o procedură de aproximare pentru calculatoare discrete (calculatoare obișnuite) care permite aproximarea utilizând un program simplu de partajare a timpului. Pe de altă parte, nu este posibil să știm cât de aproape este acest program de numărul la un moment dat. $\Omega$ $\Omega$

Posibilități teoretice și conceptuale ale hipercomputerelor

Un computer discret cu acces la probabilitatea de oprire poate rezolva problema opririi. Pentru un program de biți de intrare, citirea primilor biți ai numărului dă numărul de programe care se termină printre programe. Apoi procedăm după cum urmează: la fiecare pas sunt executate primele instrucțiuni ale fiecărui program. Creștem în acest mod până când programele au terminat. Trebuie doar să verificați dacă programul de intrare face parte din el. $\Omega$ $nu$ $nu$ $\Omega$ $k$ $2 ^ {n}$ $eu$ $eu$ $2 ^ {n}$ $eu$ $k$
O mașină Turing capabilă să efectueze un pas de infinit (vezi supertâche (en) ).
Un computer real (un fel de calculator analogic ideal) ar putea efectua hipercomputarea dacă fizica ar permite variabile reale în sens larg (nu doar numere reale calculabile ) și s-a găsit o modalitate de domesticire a acestora pentru calcul. Acest lucru ar necesita unele legi fizice destul de confuze (de exemplu, o constantă fizică măsurabilă cu o valoare oraculară, cum ar fi constanta Chaitin ) și ar necesita posibilitatea de a măsura o valoare fizică reală cu precizie arbitrară în ciuda zgomotului termic și a zgomotului.efecte cuantice .
Un sistem mecanic cuantic care folosește (de exemplu) o suprapunere infinită de stări pentru a calcula o funcție necomputabilă . Un astfel de sistem nu ar putea fi un computer cuantic obișnuit, deoarece computerele cuantice s-au dovedit a fi reductibile Turing (ar putea accelera programele rezolvând anumite probleme, dar nu ar permite rezolvarea unor noi probleme).
Un computer digital situat într-un spațiu-timp , numit spațiu-timp-Malament Hogarth (In) , ar putea realiza un număr infinit de operații rămânând în același timp în conul de lumină al unui anumit eveniment spatiotemporal.

Vezi și tu

Note

Jean-Paul Delahaye , Informații, complexitate și întâmplare , Hermès [ detaliul ediției ] , p. 87-88.
Pur și simplu nu puteți ajunge să efectuați pași interminabili (adică să nu vă opriți niciodată). Pe de altă parte, noțiunea de calcul la limită face truc. Luați în considerare din nou procedura de aproximare a numărului , care converge încet și monoton. Deși fiecare termen din această secvență este calculabil, limita nu este. Dacă un calculator ar fi capabil să facă toți acești pași de aproximare a numărului infinit, să obțină și să stocheze infinitatea sa de cifre, ar putea rezolva cu ușurință problema opririi. $\Omega$ $\Omega$ $\Omega$

Referințe

Alan Turing , Sisteme de logică bazate pe ordinali , Proc. Matematica londoneză. soc., 45 , 1939

Tien Kieu, Algoritmul cuantic pentru a zecea problemă a lui Hilbert , Int. J. Teoretic. Phys., 42 (2003) 1461-1478, e-print archive quant-ph / 0110136 ( PDF )

Boris Tsirelson (ro) , Algoritmul cuantic al lui Kieu nu rezolvă a zecea problemă a lui Hilbert . arhiva e-print quant-ph / 0111009 ( PDF )

Tien Kieu, Răspuns la „Algoritmul cuantic al lui Kieu nu rezolvă a zecea problemă a lui Hilbert” . arhiva e-print quant-ph / 0111020 ( PDF )

Hava Siegelman (ro) , Neural Networks and Analog Computation: Beyond the Turing Limit Boston: Birkhäuser.

Hava Siegelmann, Dinamica simplă a teoriilor super Turing ; Theoretical Computer Science Volumul 168, Ediția 2, 20 noiembrie 1996, paginile 461-472. (linkul este către copia site-ului ScienceDirect)

Keith Douglas, Super-Turing Computation: a Case Study Analysis ( PDF ), MS Thesis, Universitatea Carnegie Mellon, 2003.

Lenore Blum , Felipe Cucker , Michael Shub , Stephen Smale , Complexity and Real Computation , Springer-Verlag 1997. Dezvoltarea generală a teoriei complexității pentru mașini abstracte care calculează pe numere reale sau complexe în loc de biți.

Thomas Natschläger și colab. „Calculatorul lichid”: o strategie nouă pentru calculul în timp real pe seriile de timp

http://www.nature.com/nsu/010329/010329-8.html Un articol Nature despre cele de mai sus.

„ Despre puterea de calcul a rețelelor neuronale ” ( Arhivă • Wikiwix • Archive.is • Google • Ce să faci? )