Hyperberechnung oder super-Turing Berechnung beziehen sich auf Modelle der Berechnung, die übertreffen, oder zu, Berechenbarkeit von Turing unvergleichbar sind. Das schließt verschiedene hypothetische Methoden für die Berechnung von Non-Turing-Computable-Funktionen im Anschluss an superrekursive Algorithmen ein (sieh auch Superaufgabe). Der Begriff "super-Turing Berechnung" ist in einem 1995-Wissenschaftsvortrag von Hava Siegelmann erschienen. Der Begriff "Hyperberechnung" wurde 1999 von Jack Copeland und Diane Proudfoot eingeführt.

Die Begriffe sind nicht ziemlich synonymisch: "Super-Turing-Berechnung" deutet gewöhnlich an, dass das vorgeschlagene Modell physisch realisierbar sein soll, während "Hyperberechnung" nicht tut.

Technische Argumente gegen die physische Durchführbarkeit der Hyperberechnung sind präsentiert worden.

Geschichte

Ein rechenbetontes Modell, das Maschinen von Turing übertrifft, wurde von Alan Turing in seinen 1938 Doktordoktorarbeit-Systemen der auf Ordnungszahlen Basierten Logik eingeführt. Dieses Papier hat mathematische Systeme untersucht, in denen ein Orakel verfügbar war, der eine einzelne willkürliche (nichtrekursive) Funktion von naturals bis naturals schätzen konnte. Er hat dieses Gerät verwendet, um zu beweisen, dass sogar in jenen stärkeren Systemen Unentscheidbarkeit noch da ist. Die Orakel-Maschinen von Turing sind ausschließlich mathematische Abstraktionen und sind nicht physisch realisierbar.

Hyperberechnung und die Kirch-Turing-These

Die Kirch-Turing-These stellt fest, dass jede Funktion, die algorithmisch berechenbar ist, durch eine Maschine von Turing geschätzt werden kann. Hypercomputer schätzen Funktionen, dass eine Maschine von Turing nicht, folglich, nicht berechenbar im Kirch-Turing-Sinn kann.

Ein Beispiel eines Problems, das eine Maschine von Turing nicht beheben kann, ist das stockende Problem. Eine Turing Maschine kann nicht entscheiden, ob ein willkürliches Programm hinkt oder für immer läuft. Einige vorgeschlagene Hypercomputer können das Programm für eine unendliche Zahl von Schritten vortäuschen und dem Benutzer erzählen, ob das Programm gehinkt ist.

Hypercomputervorschläge

• Eine Turing Maschine, die ungeheuer viele Schritte vollenden kann. Einfach das Imstandesein, für eine unbegrenzte Zahl von Schritten zu laufen, genügt nicht. Ein mathematisches Modell ist die Maschine von Zeno (begeistert durch das Paradox von Zeno). Die Maschine von Zeno leistet seine erste Berechnung treten ein (sagen) 1 Minute, der zweite Schritt in ½ Minute, der dritte Schritt in ¼ Minute usw. Indem wir 1 +½ +¼ +... (eine geometrische Reihe) resümieren, sehen wir, dass die Maschine ungeheuer viele Schritte in insgesamt 2 Minuten durchführt. Jedoch behaupten einige Menschen, dass, im Anschluss an das Denken aus dem Paradox von Zeno, Maschinen von Zeno nicht nur physisch unmöglich, aber logisch unmöglich sind.
• Die ursprünglichen Orakel-Maschinen von Turing, die von Turing 1939 definiert sind.
• Mitte der 1960er Jahre haben E Mark Gold und Hilary Putnam unabhängig Modelle der induktiven Schlussfolgerung (der "beschränkende rekursive functionals" und "die empirischen Prädikate", beziehungsweise) vorgeschlagen. Diese Modelle ermöglichen einigen nichtrekursiven Sätzen von Zahlen oder Sprachen (einschließlich aller rekursiv enumerable Sätze von Sprachen), in der Grenze "erfahren zu werden"; wohingegen, definitionsgemäß, nur rekursive Sätze von Zahlen oder Sprachen durch eine Maschine von Turing identifiziert werden konnten. Während sich die Maschine zur richtigen Antwort auf jedem erlernbaren Satz in einer endlichen Zeit stabilisieren wird, kann es es nur als richtig identifizieren, wenn es rekursiv ist; sonst wird die Genauigkeit nur durch das Laufen der Maschine für immer und die Anmerkung gegründet, dass es nie seine Antwort revidiert. Putnam hat diese neue Interpretation als die Klasse von "empirischen" Prädikaten identifiziert, festsetzend:" wenn wir immer das 'postulieren', ist die am meisten kürzlich erzeugte Antwort richtig, wir werden eine begrenzte Zahl von Fehlern machen, aber wir werden schließlich die richtige Antwort bekommen. (Bemerken Sie jedoch, dass, selbst wenn wir zur richtigen Antwort gekommen sind (das Ende der begrenzten Folge) wir nie überzeugt sind, dass wir die richtige Antwort haben.)" das 1974-Papier von L. K. Schubert "Hat das Begrenzen wiederholt Recursion und das Programm-Minimierungsproblem" haben die Effekten studiert, das Begrenzungsverfahren zu wiederholen; das erlaubt jedem arithmetischen Prädikat, geschätzt zu werden. Schubert hat geschrieben, "Intuitiv könnte das wiederholte Begrenzen der Identifizierung als höherwertige induktive Schlussfolgerung durchgeführt insgesamt von einer jemals wachsenden Gemeinschaft der niedrigeren Ordnung induktive Inferenzmaschinen betrachtet werden."
• Ein echter Computer (eine Art idealisierter analoger Computer) kann Hyperberechnung durchführen, wenn Physik allgemeine echte Variablen (nicht nur berechenbarer reals) zulässt, und diese irgendwie "harnessable" für die Berechnung sind. Das könnte ziemlich bizarre Gesetze der Physik (zum Beispiel, eine messbare physische Konstante mit einem orakelhaften Wert, wie die Konstante von Chaitin) verlangen, und würde am Minimum, die Fähigkeit verlangen, einen reellwertigen physischen Wert zur willkürlichen Präzision trotz des Thermalgeräusches und der Quant-Effekten zu messen.
• Eine vorgeschlagene Technik, die als schöner Nichtdeterminismus oder unbegrenzter Nichtdeterminismus bekannt ist, kann die Berechnung von nichtberechenbaren Funktionen erlauben. Es gibt Streit in der zu Ende Literatur, ob diese Technik zusammenhängend ist, und ob es wirklich nichtberechenbaren Funktionen erlaubt, "geschätzt" zu werden.
• Es scheint natürlich, dass die Möglichkeit der Zeitreise (Existenz von geschlossenen Zeitmäßigkurven (CTCs)) Hyperberechnung möglich allein macht. Jedoch ist das nicht so, da ein CTC (allein) den unbegrenzten Betrag der Lagerung nicht zur Verfügung stellt, die eine unendliche Berechnung verlangen würde. Dennoch gibt es spacetimes, in dem das CTC Gebiet für die relativistische Hyperberechnung verwendet werden kann. Der Zugang zu einem CTC kann der schnellen Lösung erlauben, Probleme, eine Kompliziertheitsklasse Zu PSPACE-vollenden, die allgemein, während Turing-entscheidbar, rechenbetont unnachgiebig betrachtet wird.
• Gemäß einer 1992-Zeitung konnte ein Computer, der in einer Raum-Zeit von Malament-Hogarth oder in der Bahn um ein rotierendes schwarzes Loch funktioniert, non-Turing Berechnung theoretisch durchführen.
• 1994 hat Hava Siegelmann bewiesen, dass sie neu (1991) rechenbetontes Modell, Artificial Recurrent Neural Network (ARNN), Hyperberechnung durchführen konnte (unendliche Präzision echte Gewichte für die Synapsen verwendend). Es basiert auf dem Entwickeln eines künstlichen Nervennetzes durch eine getrennte, unendliche Folge von Staaten.
• Die unendliche Zeitmaschine von Turing ist eine Generalisation der Maschine von Zeno, die ungeheuer lange Berechnung durchführen kann, deren Schritte durch potenziell transfinite Ordinalzahlen aufgezählt werden. Es modelliert eine sonst gewöhnliche Maschine von Turing, für die nichtstockende Berechnung durch das Eingehen in einen speziellen Staat vollendet wird, der vorbestellt ist, für eine Grenze zu erreichen, Ordnungs-, und für den die Ergebnisse der vorhergehenden unendlichen Berechnung verfügbar sind.
• Jan van Leeuwen und Jiří Wiedermann haben eine 2000-Zeitung geschrieben, die vorschlägt, dass das Internet als ein ungleichförmiges Rechensystem modelliert werden sollte, das mit einer Rat-Funktion ausgestattet ist, die die Fähigkeit von zu befördernden Computern vertritt.
• Eine Symbol-Folge ist in der Grenze berechenbar, wenn es einen begrenzten, vielleicht nichtstockendes Programm auf einer universalen Maschine von Turing dass zusätzlich Produktionen jedes Symbol der Folge gibt. Das schließt die dyadische Vergrößerung von π und jeder anderes berechenbares echtes ein, aber schließt noch den ganzen nichtberechenbaren reals aus. Traditionelle Turing Maschinen können ihre vorherigen Produktionen nicht editieren; verallgemeinerte Maschinen von Turing, wie definiert, durch Jürgen Schmidhuber, können. Er definiert die konstruktiv beschreibbaren Symbol-Folgen als diejenigen, die ein begrenztes, nichtstockendes Programm haben, das auf einer verallgemeinerten Maschine von Turing, solch läuft, dass jedes Produktionssymbol schließlich zusammenläuft, d. h. ändert es sich nicht mehr nach einem begrenzten anfänglichen Zeitabstand. Wegen Beschränkungen, die zuerst von Kurt Gödel (1931) ausgestellt sind, kann es unmöglich sein, die Konvergenz-Zeit selbst durch ein stockendes Programm vorauszusagen, sonst konnte das stockende Problem behoben werden. Schmidhuber verwendet diese Annäherung, um den Satz des formell beschreibbaren oder konstruktiv berechenbaren Weltalls oder die konstruktiven Theorien von allem zu definieren. Verallgemeinerte Turing Maschinen können das stockende Problem durch das Auswerten einer Folge von Specker beheben.
• Mechanisches System eines Quants, das irgendwie eine unendliche Überlagerung von Staaten verwendet, um eine nichtberechenbare Funktion zu schätzen. Das ist nicht das mögliche Verwenden des Standardqubit-Musterquant-Computers, weil es bewiesen wird, dass ein regelmäßiger Quant-Computer PSPACE-reduzierbar ist (ein Quant-Computer, der in der polynomischen Zeit läuft, kann durch einen klassischen Computer vorgetäuscht werden, der im polynomischen Raum läuft).
• 1970 hat E.S. Santos eine Klasse von Fuzzy-Logik-basierten "krausen Algorithmen" und "krausen Maschinen von Turing" definiert. Nachher haben L. Biacino und G. Gerla gezeigt, dass solch eine Definition die Berechnung von nichtrekursiven Sprachen erlauben würde; sie haben einen alternativen Satz von Definitionen ohne diese Schwierigkeit vorgeschlagen. Jiří Wiedermann hat die Fähigkeiten zum ursprünglichen Vorschlag von Santos 2004 analysiert.
• Dmytro Taranovsky hat ein finitistic Modell traditionell non-finitistic Zweige der Analyse vorgeschlagen, die um eine Maschine von Turing gebaut ist, die mit einer schnell zunehmenden Funktion als sein Orakel ausgestattet ist. Dadurch und mehr komplizierte Modelle ist er im Stande gewesen, eine Interpretation der Arithmetik der zweiten Ordnung zu geben.

Analyse von Fähigkeiten

Viele Hyperberechnungsvorschläge belaufen sich auf alternative Weisen, ein Orakel oder in eine sonst klassische Maschine eingebettete Rat-Funktion zu lesen. Andere erlauben Zugang zu einem höheren Niveau der arithmetischen Hierarchie. Zum Beispiel Maschinen von Turing unter den üblichen Annahmen stark superzubeanspruchen, würde im Stande sein, jedes Prädikat im Wahrheitstabelle-Grad zu schätzen, der enthält oder. Begrenzungs-Recursion kann im Vergleich jedes Prädikat oder Funktion im entsprechenden Grad von Turing schätzen, der, wie man bekannt, ist. Gold hat weiter gezeigt, dass das Begrenzen teilweisen recursion die Berechnung genau der Prädikate erlauben würde.

Taxonomie von "superrekursiven" Berechnungsmethodiken

Burgin hat eine Liste dessen gesammelt, was er "superrekursive Algorithmen" nennt (von Burgin 2005: 132):

• das Begrenzen rekursiver Funktionen und das Begrenzen teilweiser rekursiver Funktionen (E. M Gold)
• Probe und Fehlerprädikate (Hilary Putnam)
• induktive Inferenzmaschinen (Carl Herbert Smith)
• induktive Maschinen von Turing (eines der eigenen Modelle von Burgin)
• beschränken Sie Maschinen von Turing (ein anderes der Modelle von Burgin)

• empirische Maschinen (Ja. Hintikka und A. Mutanen)
• Maschinen von General Turing (J. Schmidhuber)
• Internetmaschinen (van Leeuwen, J. und Wiedermann, J.)
• Entwicklungscomputer, die DNA verwenden, um den Wert einer Funktion (Darko Roglic) zu erzeugen
• krause Berechnung (Jiří Wiedermann)
• Entwicklungsmaschinen von Turing (Eugene Eberbach)

In demselben Buch präsentiert er auch eine Liste "algorithmischer Schemas":

• Maschinen von Turing mit willkürlichen Orakeln (Alan Turing)
• Maschinenbediener von Transrecursive (Borodyanskii und Burgin)
• Maschinen, die mit reellen Zahlen rechnen (L. Blum, F. Cucker, M. Shub und S. Smale)
• Nervennetze haben auf reellen Zahlen (Hava Siegelmann) gestützt

Kritik

Martin Davis, in seinen Schriften auf der Hyperberechnung

kennzeichnet dieses Thema als "ein Mythos" und bietet Gegenargumente dem an

physische Durchführbarkeit der Hyperberechnung. Bezüglich seiner Theorie argumentiert er

die Ansprüche, dass das ein neues Feld gegründet in den 1990er Jahren ist. Dieser Gesichtspunkt verlässt sich

auf der Geschichte der Berechenbarkeitstheorie (Grade der Unlösbarkeit, Berechenbarkeit über

Funktionen, reelle Zahlen und Ordnungszahlen), wie auch erwähnt, oben.

Andrew Hodges hat einen kritischen Kommentar zu Copeland und den Artikel von Proudfoot geschrieben.

Siehe auch

• Berechnung
• Superaufgabe

Weiterführende Literatur

• Hava Siegelmann und Eduardo Sontag, "Analoge Berechnung über Nervennetze," Theoretische Informatik 131, 1994: 331-360.
• Hava Siegelmann. Nervennetze und Analoge Berechnung: Außer der Turing-Grenze 1998 Boston: Birkhäuser (Buch).
• Mike Stannett, Der Fall für Hyperberechnung, Angewandte Mathematik und Berechnung, Band 178, Ausgabe 1, am 1. Juli 2006, Seiten 8-24, Sonderausgabe auf der Hyperberechnung
• Keith Douglas. Super-Turing Berechnung: eine Fallstudie-Analyse (PDF), M.S. Thesis, Universität von Carnegie Mellon, 2003.
• L. Blum, F. Cucker, M. Shub, S. Smale, Kompliziertheit und Echte Berechnung, Springer-Verlag 1997. Die allgemeine Entwicklung der Kompliziertheitstheorie für abstrakte Maschinen, die auf reellen Zahlen statt Bit rechnen.
• [ftp://ftp.cs.cuhk.hk/pub/neuro/papers/jcss1.ps.Z Auf der rechenbetonten Macht von Nervennetzen]
• Toby Ord. Hyperberechnung: Computerwissenschaft mehr als die Maschine von Turing kann rechnen: Ein Überblick-Artikel über verschiedene Formen der Hyperberechnung.
• Apostolos Syropoulos (2008), Hyperberechnung: Außer der Kirch-Turing-Barriere (Vorschau), Springer rechnend. Internationale Standardbuchnummer 978-0-387-30886-9
• Burgin, M. S. (1983) Induktive Turing Maschinen, Benachrichtigungen der Akademie von Wissenschaften der UDSSR, v. 270, Nr. 6, Seiten 1289-1293
• Mark Burgin (2005), Superrekursive Algorithmen, Monografien in der Informatik, Springer. Internationale Standardbuchnummer 0-387-95569-0
• Cockshott, P. und Michaelson, G. Gibt es neue Modelle der Berechnung? Antworten Sie Wegner und Eberbach, Der Computerzeitschrift, den 2007
• Copeland, J. (2002) Hyperberechnung, Meinungen und Maschinen, v. 12, Seiten 461-502
• Martin Davis (2006), "Die Kirch-Turing-These: Einigkeit und Opposition". Verhandlungen, Berechenbarkeit in Europa 2006. Vortrag bemerkt in der Informatik, 3988 Seiten 125-132
• Hagar, A. und Korolev, A., Quant-Hyperberechnung — Trick oder Berechnung? (2007)
• Rogers, H. (1987) Theorie von rekursiven Funktionen und wirksamer Berechenbarkeit, MIT Presse, Cambridge Massachusetts
• Volkmar Putz und Karl Svozil, kann ein Computer "gedrängt" werden, als Licht schneller zu leisten? (2010)

Links

• Hyperberechnungsforschungsnetz
• Hyperberechnung
• Toby Ord, Hyperberechnung: Computerwissenschaft mehr als die Maschine von Turing
• Toby Ord, Die vielen Formen der Hyperberechnung
• Paolo Cotogno, Hyperberechnung und die Physische Kirch-Turing-These
• Gualtiero Piccinini, Berechnung in physischen Systemen