Hypercomputing

Der Begriff Hypercomputing bezieht sich auf die verschiedenen vorgeschlagenen Methoden zur Berechnung nicht berechenbarer Funktionen . Es wurde ursprünglich von Jack Copeland eingeführt . Der Begriff Super-Turing-Berechnung wird ebenfalls verwendet , obwohl der Begriff Hypercomputing mit der verführerischen Möglichkeit verbunden sein kann, dass eine solche Maschine physikalisch machbar ist. Einige Modelle wurden vorgeschlagen, wie beispielsweise neuronale Netze mit reellen Zahlen als Gewicht, die Fähigkeit, eine unendliche Anzahl von Berechnungen gleichzeitig durchzuführen, oder die Fähigkeit, nicht Turing-berechenbare Operationen wie Grenzen oder Integrationen durchzuführen.

Geschichte

Ein Modell, das leistungsfähiger als Turing-Maschinen ist, wurde 1939 von Alan Turing in seinem Artikel " Auf Ordnungszahlen basierende Logiksysteme " vorgestellt. Dieser Artikel untersuchte mathematische Systeme, in denen wir ein Orakel haben , das eine einzelne beliebige Funktion berechnen kann (nicht rekursiv). von natürlich zu natürlich. Er benutzte diese Maschine, um zu beweisen, dass selbst in diesen leistungsstärkeren Systemen Unentscheidbarkeit vorhanden ist. Dieser Text von Turing hob die Tatsache hervor, dass die Orakelmaschinen nur mathematische Abstraktionen waren und nicht physikalisch realisiert werden konnten.

Die Herausforderung des Hypercomputing

Die algorithmische Informationstheorie ermöglicht es uns heute, besser zu verstehen, was Hypercomputing erfordert. Das Kennzeichen eines Hypercomputers ist seine Fähigkeit, das Problem des Herunterfahrens für seine Programme zu lösen , zu denen ein gewöhnlicher Computer (eine Turing-Maschine) nicht in der Lage ist. Ein herkömmlicher Computer kann jedoch bestimmen, ob ein Programm stoppt oder nicht, wenn er die Zahl $\Omega$ kennt , bei der es sich um eine Zufallszahl handelt - und daher unendlich viele Informationen enthält . ist daher ein Orakel für das Problem des Herunterfahrens. Die Darstellung dieser Größe erfordert eine unendliche Folge von Bits, und es gibt kein Programm, um sie vollständig zu berechnen. Ein Hypercomputer sollte daher in der Lage sein, auf andere Weise als durch eine Berechnung im Sinne von Turing-Maschinen zu erhalten. $\Omega$ $\Omega$

Es gibt ein Approximationsverfahren für diskrete Computer (gewöhnliche Computer), das eine Approximation unter Verwendung eines einfachen Time-Sharing-Programms ermöglicht. Andererseits ist es nicht möglich zu wissen, wie nahe dieses Programm zu einem bestimmten Zeitpunkt an der Nummer liegt . $\Omega$ $\Omega$

Theoretische und konzeptionelle Möglichkeiten von Hypercomputern

Ein diskreter Computer mit Zugriff auf die Wahrscheinlichkeit des Herunterfahrens kann das Problem des Herunterfahrens lösen. Bei einem Eingabebitprogramm gibt das Lesen der ersten paar Bits der Nummer die Anzahl der Programme an , die zwischen den Programmen enden . Wir gehen dann wie folgt vor: Bei jedem Schritt werden die ersten Anweisungen jedes der Programme ausgeführt . Wir erhöhen auf diese Weise, bis die Programme beendet sind. Sie müssen nur überprüfen, ob das Eingabeprogramm Teil davon ist. $\Omega$ $nicht$ $nicht$ $\Omega$ $k$ $2 ^ {n}$ $ich$ $ich$ $2 ^ {n}$ $ich$ $k$
Eine Turing-Maschine, die einen Schritt der Unendlichkeit ausführen kann (siehe supertâche (en) ).
Ein realer Computer (eine Art idealer analoger Rechner ) könnte Hypercomputing durchführen, wenn die Physik reale Variablen im weiteren Sinne (nicht nur reale berechenbare Zahlen ) zulässt und auf irgendeine Weise gefunden wird, sie für die Berechnung zu domestizieren . Dies würde einige ziemlich verwirrende physikalische Gesetze erfordern (zum Beispiel eine messbare physikalische Konstante mit einem orakelhaften Wert wie die Chaitin-Konstante ) und würde erfordern, dass ein tatsächlicher physikalischer Wert trotz thermischem Rauschen und Rauschen mit beliebiger Genauigkeit gemessen werden kann. Quanteneffekte .
Ein quantenmechanisches System , das (zum Beispiel) eine unendliche Überlagerung von Zuständen verwendet, um eine nicht berechenbare Funktion zu berechnen . Ein solches System könnte kein gewöhnlicher Quantencomputer sein , da sich Quantencomputer als Turing-reduzierbar erwiesen haben (sie könnten Programme zur Lösung bestimmter Probleme beschleunigen, aber keine Lösung neuer Probleme ermöglichen).
Ein digitaler Computer in einer Raum-Zeit , genannt Raum-Zeit-Malament Hogarth (In) , könnte eine unendliche Anzahl von Operationen erreichen, während er im Lichtkegel eines bestimmten Ereignisses raumzeitlich bleibt .

Siehe auch

Anmerkungen

Jean-Paul Delahaye , Information, Komplexität und Zufall , Hermès [ Detail der Ausgabe ] , p. 87-88.
reicht nicht aus, nur endlose Schritte ausführen zu können (dh niemals anzuhalten). Auf der anderen Seite macht der Begriff der Berechnung am Limit den Trick. Betrachten Sie noch einmal das Verfahren zur Annäherung der Zahlen , das langsam und monoton konvergiert. Obwohl jeder Term in dieser Sequenz berechenbar ist, ist die Grenze nicht. Wenn ein Taschenrechner in der Lage wäre, alle diese Schritte zur Approximation unendlicher Zahlen auszuführen, seine unendlichen Ziffern abzurufen und zu speichern, könnte er das Stoppproblem leicht lösen. $\Omega$ $\Omega$ $\Omega$

Verweise

Alan Turing , Logiksysteme basierend auf Ordnungszahlen , Proc. Londoner Mathematik. Soc., 45 , 1939

Tien Kieu, Quantenalgorithmus für das zehnte Hilbert-Problem , Int. J. Theor. Phys., 42 (2003) 1461-1478, E-Print-Archiv quant-ph / 0110136 ( PDF )

Boris Tsirelson (en) , Der Quantenalgorithmus von Kieu löst das zehnte Problem von Hilbert nicht . E-Print-Archiv quant-ph / 0111009 ( PDF )

Tien Kieu, Antwort auf "Der Quantenalgorithmus von Kieu löst das zehnte Problem von Hilbert nicht" . E-Print-Archiv quant-ph / 0111020 ( PDF )

Hava Siegelman (en) , Neuronale Netze und analoge Berechnungen: Jenseits der Turing-Grenze Boston: Birkhäuser.

Hava Siegelmann, Die einfache Dynamik von Super-Turing-Theorien ; Theoretical Computer Science Volume 168, Ausgabe 2, 20. November 1996, Seiten 461-472. (Der Link führt zur Kopie der ScienceDirect-Website.)

Keith Douglas, Super-Turing-Berechnung: eine Fallstudienanalyse ( PDF ), MS-Arbeit, Carnegie Mellon University, 2003.

Lenore Blum , Felipe Cucker , Michael Shub , Stephen Smale , Komplexität und reelle Berechnung , Springer-Verlag 1997. Allgemeine Entwicklung der Komplexitätstheorie für abstrakte Maschinen, die auf reellen oder komplexen Zahlen anstelle von Bits rechnen.

Thomas Natschläger et al. der "Liquid Computer": Eine neuartige Strategie für Echtzeit-Computing in Zeitreihen

http://www.nature.com/nsu/010329/010329-8.html Ein Nature- Artikel zu den oben genannten Themen.

" Über die Rechenleistung neuronaler Netze " ( Archiv • Wikiwix • Archiv.is • Google • Was tun? )