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

In praktischen Sprachbegriffen, die den meisten Programmierern vertraut sind, besteht die übliche Art, Turing-Vollständigkeit zu erkennen, darin, dass die Sprache die Simulation von verschachtelten unbegrenzten while-Anweisungen (im Gegensatz zu for-Anweisungen im Pascal-Stil mit festen Obergrenzen) erlaubt oder zulässt.

Answer 2

Als Waylon Flinn sagte :

Turing Complete bedeutet, dass sie mindestens so leistungsfähig ist wie eine Turing-Maschine.

Ich glaube, das ist falsch, ein System ist Turing-vollständig, wenn es genau so mächtig ist wie die Turing-Maschine, d.h. jede Berechnung, die von der Maschine ausgeführt wird, kann von dem System ausgeführt werden, aber auch jede Berechnung, die von dem System ausgeführt wird, kann von der Turing-Maschine ausgeführt werden.

Answer 3

Wir nennen eine Sprache dann und nur dann Turing-vollständig, wenn sie (1) von einer Turing-Maschine entscheidbar ist, aber (2) nicht von etwas weniger Fähigem als einer Turing-Maschine. Zum Beispiel ist die Sprache der Palindrome über dem Alphabet {a, b} von Turing-Maschinen entscheidbar, aber auch von Pushdown-Automaten; diese Sprache ist also nicht Turing-komplett. Wirklich Turing-komplette Sprachen - solche, die die volle Rechenleistung von Turing-Maschinen erfordern - sind ziemlich selten. Vielleicht ist die Sprache der Zeichenketten x.y.z, in der x eine Zahl, y eine Turing-Maschine und z eine anfängliche Bandkonfiguration ist und y auf z in weniger als x Schritten zum Stillstand kommt, eine solche Sprache (auch wenn das gezeigt werden müsste!).

Im allgemeinen Sprachgebrauch wird Turing-Vollständigkeit mit Turing-Äquivalenz verwechselt. Turing-Äquivalenz bezieht sich auf die Eigenschaft eines Rechensystems, das Turing-Maschinen simulieren kann und von diesen simuliert werden kann. Man könnte zum Beispiel sagen, dass Java eine Turing-äquivalente Programmiersprache ist, weil man einen Turing-Maschinen-Simulator in Java schreiben kann und weil man eine Turing-Maschine definieren könnte, die die Ausführung von Java-Programmen simuliert. Nach der Church-Turing-These können Turing-Maschinen jede effektive Berechnung durchführen, also bedeutet Turing-Äquivalenz, dass ein System so fähig wie möglich ist (wenn die Church-Turing-These wahr ist!).

Turing-Äquivalenz ist ein weitaus wichtigeres Anliegen als echte Turing-Vollständigkeit; dies und die Tatsache, dass "vollständig" kürzer ist als "äquivalent", mag erklären, warum "Turing-komplett" so oft fälschlicherweise als "Turing-äquivalent" verwendet wird, aber ich schweife ab.

Answer 4

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 Turing-komplett ist.

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