Was ist Turing abgeschlossen?

Was bedeutet der Ausdruck "Turing Complete"?

Können Sie eine einfache Erklärung geben, ohne auf zu viele theoretische Details einzugehen?

Hier ist die kürzeste Erklärung:

Ein Turing Complete-System ist ein System, in das ein Programm geschrieben werden kann, das eine Antwort findet (allerdings ohne Garantie für Laufzeit oder Speicher).

Wenn also jemand sagt "mein neues Ding ist Turing Complete", bedeutet dies im Prinzip (obwohl oft nicht in der Praxis), dass es zur Lösung eines Rechenproblems verwendet werden kann.

Manchmal ist es ein Witz ... ein Typ hat einen Turing-Maschinensimulator in vi geschrieben, also kann man sagen, dass vi die einzige Rechenmaschine ist, die jemals auf der Welt benötigt wird.

Hier ist die einfachste Erklärung

Alan Turing hat eine Maschine erstellt, die ein Programm aufnehmen, dieses Programm ausführen und einige Ergebnisse anzeigen kann. Aber dann musste er verschiedene Maschinen für verschiedene Programme erstellen. Also schuf er "Universal Turing Machine", die JEDES Programm nehmen und ausführen kann.

Programmiersprachen ähneln diesen Maschinen (obwohl virtuell). Sie nehmen Programme und führen sie aus. Jetzt heißt eine Programmiersprache "Turing abgeschlossen", wenn sie jedes Programm (unabhängig von der Sprache) ausführen kann, das eine Turing-Maschine mit genügend Zeit und Speicher ausführen kann.

Zum Beispiel: Nehmen wir an, es gibt ein Programm, das 10 Zahlen nimmt und diese hinzufügt. Turing Maschine kann dieses Programm leicht ausführen. Stellen Sie sich jetzt vor, dass Ihre Programmiersprache aus irgendeinem Grund nicht dieselbe Addition ausführen kann. Dies würde es "Turing unvollständig" machen (sozusagen). Wenn andererseits ein Programm ausgeführt werden kann, das die universelle Turing-Maschine ausführen kann, ist Turing abgeschlossen.

Die meisten modernen Programmiersprachen (z. B. Java, JavaScript, Perl usw.) sind alle Turing-vollständig, da sie alle Funktionen ausführen, die zum Ausführen von Programmen erforderlich sind, z Daten und so weiter.

Update: Weitere Informationen finden Sie in meinem Blogbeitrag: "JavaScript ist vollständig" - Erklärt

Aus Wikipedia :

Die nach Alan Turing benannte Vollständigkeit von Turing ist insofern von Bedeutung, als jedes plausible Design für ein bisher fortgeschrittenes Computergerät von einer universellen Turing-Maschine emuliert werden kann - eine Beobachtung, die als Church-Turing-These bekannt geworden ist. Somit kann eine Maschine, die als universelle Turingmaschine fungieren kann, im Prinzip jede Berechnung durchführen, die jeder andere programmierbare Computer kann. Dies hat jedoch nichts mit dem Aufwand zu tun, der zum Schreiben eines Programms für die Maschine erforderlich ist, der Zeit, die die Maschine möglicherweise benötigt, um die Berechnung durchzuführen, oder mit den Fähigkeiten der Maschine, die möglicherweise nicht mit der Berechnung zusammenhängen.

Während wirklich Turing-vollständige Maschinen sehr wahrscheinlich physisch unmöglich sind, da sie unbegrenzten Speicherplatz erfordern, wird die Vollständigkeit von Turing häufig lose physischen Maschinen oder Programmiersprachen zugeschrieben, die universell wären, wenn sie unbegrenzten Speicherplatz hätten. Alle modernen Computer sind in diesem Sinne Turing-vollständig.

Ich weiß nicht, wie Sie nicht-technischer sein können, außer wenn Sie sagen: "Vollständig zu sein bedeutet, ein berechenbares Problem zu beantworten, wenn genügend Zeit und Raum vorhanden sind."

Informelle Definition

Eine vollständige Turing-Sprache kann jede Berechnung durchführen. Die Church-Turing-These besagt, dass jede durchführbare Berechnung von einer Turing-Maschine durchgeführt werden kann. Eine Turingmaschine ist eine Maschine mit unendlichem Direktzugriffsspeicher und einem endlichen 'Programm', das vorschreibt, wann sie diesen Speicher lesen, schreiben und durchlaufen soll, wann sie mit einem bestimmten Ergebnis enden soll und was sie als nächstes tun soll. Die Eingabe in eine Turing-Maschine wird vor dem Start gespeichert.

Dinge, die eine Sprache NICHT vollständig machen können

Ein Turing - Maschine kann Entscheidungen treffen , auf dem, was sie im Speicher sieht - die ‚Sprache‘ , dass nur unterstützt +, -, *, und /auf ganze Zahlen ist Turing nicht abgeschlossen werden, da es keine andere Wahl aufgrund seiner Eingabe machen, sondern eine Turing - Maschine kann.

Eine Turing-Maschine kann für immer laufen - Wenn wir Java, Javascript oder Python verwenden und die Möglichkeit entfernen würden, Schleifen, GOTOs oder Funktionsaufrufe auszuführen, wäre Turing nicht vollständig, da keine beliebige Berechnung durchgeführt werden kann endet nie. Coq ist ein Theorembeweiser, der keine Programme ausdrücken kann, die nicht beendet werden. Daher ist Turing nicht vollständig.

Eine Turing-Maschine kann unendlichen Speicher verwenden - Eine Sprache, die genau wie Java war, jedoch beendet wurde, wenn mehr als 4 Gigabyte Speicher verwendet wurden, wäre nicht vollständig, da eine Turing-Maschine unendlichen Speicher verwenden kann. Aus diesem Grund können wir keine Turing-Maschine erstellen , aber Java ist immer noch eine vollständige Turing-Sprache, da die Java- Sprache keine Einschränkungen aufweist, die die Verwendung von unendlichem Speicher verhindern. Dies ist einer der Gründe, warum reguläre Ausdrücke nicht vollständig sind.

Eine Turing-Maschine verfügt über Arbeitsspeicher mit wahlfreiem Zugriff - Eine Sprache, mit der Sie nur mit Speicher arbeiten pushund popOperationen an einem Stapel ausführen können, wäre Turing nicht vollständig. Wenn ich eine 'Sprache' habe, die eine Zeichenfolge einmal liest und den Speicher nur durch Drücken und Poppen von einem Stapel verwenden kann, kann sie mir später sagen, ob jede (Zeichenfolge ihre eigene hat ), indem sie drückt, wenn sie sieht, (und knallt, wenn sie sieht ). Es kann mir jedoch nicht sagen, ob jeder später (seinen eigenen hat und jeder später seinen eigenen hat (Hinweis, der diese Kriterien erfüllt, dies aber nicht tut). Eine Turing-Maschine kann ihren Direktzugriffsspeicher verwenden, um die und zu verfolgen)[]([)]([]]()[]ist separat, aber diese Sprache mit nur einem Stapel kann nicht.

Eine Turingmaschine kann jede andere Turingmaschine simulieren - Eine Turingmaschine kann, wenn sie ein geeignetes 'Programm' erhält, das 'Programm' einer anderen Turingmaschine nehmen und es bei beliebiger Eingabe simulieren. Wenn Sie eine Sprache hätten, deren Implementierung eines Python-Interpreters verboten war, wäre Turing nicht vollständig.

Beispiele für Turing komplette Sprachen

Wenn Ihre Sprache über einen unendlichen Direktzugriffsspeicher, eine bedingte Ausführung und eine Form der wiederholten Ausführung verfügt, ist sie wahrscheinlich vollständig. Es gibt exotischere Systeme, die immer noch alles erreichen können, was eine Turing-Maschine kann, was sie auch komplett macht:

• Untypisierter Lambda-Kalkül
• Conways Spiel des Lebens
• C ++ - Vorlagen
• Prolog

Grundsätzlich ist die Vollständigkeit von Turing eine kurze Voraussetzung, eine unbegrenzte Rekursion.

Nicht einmal an die Erinnerung gebunden.

Ich habe unabhängig darüber nachgedacht, aber hier ist 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.

Turing Complete bedeutet, dass es mindestens so leistungsstark ist wie eine Turing-Maschine . Dies bedeutet, dass alles, was von einer Turing-Maschine berechnet werden kann, von einem Turing-Komplettsystem berechnet werden kann.

Niemand hat bisher ein System gefunden, das leistungsfähiger ist als eine Turingmaschine. Die Aussage, dass ein System Turing Complete ist, ist vorerst dasselbe wie die Aussage, dass das System genauso leistungsfähig ist wie jedes bekannte Computersystem (siehe Church-Turing-These ).

Im einfachsten Sinne kann ein Turing-Komplettsystem jedes mögliche Rechenproblem lösen.

Eine der Hauptanforderungen ist, dass die Größe des Notizblocks unbegrenzt ist und dass ein Rücklauf möglich ist, um auf vorherige Schreibvorgänge auf dem Notizblock zuzugreifen.

Somit ist in der Praxis kein System Turing-vollständig.

Vielmehr nähern sich einige Systeme der Turing-Vollständigkeit an, indem sie unbegrenzten Speicher modellieren und mögliche Berechnungen durchführen, die in den Speicher des Systems passen.

Ich denke, die Bedeutung des Konzepts "Turing Complete" liegt in der Fähigkeit, eine Rechenmaschine (nicht unbedingt einen mechanischen / elektrischen "Computer") zu identifizieren, deren Prozesse in "einfache" Anweisungen zerlegt werden können, die aus einfacheren und einfacheren bestehen Anweisungen, die eine Universalmaschine interpretieren und dann ausführen könnte.

Ich kann The Annotated Turing nur empfehlen

@ Mark Ich denke, was Sie erklären, ist eine Mischung aus der Beschreibung der Universal Turing Machine und Turing Complete.

Etwas, das im praktischen Sinne Turing Complete ist, wäre eine Maschine / ein Prozess / eine Berechnung, die / der als Programm geschrieben und dargestellt werden kann und von einer Universalmaschine (einem Desktop-Computer) ausgeführt werden kann. Allerdings wird weder Zeit noch Speicher berücksichtigt, wie von anderen erwähnt.

Was ich in einfachen Worten verstehe:

Turing abgeschlossen: Eine Programmiersprache / ein Programm, das Berechnungen durchführen kann, ist Turing abgeschlossen.

Beispielsweise :

1. Können Sie zwei Zahlen verwenden Fügen Sie einfach HTML . (Ans ist ' Nein ', Sie müssen Javascript verwenden, um das Hinzufügen durchzuführen.) Daher ist HTML nicht vollständig.

2. Sprachen wie Java, C ++, Python, Javascript, Solidity for Ethereum usw. sind Turing Complete, da Sie mit diesen Sprachen Berechnungen wie das Hinzufügen von zwei Zahlen durchführen können.

Hoffe das hilft.

Es ist vollständig, wenn es testen und verzweigen kann (hat ein 'wenn')

Eine Turingmaschine erfordert, dass jedes Programm Zustandstests durchführen kann. Das ist grundlegend.

Betrachten Sie einen Player Piano Roll. Das Player Piano kann ein sehr kompliziertes Musikstück spielen, aber es gibt niemals eine bedingte Logik in der Musik. Es ist Turing abgeschlossen.

Bedingte Logik ist sowohl die Leistung als auch die Gefahr einer Maschine, die Turing Complete ist.

Die Pianorolle wird garantiert jedes Mal angehalten. Es gibt keine solche Garantie für ein TM. Dies wird als "Halteproblem" bezeichnet.

Wie Waylon Flinn sagte :

Turing Complete bedeutet, dass es mindestens so leistungsstark ist wie eine Turing-Maschine.

Ich glaube, das ist falsch, ein System ist Turing vollständig, wenn es genau so leistungsfähig ist wie die Turing-Maschine, dh jede von der Maschine durchgeführte Berechnung kann vom System durchgeführt werden, aber auch jede vom System durchgeführte Berechnung kann von der Turing-Maschine durchgeführt werden .

In praktischen Sprachbegriffen, die den meisten Programmierern bekannt sind, besteht die übliche Methode zur Erkennung der Turing-Vollständigkeit darin, dass die Sprache die Simulation verschachtelter unbegrenzter while-Anweisungen zulässt oder zulässt (im Gegensatz zum Pascal-Stil für Anweisungen mit festen Obergrenzen).

Kann eine relationale Datenbank Breiten- und Längengrade von Orten und Straßen eingeben und den kürzesten Weg zwischen ihnen berechnen - nein. Dies ist ein Problem, das zeigt, dass SQL nicht vollständig ist.

Aber C ++ kann es und kann jedes Problem lösen. So ist es.