Was ist Turing Complete?

Question

Was bedeutet der Ausdruck "Turing Complete"?

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

Answer 1

Hier ist die kürzeste Erklärung:

Ein Turing-komplettes System ist ein System, in dem ein Programm geschrieben werden kann, das eine Antwort findet (wenn auch ohne Garantien in Bezug auf Laufzeit oder Speicher).

Wenn also jemand sagt: "Mein neues Ding ist Turing-vollständig", dann bedeutet das, dass es im Prinzip (wenn auch oft nicht in der Praxis) zur Lösung jedes Rechenproblems verwendet werden kann.

Manchmal ist es ein Witz... ein Typ hat einen Turingmaschinen-Simulator in vi geschrieben, so dass man sagen kann, dass vi die einzige Rechenmaschine ist, die jemals auf der Welt gebraucht wurde.

Answer 2

Hier ist die einfachste Erklärung

Alan Turing schuf eine Maschine, die ein Programm aufnehmen, ausführen und ein Ergebnis anzeigen kann. Aber dann musste er verschiedene Maschinen für verschiedene Programme entwickeln. So schuf er die "Universal Turing Machine", die JEDES Programm annehmen und ausführen kann.

Programmiersprachen sind diesen Maschinen ähnlich (wenn auch virtuell). Sie nehmen Programme auf und führen sie aus. Eine Programmiersprache wird als "Turing-komplett" bezeichnet, 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 sie addiert. Eine Turing-Maschine kann dieses Programm leicht ausführen. Aber nun stellen Sie sich vor, dass Ihre Programmiersprache aus irgendeinem Grund die gleiche Addition nicht durchführen kann. Dann wäre sie sozusagen "Turing-unvollständig". Wenn sie andererseits jedes Programm ausführen kann, das auch die universelle Turing-Maschine ausführen kann, dann ist sie "Turing-komplett".

Die meisten modernen Programmiersprachen (z. B. Java, JavaScript, Perl usw.) sind alle Turing-komplett, da sie alle Funktionen implementieren, die für die Ausführung von Programmen erforderlich sind, wie z. B. Addition, Multiplikation, if-else-Bedingungen, Rücksprunganweisungen, Möglichkeiten zum Speichern/Abrufen/Löschen von Daten und so weiter.

Update: Weitere Informationen finden Sie in meinem Blogbeitrag: "JavaScript ist Turing-komplett"-erklärt

Answer 3

Informelle Definition

Eine vollständige Turing-Sprache ist eine Sprache, die jede Berechnung ausführen kann. Die Church-Turing-These besagt, dass jede durchführbare Berechnung von einer Turing-Maschine ausgeführt werden kann. A Turingmaschine ist eine Maschine mit einem unendlichen Speicher mit wahlfreiem Zugriff und einem endlichen "Programm", das ihr vorschreibt, wann sie lesen, schreiben und sich in diesem Speicher bewegen soll, wann sie mit einem bestimmten Ergebnis enden soll und was sie als nächstes tun soll. Die Eingabe für eine Turing-Maschine wird in den Speicher eingegeben, bevor sie gestartet wird.

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

Eine Turing-Maschine kann Entscheidungen auf der Grundlage dessen treffen, was sie im Speicher sieht - Die "Sprache", die nur unterstützt + , - , * et / auf Ganzzahlen ist nicht Turing-vollständig, weil sie keine Wahl auf der Grundlage ihrer Eingabe treffen kann, eine Turing-Maschine aber schon.

Eine Turing-Maschine kann ewig laufen - Wenn wir Java, Javascript oder Python nehmen und die Fähigkeit, jede Art von Schleife, GOTO oder Funktionsaufruf zu machen, entfernen würden, wäre es nicht Turing-vollständig, weil es keine beliebige Berechnung durchführen kann, die nie endet. Coq ist ein Theorembeweiser, der keine Programme ausdrücken kann, die nicht terminieren, also ist er nicht Turing-vollständig.

Eine Turing-Maschine kann unendlichen Speicher verwenden - Eine Sprache, die genau wie Java wäre, sich aber beenden würde, sobald sie mehr als 4 Gigabyte Speicher verbraucht, wäre nicht Turing-komplett, da eine Turing-Maschine unendlich viel Speicher verwenden kann. Deshalb können wir eigentlich nicht bauen eine Turing-Maschine, aber Java ist trotzdem eine vollständige Turing-Sprache, weil die Java Sprache hat keine Einschränkung, die verhindert, dass sie unendlich viel Speicher verbraucht. Dies ist ein Grund, warum reguläre Ausdrücke nicht Turing-vollständig sind.

Eine Turing-Maschine hat einen Speicher mit wahlfreiem Zugriff - Eine Sprache, die die Arbeit mit dem Speicher nur über push y pop Operationen auf einem Stapel wären nicht Turing-vollständig. Wenn ich eine "Sprache" habe, die eine Zeichenkette liest einmal und nur Speicher durch Push- und Poppingvorgänge von einem Stapel verwenden kann, kann es mir sagen, ob jeder ( in der Zeichenkette hat eine eigene ) später durch Schieben, wenn es sieht ( und knallt, wenn er sieht ) . Es kann mir aber nicht sagen, ob jeder ( hat seine eigene ) zu einem späteren Zeitpunkt et jede [ hat seine eigene ] später (beachten Sie, dass ([)] diese Kriterien erfüllt, aber ([]] nicht). Eine Turing-Maschine kann ihren Arbeitsspeicher nutzen, um zu verfolgen () und [] Aber diese Sprache mit nur einem Stapel kann das nicht.

Eine Turing-Maschine kann jede andere Turing-Maschine simulieren - Eine Turing-Maschine kann, wenn sie ein entsprechendes "Programm" erhält, das "Programm" einer anderen Turing-Maschine nehmen und es mit einer beliebigen Eingabe simulieren. Wenn man eine Sprache hätte, der es verboten wäre, einen Python-Interpreter zu implementieren, wäre sie nicht Turing-komplett.

Beispiele für vollständige Turing-Sprachen

Wenn Ihre Sprache unendlichen Speicher mit wahlfreiem Zugriff, bedingte Ausführung und irgendeine Form der wiederholten Ausführung hat, ist sie wahrscheinlich Turing-komplett. Es gibt exotischere Systeme, die trotzdem alles erreichen können, was eine Turing-Maschine kann, was sie ebenfalls Turing-vollständig macht:

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

Answer 4

Von wikipedia :

Turing-Vollständigkeit, benannt nach Alan Turing, ist insofern von Bedeutung, als dass jeder plausibles Design für einen Computer so weit fortgeschrittenen Gerät emuliert werden kann durch eine universelle Turing-Maschine emuliert werden kann - eine Beobachtung, die bekannt geworden ist als die Church-Turing-These bekannt geworden ist. Daher ist eine Maschine, die wie eine universelle Turing-Maschine fungieren kann, kann im Prinzip, jede Berechnung durchführen, die jeder andere jeder andere programmierbare Computer kann. Dies hat jedoch nichts zu tun mit dem Aufwand für das Schreiben eines Programms für die Maschine zu schreiben, die Zeit, die es Zeit, die die Maschine zur Durchführung der Berechnung benötigt, oder mit den Fähigkeiten der Maschine besitzen kann, die nichts mit die nichts mit der Berechnung zu tun haben.

Während wirklich Turing-komplette Maschinen sehr wahrscheinlich physikalisch unmöglich sind, da sie unbegrenzten Speicherplatz benötigen, wird die Turing-Vollständigkeit oft grob physischen Maschinen oder Programmiersprachen zugeschrieben Programmiersprachen, die universell wären universal wären, wenn sie unbegrenzten Speicherplatz hätten. Alle modernen Computer sind Turing-komplett in diesem Sinne.

Ich weiß nicht, wie man noch untechnischer sein kann, außer indem man sagt: "Turing-vollständig bedeutet 'in der Lage, ein berechenbares Problem zu beantworten, wenn man genügend Zeit und Platz hat'".

Answer 5

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.