Theoretische Maschinen, die leistungsstärker sind als Turingmaschinen

39

Gibt es theoretische Maschinen, die in einigen Bereichen die Leistungsfähigkeit von Turing-Maschinen übersteigen?

user1561358
quelle
5
Fragen wie "Ist X ein bestimmendes Merkmal unseres Universums?" ist eine physikalische Frage, da die Physik genau das Studium der "Gesetze des Universums" ist. In der Informatik geht es um mathematische Objekte, die manchmal durch physikalische Mittel umsetzbar sind.
Bakuriu
2
Ich würde empfehlen, nach "Super Turing Machines" zu suchen, insbesondere nach den Vorschlägen von Have Siegelmann: umass.edu/newsoffice/article/… und binds.cs.umass.edu/papers/1995_Siegelmann_Science.pdf
nobillygreen am
1. Wir bitten Sie, pro Beitrag nur eine Frage zu stellen. Wenn Sie andere Fragen haben, können Sie diese separat posten, nachdem Sie die Antworten darauf gesehen haben. Auch Fragen zu den bestimmenden Merkmalen unseres Universums sind physikalische Fragen und werden hier nicht behandelt. Ich bearbeite die Zusatzfragen, damit Sie sich auf eine einzelne Frage konzentrieren können. Sie können sie separat veröffentlichen (im Revisionsverlauf finden Sie sie wieder). 2. Was hast du recherchiert? Was sind deine Gedanken? Eine Frage mit einem Satz ist zu kurz. Versuchen Sie, es zu bearbeiten, um es zu vervollständigen. das wird Ihnen helfen, bessere Antworten zu geben.
DW
3. "Können wir das annehmen ..." - nein, natürlich nicht. Warum denkst du, dass du es annehmen kannst? Sie können nicht einfach etwas annehmen, weil es schön wäre, wenn es wahr wäre, oder es scheint, als ob es wahr wäre, oder weil wir nicht sofort einen Grund dafür sehen, warum es falsch wäre. In der Informatik geht es um Beweise, nicht nur um die Annahme von Dingen. Was ist deine wirkliche Frage?
DW

Antworten:

26

Die Church-Turing-These (in einer Formulierung) besagt, dass alles, was physikalisch berechenbar ist, auch auf einer Turing-Maschine berechnet werden kann. Angenommen, Sie glauben diesen Thesen und sind an Funktionen interessiert, die solche Maschinen berechnen könnten (und nicht etwa an interaktiven Berechnungen), dann ist keine Hyperberechnung möglich.

Die Church-Turing-These befasst sich nur mit dem Berechenbaren, nicht aber mit der Effizienz der Berechnung. Es ist bekannt, dass Turing-Maschinen nicht so effizient sind, obwohl sie polynomisch klassische Computer simulieren. Man geht davon aus, dass Quantencomputer exponentiell effizienter sind als Turing-Maschinen. In diesem Sinne können Sie Turing-Maschinen schlagen (wenn Sie nur einen skalierbaren Quantencomputer bauen könnten).

Scott Aaronson hat wahrscheinlich mehr zu sagen - ich überlasse es Ihnen, dies selbst nachzuschlagen.

Yuval Filmus
quelle
Eigentlich habe ich Scotts Blog schon vorgemerkt. :) Wie auch immer, da die CT-These bis heute gültig ist (es sei denn, es ist etwas passiert, von dem ich nichts weiß), bleibt nur noch über die Definition der berechenbaren Maschine zu sprechen oder nach einer Maschine zu suchen, die die CT irgendwie widerlegt.
user1561358
3
"Wie in diesem Aufsatz erörtert, ist die Komplexitätstheorie inzwischen weit über deterministische Turing-Maschinen hinausgegangen und umfasst (zum Beispiel) Quantenmechanik, paralleles und verteiltes Rechnen und stochastische Prozesse wie die Darwinsche Evolution." ( Warum sich Philosophen um die Komplexität von
Computern kümmern sollten
1
Ich finde es auch bemerkenswert, dass Quantencomputer keine willkürliche AFAIK-Aufgabe beschleunigen. Und sie beschleunigen es "nur" um maximal 2 ^ N, wobei N die Anzahl der Quantenbits ist.
Hoffentlich
13

Die Church-Turing-These muss nicht als Glaubensartikel aufgefasst werden. es ist wahrscheinlich sinnvoller, es als eine Beschreibung, eine Definition dessen zu betrachten , was wir unter dem Begriff "Berechnung" verstehen, und es ist auch ein ziemlich enger Begriff der Berechnung: Berechnung durch einen einzelnen Prozessor, der Schritte streng sequentiell ohne externe Schritte ausführt Interferenz. Bestimmte Aspekte der Berechnung, über die wir nachdenken müssen, werden von diesem Begriff nicht abgedeckt, und viele zusätzliche mathematische Theorien wurden in der Informatik entwickelt, um diese Bedenken auszuräumen.

Die Church-Turing-These ist also nicht so sehr ein bestimmendes Merkmal unseres Universums, sondern vielmehr ein bestimmendes Merkmal einer bestimmten Art, bestimmte Dinge in unserem Universum zu tun.

In dieser Hinsicht kann es mit der euklidischen Geometrie verglichen werden. Ist unser Universum von Natur aus euklidisch? Warum sind unsere Methoden zur Landmessung durch ihre Prinzipien begrenzt? Können wir keine Hypergeometrie haben, die eine leistungsfähigere Landmessung ermöglicht? Die Antwort lautet: Wir können und wir tun es, aber wir nennen die Ergebnisse nicht immer "Landmessung" oder "Geometrie".

Ebenso gehen unsere Theorie und Praxis in Bezug auf die Berechnung über das hinaus, was Turing-Maschinen beschreiben können (z. B. gibt es Prozesskalküle zur Beschreibung von gleichzeitigen Systemen), aber wir bezeichnen diese Erweiterungen nicht unbedingt als "Berechnung".

reinierpost
quelle
Meinen Sie mit "Berechnung durch einen einzelnen Prozessor, der Schritte streng sequentiell ohne externe Interferenzen ausführt", dass ein Computer, der externe Interferenzen aufweist oder parallel arbeiten kann, viel leistungsfähiger ist als eine Turing-Maschine?
Kate
1
Nicht ganz. Wenn Sie nur wissen möchten, welche Zuordnungen von endlichen Eingaben zu endlichen Ausgaben berechnet werden können, können Sie durch Hinzufügen dieser Zuordnungen nicht mehr Leistung erhalten: Sie können nicht mehr Zuordnungen als zuvor berechnen.
Reinierpost
5

Eine theoretische Schwäche einer Turingmaschine ist ihre Vorhersagbarkeit. Ein allmächtiger und allwissender Gegner könnte diese Schwäche ausnutzen, wenn er ein Spiel gegen die Turing-Maschine spielt. Wenn eine theoretische Maschine also Zugang zu einer zufälligen Quelle hätte, die ihr Gegner nicht vorhersagen (und ihren inneren Zustand vor ihrem Gegner verbergen könnte), dann wäre diese theoretische Maschine leistungsfähiger als eine Turing-Maschine.

Das Problem bei dieser Art theoretischer Maschine im wirklichen Leben ist nicht, ob die Zufallsquelle vollkommen zufällig ist oder nicht (vorausgesetzt, sie ist vollkommen zufällig, eine harmlose Idealisierung), sondern dass wir niemals sicher sein können, ob es uns gelungen ist, unser Inneres zu verbergen Zustand von unserem Gegner. Im konkreten Fall kann man also nie sicher sein, ob es gültig ist, den aktuellen Fall einer Situation durch eine solche Maschine zu idealisieren. Dies ist nur geringfügig besser als die Situation für die meisten Arten von Hypercomputern, in denen mir unklar ist, welche idealisierten Situationen von diesen modelliert werden sollten (ich antwortete einmal: Ich brauche also eine Art allwissende Wundermaschine, um "RE" zu lösen, Ich wusste nicht, dass es solche Maschinen gibt. )

Π20 Diese Entschuldigung ergab sich aus einem Gespräch mit einem anderen Thomas, nämlich Thomas Chust.)

Thomas Klimpel
quelle