Was bedeutet der Ausdruck "Turing Complete"?
Können Sie eine einfache Erklärung geben, ohne auf zu viele theoretische Details einzugehen?
Antworten
Zu viele Anzeigen?
Shelby Moore III
Punkte
5909
Im Grunde genommen besteht die Turing-Vollständigkeit aus einer einzigen prägnanten Anforderung, der unbeschränkten Rekursion.
Nicht einmal durch den Speicher begrenzt.
Ich habe mir das selbst ausgedacht, aber hier eine Diskussion der Behauptung. Meine Definition von LSP bietet mehr Kontext.
Die anderen Antworten hier definieren nicht direkt das grundlegende Wesen der Turing-Vollständigkeit.
Shelby Moore III
Punkte
5909
Vereinfacht ausgedrückt, kann ein Turing-komplettes System jedes mögliche Rechenproblem lösen.
Eine der wichtigsten Anforderungen ist, dass die Größe des Scratchpads unbegrenzt ist und dass es möglich ist, zurückzuspulen, um auf frühere Schreibvorgänge im Scratchpad zuzugreifen.
In der Praxis ist also kein System Turing-komplett.
Vielmehr nähern sich einige Systeme der Turing-Vollständigkeit an, indem sie einen unbegrenzten Speicher modellieren und alle möglichen Berechnungen durchführen, die in den Speicher des Systems passen.
Glenn Mohammad
Punkte
2650
Superkurze Zusammenfassung dessen, was Professor Brasilford in diesem Artikel erklärt Video .
Turing Complete macht alles, was eine Turing-Maschine machen kann.
-
Sie hat bedingte Verzweigung (d.h. "if-Anweisung"). Bedeutet auch "go to" und erlaubt somit eine Schleife.
-
Es wird beliebige Menge an Speicherplatz (z.B. ausreichend langes Band), die das Programm benötigt.
Brian Leahy
Punkte
33603
Ich denke, die Bedeutung des Konzepts "Turing Complete" liegt in der Fähigkeit, eine Rechenmaschine (nicht notwendigerweise ein mechanischer/elektrischer "Computer") zu identifizieren, deren Prozesse in "einfache" Anweisungen zerlegt werden können, die aus immer einfacheren Anweisungen bestehen, die eine Universalmaschine interpretieren und dann ausführen könnte.
Ich empfehle sehr The Annotated Turing
@Mark ich denke, was du erklärst, ist eine Mischung aus der Beschreibung der Universal Turing Machine und Turing Complete.
Etwas, das im praktischen Sinne Turing-vollständig ist, wäre eine Maschine/ein Prozess/eine Berechnung, der/die als Programm geschrieben und dargestellt werden kann, um von einer Universalmaschine (einem Desktop-Computer) ausgeführt zu werden. Dabei werden jedoch weder Zeit noch Speicherplatz berücksichtigt, wie von anderen erwähnt.
Richard Riehle
Punkte
31
Eine Turing-Maschine erfordert, dass jedes Programm Bedingungstests durchführen kann. Das ist grundlegend.
Betrachten Sie eine Player-Piano-Rolle. Das Player-Piano kann ein hochkompliziertes Musikstück spielen, aber es gibt niemals eine bedingte Logik in der Musik. Sie ist pas Turing abgeschlossen.
Die bedingte Logik ist sowohl die Macht als auch das Gefahr einer Maschine, die Turing-komplett ist.
Die Klavierrolle hält garantiert jedes Mal an. Bei einer TM gibt es diese Garantie nicht. Dieses wird das "Halteproblem" genannt.
