Was bedeutet es, Turing vollständig zu sein?

33

Ich sehe, dass die meisten Definitionen dessen, was es heißt, vollständig zu sein, bis zu einem gewissen Grad tautologisch sind. Zum Beispiel, wenn Sie Google "Was bedeutet es, Turing vollständig zu sein", erhalten Sie:

Ein Computer ist vollständig, wenn er ein Problem lösen kann, das eine Turing-Maschine ...

Obwohl es sehr gut definiert ist, ob verschiedene Systeme Turing vollständig sind oder nicht, habe ich keine Erklärung dafür gesehen, welche Auswirkungen / Konsequenzen es hat, wenn Turing vollständig ist.

Was kann eine Turing-Maschine tun, wenn es keine Nicht-Turing-Maschine gibt, die dieselbe Aufgabe ausführen kann? Zum Beispiel kann ein Computer einfache Berechnungen durchführen (1+5)/3=?, aber ein gewöhnlicher Taschenrechner kann sie auch ausführen , was nicht vollständig ist, wenn ich richtig liege.

Gibt es eine Möglichkeit, die Funktionen von Turing Machine zu definieren, ohne nur zu sagen, dass "eine andere Turing Machine simuliert werden kann"?

Sashoalm
quelle
31
Suchen Sie die Definition von "Turing-Maschine". Es gibt keine zirkuläre Definition, da eine Turing-Maschine nicht als "in der Lage ist, eine andere Turing-Maschine zu simulieren" definiert ist - es ist ein vollständig entwickelter theoretischer Computer (im Grunde eine unendliche Bandzustandsmaschine). Sie mischen nur "turing-complete" und "turing machine". Soweit ich weiß, kennen wir noch keine Algorithmen, die nicht auf einer Turing-Maschine laufen können, aber das könnte nur meine eigene Unkenntnis sein.
Luaan
2
@Luaan Die Church-Turing-These würde Ihnen zustimmen.
Brian McCutchon
"Gibt es eine Möglichkeit, die Fähigkeiten von Turing Machine zu definieren?" Sicher. In der Theorie geht es darum, wie viel Raum und Zeit benötigt wird, um Algorithmen mit Turing-Maschinen (L, NL, P, NP, PSPACE usw.) zu lösen, und es gibt auch Probleme, die nicht gelöst werden können (die in der Regel durch Reduzierungen auf gelöst werden können andere unlösbare Probleme). Ein Beispiel für ein Problem, das von Turing-Maschinen nicht gelöst werden kann, ist das Stopp-Problem.
Millie Smith
Wenn es um CS (oder eine andere) Theorie geht, ist es immer besser, ein Buch über ein Thema zu lesen, als es zu googeln und einige Blog-Beiträge zu einem Thema zu lesen, die in vielen Fällen von Personen verfasst wurden, die das Thema nicht vollständig verstehen sich. Ein gutes Buch spart Ihnen Zeit, gibt Ihnen ein umfassenderes Bild und ein besseres Verständnis.
Bozidar Sikanjic
Die Ackermann-Funktion ist ein prominentes Beispiel für etwas, das eine Turing-Maschine berechnen kann, ein eingeschränkteres Rechenmodell ( primitive Rekursion ) jedoch nicht.
zwol

Antworten:

13

Ich überlegte eine Weile, ob ich noch eine Antwort hinzufügen sollte. Die anderen Antworten konzentrieren sich auf die Mitte seiner Frage ("Turing Complete", "Tautology" usw.). Lassen Sie mich den ersten und letzten Teil und damit das größere und leicht philosophische Bild festhalten:

Aber was bedeutet es?

Was bedeutet es, Turing vollständig zu sein?

Gibt es eine Möglichkeit, die Funktionen von Turing Machine zu definieren, ohne nur zu sagen, dass "eine andere Turing Machine simuliert werden kann"?

Informell ausgedrückt bedeutet Turing Complete, dass Ihr Mechanismus jeden erdenklichen Algorithmus ausführen kann , unabhängig davon, wie komplex, tief, rekursiv, kompliziert, lang (in Bezug auf Code) er ist und wie viel Speicherplatz oder Zeit benötigt wird benötigt, um es zu bewerten. Es ist selbstverständlich , dass es gelingt nur , wenn das Problem berechenbar ist, aber wenn es ist berechenbar, es wird (Halt) gelingen.

(NB: Um herauszufinden, warum dies "informell" ist, lesen Sie die Church-Turing-These, die in diesem Sinne verfasst ist. Da es sich um eine These handelt, könnte sie jedoch richtig sein oder auch nicht. Dank an @DavidRicherby für wies in einem Kommentar auf diese kleine Lücke hin.)

"Algorithmus" bedeutet das, was wir heute allgemein als Computeralgorithmus verstehen. dh eine Reihe von diskreten Schritten, die den Speicher manipulieren, wobei eine Steuerlogik eingemischt ist. Es ist jedoch nicht wie eine Oracle-Maschine, dh es kann nicht "erraten".

Beispiel für eine praktische Fremdsprache

Wenn Sie sich selbst programmiert haben, kennen Sie wahrscheinlich reguläre Ausdrücke, mit denen Zeichenfolgen einem Muster zugeordnet werden.

Dies ist ein Beispiel für ein Konstrukt, das nicht vollständig ist. Sie können leicht Übungen finden, bei denen es einfach unmöglich ist, einen regulären Ausdruck zu erstellen, der bestimmten Phrasen entspricht.

Zum Beispiel (und dies hat sicherlich viele Programmierer in der tatsächlichen realen Anwendungen geärgert), ist es theoretisch und praktisch unmöglich , einen regulären Ausdruck zu erstellen , die eine Programmiersprache oder ein XML - Dokument übereinstimmt: Es ist unmöglich für eine regexp die Blockstruktur zu finden ( do ... endoder { ... }in Sprachen (Öffnen und Schließen von Tags in XML-Dokumenten), wenn sie beliebig tief sein dürfen. Wenn es dort eine Beschränkung gibt, können Sie beispielsweise nur drei Ebenen der "Rekursion" haben, dann könnten Sie einen regulären Ausdruck finden; aber wenn es nicht begrenzt ist, dann ist es ein No-Go.

Da es offensichtlich möglich ist, ein Programm in einer Turing-vollständigen Sprache (wie C) zu erstellen, um den Quellcode zu analysieren (jeder Compiler tut dies), können reguläre Ausdrücke dieses Programm niemals simulieren, daher sind sie per Definition nicht Turing-vollständig

Motivation

Die Idee der Turingmaschine an sich ist nichts Praktisches; Das heißt, Turing hat es sicherlich nicht erfunden, um einen echten Computer oder so etwas zu erschaffen, im Gegensatz zu zum Beispiel Charles Babbage oder von Neumann. Das Konzept der Turing-Maschine ist äußerst einfach. Es besteht fast aus nichts. Es reduziert mögliche (und tatsächliche) Computer auf ein denkbar geringes Maß.

Der Sinn dieser Vereinfachung besteht wiederum darin, dass es so einfach (ish) ist, über theoretische Fragen nachzudenken (wie das Stoppen von Problemen, Komplexitätsklassen und was auch immer sich die theoretische Informatik selbst stört). Ein besonderes Merkmal ist, dass es normalerweise sehr einfach ist, zu überprüfen, ob eine bestimmte Sprache oder ein bestimmter Computer eine Turing-Maschine simulieren kann, indem einfach die Turing-Maschine (was so einfach ist!) In dieser Sprache programmiert wird.

Zur Unendlichkeit

Beachten Sie, dass Sie niemals unendlich viel Zeit oder Speicherplatz benötigen . aber sowohl Zeit als auch Speicher sind unbegrenzt. Sie haben einen Maximalwert für jeden einzelnen berechenbaren Lauf, aber es gibt keine Begrenzung dafür, wie groß dieser Wert werden kann. Die Tatsache, dass einem echten Computer irgendwann der Arbeitsspeicher ausgeht, wird hier beschönigt. Dies ist natürlich eine Grenze für jeden physischen Computer, aber es ist auch offensichtlich und für die theoretische "Rechenleistung" der Maschine nicht von Interesse. Außerdem interessiert es uns überhaupt nicht, wie lange es tatsächlich dauert. Unsere kleine Maschine kann also beliebig viel Zeit und Raum beanspruchen, was sie absolut unpraktisch macht.

... und darüber hinaus

Ein erstaunlicher letzter Punkt ist, dass so eine einfache Sache alles kann, was ein realer Computer im gesamten Universum jemals erreichen könnte (nur sehr viel langsamer) - zumindest soweit wir heute wissen.

AnoE
quelle
"Informell gesehen bedeutet Turing vollständig zu sein, dass Ihr Mechanismus jeden Algorithmus ausführen kann, den Sie sich vorstellen können." Nun, das setzt voraus, dass Sie die Church-Turing-These akzeptieren, wonach Turing-Maschinen jeden Algorithmus implementieren können, den Sie sich vorstellen können. Alternativ können Sie Turing-Maschinen als Definition des Algorithmus verwenden. In diesem Fall ist die informelle Anweisung nur eine informelle Version von "kann jede Turing-Maschine simulieren" (was keine schlechte Sache ist; nur eine Beobachtung).
David Richerby
Mein Eindruck war, dass das OP nach einem intuitiven Verständnis fragt, was es bedeutet, vollständig zu sein. Daher ist diese Art von flippiger, nicht-theoretischer Informatik-Antwort. Vielen Dank für den Hinweis, ich werde es in die Antwort integrieren. @DavidRicherby
AnoE
Vielen Dank! Das ist die Art von Antwort, nach der ich gesucht habe. Ich habe über das Stopp-Problem nachgedacht und darüber, wie Sprachen mit einfachen For-Loops vorhersehbar sind (sie halten immer an) - und somit nicht Turing-vollständig. Ich dachte, Turing-complete zu sein, bedeutet möglicherweise in irgendeiner Weise unvorhersehbar zu sein (ist chaotisch der richtige Begriff für diese Funktionen?)
Sashoalm
@sashoalm, froh, dass dir die Antwort gefällt. Nein, Unvorhersehbarkeit spielt keine Rolle. Bounded for-loops (als non-tc) sind ebenfalls ein gutes Beispiel. Tatsächlich wäre ein weiteres gutes Beispiel für eine einfache (und realistischere) tc-Sprache eine, die nur Variablen hat und (unbegrenzt) while- das ist bereits genug, um tc zu sein. Die (Un-) Begrenztheit der Kontrollstruktur ist eines der Schlüsselelemente.
AnoE
38

Es ist überhaupt nicht tautologisch.

Ein Berechnungsmodell ist Turing-vollständig, wenn es alle Turing-Maschinen simulieren kann, dh es ist mindestens so leistungsfähig wie Turing-Maschinen.

Eine Sache, die Turingmaschinen tun können, ist die Simulation anderer Turingmaschinen (über die universelle Turingmaschine). Das heißt, wenn Ihr Berechnungsmodell Turing-Maschinen nicht simulieren kann, kann es nicht mindestens eines tun, was Turing-Maschinen können, sodass es nicht der Definition entspricht und Turing nicht vollständig ist. Es gibt keine Zirkularität, weil wir die Turing-Vollständigkeit nicht in sich selbst definiert haben: Wir sagten, dass die Turing-Vollständigkeit die Eigenschaft ist, in der Lage zu sein, alles zu tun, was Turing-Maschinen können.

ab

Gibt es eine Möglichkeit, die Funktionen von Turing Machine zu definieren, ohne nur zu sagen, dass "eine andere Turing Machine simuliert werden kann"?

Ich bin mir nicht sicher, was Sie unter "die Fähigkeiten von Turing-Maschinen definieren" verstehen. Die Fähigkeiten werden in Bezug auf den endlichen Automaten definiert, der auf dem unendlichen Band arbeitet. (Ich werde die vollständige Definition nicht wiederholen, aber Sie finden sie z . B. auf Wikipedia .)

David Richerby
quelle
19
Ich denke OP verwechselt Turingmaschine und Turing komplett. Was er eigentlich sucht, ist die Definition einer Turing-Maschine; Ihr letzter Satz ist die Antwort. en.wikipedia.org/wiki/Turing_machine würde helfen.
JollyJoker
Was kann eine Turingmaschine? Wenn ich beweisen wollte, dass etwas eine Turing-Maschine emulieren kann, welche minimalen Verhaltensweisen muss ich dann nachweisen können, dass meine Maschine dies auch kann?
Akshat Mahajan
2
Egal - ich habe herausgefunden, dass es ausreicht, zu demonstrieren, dass eine Sprache die Funktionsweise einer Turing-Maschine imitieren kann, um zu beweisen, dass sie vollständig ist.
Akshat Mahajan
17

Turings Rechenmodell ist nur eines von vielen äquivalenten Rechenmodellen. Es hat die gleiche Kraft wie Gödels rekursive Funktionen und die etwa zur gleichen Zeit vorgeschlagene Lambda-Rechnung von Church sowie andere Modelle wie die Zeigermaschine. Das können Sie also sagen

Ein Computer ist vollständig, wenn er ein Problem lösen kann, das Excel kann.

Dies funktioniert, da Excel auch vollständig ist. Ich empfehle einen Blick auf die Wikipedia-Seite zur Church-Turing-These und auf ein Übersichtsblatt von Blass und Gurevich, Algorithmen: Eine Suche nach absoluten Definitionen .


In Bezug auf Ihre Frage, was eine Turing-Maschine kann, was eine Nicht-Turing-Maschine nicht kann, hängt die Antwort im Allgemeinen leider von der Nicht-Turing-Maschine ab.

Es ist jedoch möglich, nicht-triviale Begriffe von Turing-vollständigen Problemen zu definieren, zum Beispiel:

LAfaAf(a)L

Unter dieser Definition sind geeignete Kodierungen des Halteproblems Turing-vollständig, und für eine vernünftige Klasse von Maschinen (abhängig von der Definition von "effizient berechenbar") ist die Maschine Turing-vollständig, wenn sie einige (äquivalent alle) realisieren kann ) Richtungsweisende Sprache.

Es gibt viele andere Turing-vollständige Probleme, die von diesem Formalismus erfasst werden, abhängig von der Definition von "effizient berechenbar", wie beispielsweise das Turing-Korrespondenzproblem und Probleme in Bezug auf Wang-Kacheln und das Spiel des Lebens. Jedes dieser Probleme kann anstelle des Halteproblems als Benchmark fungieren.

Yuval Filmus
quelle
"Die Antwort hängt leider von der Nicht-Turing-Maschine ab" - Ich habe meine Frage bearbeitet, weil es nicht klar war. Sie können eine beliebige Nicht-Turing-Maschine auswählen, sofern diese die Aufgabe ausführen kann und nicht vollständig ist.
Sashoalm
5
Excel is also Turing-complete.- Nur wenn Sie Excel unendlich viel Speicher geben können. Excel ist auf 1.048.576 Zeilen und 16.384 Spalten beschränkt, was bei weitem nicht unendlich ist.
MattClarke
5
@MattClarke: Richtig, aber aus dem gleichen Grund ist kein System, das jemals gebaut wurde, vollständig.
Emil
3
@Emil: Genau, und es ist wichtig, dass die Schüler von CS zwischen den Fähigkeiten von Rechenmodellen und den Fähigkeiten tatsächlicher Maschinen unterscheiden. Diejenigen von uns, die wiederholt an die physikalischen Grenzen unserer Maschinen gestoßen sind, können diese Unterscheidung natürlich leicht treffen. Wir wissen also, wie wir eine uneingeschränkte Version des Excel-Rechenmodells definieren und ob es vollständig ist. Auch wenn das Ausschreiben dieser Definition etwas umständlich ist.
Steve Jessop
4
@SteveJessop Physikalische Grenzen von Maschinen? Wie könnte jemand so etwas schlagen? 640k ist genug für jedermann!
David Richerby
4

Zunächst möchte ich darauf hinweisen, dass die Definition der Turing-Vollständigkeit überhaupt nicht tautologisch ist. Ein Rechenmodell nicht nur beweisen Turing-complete ist ein interessantes Ergebnis für sich, sondern ermöglicht es Ihnen auch, alle Ergebnisse der Rechenfähigkeitstheorie sofort auf dieses andere Rechenmodell zu übertragen. Beispiel: 2-Zähler-Maschinen sind Turing-vollständig. Turing-Maschinen können das Problem des Anhaltens nicht lösen, daher können es auch keine 2-Zähler-Maschinen.

μ

Eine solche Klasse enthält jene Funktionen, die "intuitiv berechenbar" sind, dh die von einem Menschen nach einem genauen Algorithmus mit Bleistift und Papier berechnet werden könnten.

Offensichtlich ist "intuitiv berechenbar" keine formale Definition, die Identifikation von "intuitiv berechenbar" mit "Turing berechenbar" ist als "Church-Turing-These" bekannt. Da viele formale Versuche, die Berechenbarkeit zu charakterisieren, letztendlich zu einem Rechenmodell konvergieren, das Turing-vollständig ist, obwohl es niemals einen formalen Beweis für eine solche Behauptung im mathematischen Sinne geben wird, gibt es starke Gründe, dies zu glauben.

schnelle Sorte
quelle
0

Eine Turing-Maschine kann dieselben Funktionen wie ein universeller Quantencomputer berechnen, der jedes physikalische System simulieren kann:

https://www.cs.princeton.edu/courses/archive/fall04/cos576/papers/deutsch85.pdf

Als solches kann eine Turing-Maschine jede nach den Gesetzen der Physik zulässige Informationsverarbeitung ausführen, obwohl sie eine solche Verarbeitung nicht immer so effizient wie möglich ausführt.

alanf
quelle