Klar, vollständig, Beweis dafür, dass eine Sprache Turing Compete ist?

Ich habe Websites gesehen, die vorgeben zu "beweisen", dass HTML5 + CSS Turing Complete ist.

Ich habe Websites gesehen, die vorgeben, "zu beweisen", dass SQL Turing Complete ist.

Ich habe eine Reihe von Websites gesehen, die vorgeben zu "erklären", was es bedeutet, Turing Complete zu sein.

Genug!

Wo finde ich ein Buch (geschrieben von einem Experten für Berechenbarkeitstheorie) oder einen von Experten begutachteten Artikel (in einer seriösen Zeitschrift), der den Beweis liefert: "Diese Sprache XYZ kann eine Rechenmaschine beschreiben, die dieselbe Rechenleistung besitzt als Turingmaschine "?

computability turing-machines automata turing-completeness church-turing-thesis Roger Costello
quelle

Kein Experte wird ein solches Papier schreiben, weil es sinnlos wäre.

Andrej Bauer

Aber es gibt Papiere, die das tun. Betrachten Sie quasi verzögerungsunempfindliche Schaltungen als Turing-vollständig, die einen Konstruktionsnachweis haben.

Dan D.

Ich esse meinen Hut, wenn Sie ein Peer-Review-Papier finden, das einen detaillierten Beweis dafür enthält, dass HTML5 + CSS, SQL oder PHP vollständig sind.

Andrej Bauer

@andrej versuchen Sie dieses. nahe genug? XSLT Version 2.0 ist Turing-Complete: Ein rein transformationsbasierter Beweis . Vielleicht essen Sie einfach Ihr Gemüse: p

vzn

siehe auch, was eine Sprache komplett macht , programmers.se

vzn

Antworten:

$C_1, C_2$

$1$ $C_i$ $I_j$
$1$ $C_i$ $C_i > 0$ $I_j$ $C_i = 0$ $I_k$

Das Ergebnis ist bewiesen in:

Marvin L. Minsky, "Rekursive Unlösbarkeit des Post-Problems von Tag und anderen Themen in der Theorie der Turingmaschinen" (1961)

Vergessen Sie nicht, dass ein Rechenmodell (in Ihrem Fall eine Programmiersprache + ein Gerät, das in dieser Sprache geschriebene Programme ausführt ) nur dann als vollständig angesehen werden kann, wenn es den Zugriff auf eine unbegrenzte Menge an Speicher (dh Speicherplatz) unterstützt oder speichern kann ( in irgendeiner Form) beliebig große ganze Zahlen. Eine Programmiersprachenimplementierung auf einem realen Computer entspricht einem linear begrenzten Automaten .

Auf den Wikipedia-Seiten zum RAM-Modell und zum RASP-Modell finden Sie auch zahlreiche Referenzen .

Schließlich ist ein schönes Buch, das sich mit der Äquivalenz verschiedener Rechenmodelle befasst:

"Modelle der Berechnung: Eine Einführung in die Berechenbarkeitstheorie" von Maribel Fernandez

Vor
quelle

"Vergessen Sie nicht, dass eine Programmiersprache nur dann als Turing vollständig betrachtet werden kann, wenn sie den Zugriff auf unendlichen Speicher unterstützt." Daher kann es keine Implementierung einer Turing Complete-Sprache geben? Ist das deine Schlussfolgerung? Oder wollten Sie sagen, dass alle (die meisten) Sprachen, die wir verwenden, Turing Complete sind, weil diese Anforderung leicht zu erreichen ist? Beide Schlussfolgerungen sind aus Ihrer jetzigen Antwort gültig.

Bakuriu

bakuriu siehe TM vollständige & Rechenleistung

vzn

@ Bakuriu: in der Tat ist der Satz ein bisschen mehrdeutig; Ich meine nur, dass ein Rechenmodell als vollständig angesehen werden kann, wenn es in irgendeiner Form die Verwendung eines unbegrenzten Speichers ermöglicht. Die meisten Programmiersprachen sind Turing vollständig, da sie in ihren (Syntax-) Spezifikationen keine Beschränkungen für die Größe von Variablen oder Zeigern haben, aber ihre Implementierungen sind begrenzt. siehe zum Beispiel Cs <limit.h>. Selbst wenn Sie einen Computer mit unbegrenztem Speicher haben, auf dem eine C-Implementierung ausgeführt wird, können Sie diesen Speicher nur verwenden, wenn Sie einen "zusätzlichen Mechanismus" bereitstellen, der nicht Teil der Sprache ist.

Vor dem

{w . w ∣ w \in {0, 1}}

$\{w.w \mid w \in \{0, 1\}\}$

Die beiden am häufigsten verwendeten Lehrbücher zur Berechenbarkeits- und Komplexitätstheorie sind:

Michael Sipser: Einführung in die Berechnungstheorie , 2 / e, Cengage, 2005.

John E Hopcroft; Jeffrey D Ullman: Einführung in die Automatentheorie, Sprachen und Berechnung , Addison-Wesley, 1979.

Es gibt auch eine schöne Philosophie-Monographie für Laien, die die technischen Details der Berechenbarkeitstheorie ohne die formalen Beweise durcharbeitet.

Douglas Hoftstadter: Gödel, Escher, Bach , Grundlegende Bücher, 1979.

Schließlich kann die beste Einführung in die Berechenbarkeit ein Puzzle-Buch eines berühmten Logikers sein:

Raymond Smullyan: Die Dame oder der Tiger und andere logische Rätsel , Pinguin, 1983. (Jetzt in einer preiswerten Dover-Ausgabe, 2009.)

(Er beginnt mit einer Reihe von Rätseln, die auf dem Paradoxon des Lügners basieren, und führt Sie dann durch die Konstruktion einer selbstreferenziellen Aussage in der Gestalt eines Puzzles im Sherlock Holmes-Stil über eine mysteriöse verschlossene Schachtel.)

Wanderlogik
quelle