Was macht eine Sprache Turing-komplett?

A Turing tarpit ist eine Art esoterische Programmiersprache, die sich bemüht, Turing-vollständig zu sein und dabei so wenig Elemente wie möglich zu verwenden. Brainfuck ist vielleicht die bekannteste Plane, aber es gibt viele.

• Iota und Jot sind Funktionssprachen mit zwei bzw. drei Symbolen, basierend auf der SK (I) -Kombinatorrechnung .

• OISC ( Ein Befehlssatzcomputer ) bezeichnet eine Art von Imperativberechnung, die nur einen Befehl mit einem oder mehreren Argumenten erfordert, normalerweise „subtrahieren und verzweigen, wenn kleiner oder gleich Null“ oder „Umkehren subtrahieren und überspringen, wenn ausleihen“. Die x86-MMU implementiert die vorherige Anweisung und ist somit Turing-vollständig.

Im Allgemeinen für eine Um eine vollständige Turing-Sprache zu erhalten, ist Folgendes erforderlich:

1. Eine Form der bedingten Wiederholung oder des bedingten Sprungs (z. B. while, if + goto)

2. Eine Möglichkeit, irgendeine Form von Speicher zu lesen und zu schreiben (z , Variablen, Band)

Damit eine Lambda-Kalkül -basierte Funktionssprache TC ist, ist es Bedürfnisse:

1. Die Fähigkeit, Funktionen über Argumente zu abstrahieren (z. B. Lambda-Abstraktion, Zitat)

2. Die Fähigkeit, Funktionen anzuwenden Argumente (z. B. Reduktion)

Es gibt natürlich andere Betrachtungsweisen für die Berechnung, aber dies sind gängige Modelle für Turing-Tarpits. Beachten Sie, dass echte Computer nicht universelle Turing-Maschinen sind, da sie keinen unbegrenzten Speicher haben. Genau genommen handelt es sich um „gebundene Speichermaschinen“. Wenn Sie ihnen weiterhin Speicher hinzufügen würden, würden sie sich asymptotisch Turing-Maschinen an der Macht nähern. Für die Berechnung sind jedoch auch begrenzte Speichermaschinen und Finite-State-Maschinen nützlich. Sie sind einfach nicht universell .

Genau genommen ist E / A für die Vollständigkeit von Turing nicht erforderlich. TC behauptet nur, dass eine Sprache die gewünschte Funktion berechnen kann, nicht, dass sie Ihnen das Ergebnis zeigen kann. In der Praxis hat jede nützliche Sprache eine Möglichkeit, irgendwie mit der Welt zu interagieren.

Kommentare

• Sind einfache Variablen für imperative Sprachen ausreichend? Ich hatte den Eindruck, dass eine Art Sammlung (z. B. Arrays oder verknüpfte Listen) erforderlich wäre.
• @luiscubal Sie müssen in der Lage sein, eine beliebige Datenmenge anzugeben. Mit einfachen Variablen können Sie die Datenmenge darstellen, über die die Variablen selbst verfügen. Was ist, wenn Sie N + 1 verschiedene Daten darstellen müssen? Man könnte argumentieren, dass man mit Tricks , wie Fractran spielt, dies auch in einfachen Variablen tun könnte … aber dass ‚ ist nicht ganz das, was Sie ‚ fragen.
• Ist ‚ nicht erforderlich, dass die Sprache ENDLOSE Schleifen?
• Re, “ Jede nützliche Sprache hat eine Möglichkeit, mit der Welt zu interagieren. “ Algol 60 hatte keine definierte Art der Interaktion mit der Welt. Alle Ihre E / A in einem Algol 60-Programm wurden durch Aufrufen von Bibliotheksfunktionen ausgeführt, und die Bibliotheksfunktionen können in verschiedenen Implementierungen völlig unterschiedlich sein. Ich möchte mich hiermit jedoch jeder Diskussion entziehen, ob Algol 60 “ nützlich war oder nicht. “

Aus praktischer Sicht: Wenn Sie alle Programme in einer Turing-vollständigen Sprache in Ihre Sprache übersetzen können, dann (soweit) Ich weiß), deine Sprache muss Turing-vollständig sein.Wenn Sie überprüfen möchten, ob eine von Ihnen entworfene Sprache Turing-vollständig ist, können Sie einfach einen Brainf *** an Ihren YourLanguage-Compiler schreiben und beweisen / demonstrieren, dass er alle legalen BF-Programme kompilieren kann.

To Ich meine, dass Sie zusätzlich zu einem Interpreter für YourLanguage einen Compiler (in einer beliebigen Sprache) schreiben, der jedes BF-Programm in YourLanguage kompilieren kann (natürlich unter Beibehaltung der gleichen Semantik).

Kommentare

• Ja, das wäre definitiv der praktischste Weg, sich dem anzunähern. </sarcasm>
• @RobertHarvey hat einen Punkt, aber die allgemeine Idee ist sehr wichtig. Brainfuck ist nachweislich vollständig und sehr einfach in Bezug auf Programmiersprachen. Für nicht-esoterische Programmiersprachen ist die Implementierung eines Brainfuck-Interpreters möglicherweise viel einfacher und schneller als die Bereitstellung eines strengen Beweises aus dem Nichts (ich kann BF in ein paar Zeilen Python implementieren, aber ich ‚ Ich bin mir nicht sicher, wo ich mit einem formalen Beweis beginnen soll, dass Python vollständig ist. und Dutzende von esoterischen, von Brainfuck inspirierten Sprachen sind bekanntermaßen vollständig, weil ‚ bekannt ist, wie sie auf Brainfuck abgebildet werden.
• @RobertHarvey: Warum nicht? Sicherlich könnte jemand, der seine eigene Sprache entwirft, einen BF-Compiler schreiben (wenn dies unbedingt erforderlich wäre, und ansonsten eine geeignete andere Sprache finden).
• @delnan: Sie werden Sie müssen jedoch nachweisen, dass Ihr BF-Interpreter die BF-Spezifikation korrekt implementiert. IOW müssen Sie nachweisen, dass Ihr BF-Interpreter tatsächlich ein BF-Interpreter und kein Interpreter für eine BF-ähnliche Sprache ist, die möglicherweise nicht vorhanden ist Turing-complete.
• @ DarekNędza, dass ‚ nur eine natürliche Folge der Definition der Turing-Vollständigkeit ist; Jede Erweiterung einer Turing Complete-Sprache ist weiterhin Turing Complete.

Ein System kann nur berücksichtigt werden Turing vollständig zu sein, wenn es etwas kann, was eine universelle Turing-Maschine kann. Da die universelle Turing-Maschine in der Lage sein soll, jede berechenbare Funktion zu einem bestimmten Zeitpunkt zu lösen, können Turing-Komplettsysteme dies auch tun.

Um zu überprüfen, ob etwas Turing-vollständig ist, prüfen Sie, ob Sie kann eine Turing-Maschine darin implementieren. Mit anderen Worten, prüfen Sie, ob Folgendes simuliert werden kann:

1. Die Fähigkeit, „Variablen“ (oder beliebige Daten) zu lesen und zu schreiben) : Ziemlich selbsterklärend.
2. Die Möglichkeit, das Bewegen des Lese- / Schreibkopfs : Es reicht nicht aus, nur Variablen abzurufen und zu speichern. Es muss auch möglich sein, die Fähigkeit zu simulieren, den Kopf des Bandes zu bewegen, um auf andere Variablen zu verweisen. Dies kann häufig in Programmiersprachen unter Verwendung von Array-Datenstrukturen (oder Äquivalenten) oder bei bestimmten Sprachen wie Maschinencode durch die Möglichkeit, andere Variablen mithilfe von „Zeigern“ (oder Äquivalenten) zu referenzieren, simuliert werden.
3. Die Fähigkeit, eine Finite-State-Maschine zu simulieren : Obwohl nicht oft erwähnt, sind Turing-Maschinen tatsächlich eine Variation der Finite-State-Maschinen, die häufig in der KI-Entwicklung verwendet werden. Alan Turing sagte, der Zweck der Zustände sei es, die verschiedenen Arten der Problemlösung einer Person zu simulieren.
4. Ein „Halt“ -Zustand : Obwohl oft erwähnt wird, dass sich ein Regelwerk wiederholen kann, um als vollständig zu gelten, ist dies kein wirklich gutes Kriterium seit der formalen Definition dessen, was ein Algorithmus ist Zustand Algorithmen müssen immer irgendwann schließen. Wenn sie nicht auf irgendeine Weise schließen können, ist sie entweder nicht vollständig oder der Algorithmus ist keine berechenbare Funktion. Wenn komplette Systeme, die aufgrund ihrer Funktionsweise technisch nicht abgeschlossen werden können (wie z. B. Spielekonsolen), diese Einschränkung umgehen, können sie einen Haltezustand auf irgendeine Weise „simulieren“. Nicht zu verwechseln mit dem „Halteproblem“ „, eine unentscheidbare Funktion, die beweist, dass es unmöglich ist, ein System zu erstellen, das mit 100% iger Zuverlässigkeit erkennen kann, ob eine bestimmte Eingabe dazu führt, dass ein anderes System nicht geschlossen wird.

Dies ist das wahre Minimum Anforderungen an ein System, das als vollständig angesehen werden soll. Nicht mehr, nicht weniger. Wenn es keines davon auf irgendeine Weise simulieren kann, ist es nicht vollständig. Die von anderen vorgeschlagenen Methoden sind nur Mittel zum Zweck, da es mehrere Turing-Komplettsysteme gibt, die diese Funktionen nicht aufweisen.

Beachten Sie, dass es keine bekannte Möglichkeit gibt, ein echtes Turing-Komplettsystem zu erstellen Dies liegt daran, dass es keine bekannte Möglichkeit gibt, die Grenzenlosigkeit des Bandes der Turing-Maschine im physischen Raum wirklich zu simulieren.

Eine Programmiersprache ist vollständig, wenn Sie damit rechnen können.Es gibt nicht nur eine Reihe von Funktionen, die eine Sprachprüfung vervollständigen, sodass Antworten, die besagen, dass Sie Schleifen benötigen oder Variablen benötigen, falsch sind, da es Sprachen gibt, die keine aber Turing ist vollständig.

Alan Turing hat die Universal-Turing-Maschine erstellt. Wenn Sie ein Programm übersetzen können, das für die Universal-Maschine entwickelt wurde, um in Ihrer Sprache ausgeführt zu werden, ist Turing auch vollständig. Dies funktioniert auch indirekt, sodass Sie sagen können, dass die Sprache X vollständig ist, wenn alle Programme für die vollständige Sprache Y für X übersetzt werden können, da alle universellen Turing-Maschinenprogramme in ein Y-Programm übersetzt werden können.

Die zeitliche Komplexität Die Komplexität des Raums, das einfache Eingabe- / Ausgabeformat und das einfache Schreiben eines Programms sind nicht in der Gleichung enthalten, sodass eine solche Maschine theoretisch alle Berechnungen durchführen kann, wenn die Berechnungen nicht durch Leistungsverlust oder Verschlucken der Erde durch die Sonne gestoppt werden.

Um die Vollständigkeit der Sprache zu beweisen, stellen sie normalerweise einen Dolmetscher für jede nachweislich vollständige Sprache her. Damit dies jedoch funktioniert, benötigen Sie Eingabe- und Ausgabemittel, zwei Dinge, die für eine vollständige Sprache wirklich nicht erforderlich sind. Es reicht aus, dass Ihr Programm den Status beim Start ändern kann und Sie den Speicher nach dem Anhalten des Programms überprüfen können.

Um eine erfolgreiche Sprache zu erstellen, ist jedoch mehr als nur die Vollständigkeit erforderlich Dies gilt auch für Turing-Tarpits. Ich glaube nicht, dass BrainFuck ohne , und ..

Kommentare

• “ Eine Programmiersprache ist vollständig, wenn Sie eine Berechnung durchführen können damit. “ Das ‚ ist die Church-Turing-These, nicht das, was eine Sprache Turing-vollständig macht.
• @Rhymoid Sie meinen also, dass nichts vollständig ist, es sei denn, Sie können einen Interpreter erstellen? Das heißt, der Lambda-Kalkül ist nicht vollständig, selbst wenn er ‚ gleich ist?
• Ich ‚ suche immer noch nach einer maßgeblichen Definition der Begriffe Turing-Äquivalent und Turing-vollständig (und Turing-mächtig). I ‚ Ich habe bereits zu viele Fälle gesehen, von Leuten in Message Boards bis zu Forschern in ihren eigenen verdammten ‚ Papieren, die diese Begriffe unterschiedlich interpretieren.
• Wie auch immer, Ich interpretiere ‚ Turing-complete ‚ als Simulation, die einer Universal Turing Machine (UTM; Dies wiederum kann jede Turing-Maschine simulieren – daher ‚ universal ‚). In Turing ‚ s Papier von 1936, in dem er seine Maschinen vorstellte, definierte er den Begriff einer UTM und gab eine Skizze eines Beweises, dass UTMs eine Simulation sind, die der Church ‚ s Lambda-Kalkül. Auf diese Weise bewies er, dass sie die gleiche Rechenleistung hatten. In der Church-Turing-These wird einfach gesagt, dass “ ‚ die gesamte Rechenleistung ist, die Sie ‚ wird jemals “ erhalten.
• Es gibt zwei formale Definitionen für Vollständigkeitsseite von Wikipedia . Eine erfordert E / A, die andere nicht ‚ t. Diejenige, die nicht ‚ sagt, dass eine Maschine vollständig ist, wenn sie jede Turing-berechenbare Funktion berechnen kann. Damit ist die Lambda-Rechnung wieder vollständig, da Sie in der Lambda-Rechnung problemlos ein gleichwertiges Programm erstellen können, das das gleiche wie alle anderen Turing-Maschinenprogramme berechnet.

Sie können nicht sagen, ob es eine Endlosschleife gibt oder stoppt.

————-

Erläuterung: Bei einigen Eingaben ist es unmöglich, in jedem Fall (mit einer anderen Turing-Maschine) zu sagen, ob das Ding eine Endlosschleife durchlaufen oder schließlich anhalten wird, außer durch Ausführen (was Ihnen eine Antwort gibt, wenn dies der Fall ist) stoppen, aber nicht, wenn es Schleifen gibt!).

Dies bedeutet, dass Sie in der Lage sein müssen, eine potenziell unbegrenzte Datenmenge auf irgendeine Weise zu speichern – es muss ein Äquivalent zum unendlichen Band geben, egal wie verschlungen! (Andernfalls gibt es nur eine begrenzte Anzahl von Zuständen, und dann können Sie überprüfen, ob Sie diesen Zustand zuvor durchlaufen haben und schließlich aufhören). Im Allgemeinen können Turing-Maschinen die Größe ihres Zustands auf kontrollierbare Weise vergrößern oder verkleinern.

Da die ursprüngliche universelle Turing-Maschine von Turing ein unlösbares Halteproblem aufweist, muss Ihre eigene Turing-Komplettmaschine auch ein unlösbares Anhalten aufweisen Problem.

Turing-Komplettsysteme können jedes andere Turing-Komplettsystem emulieren. Wenn Sie also einen Emulator für ein bekanntes Turing-Komplettsystem in Ihrem System erstellen können, beweist dies, dass Ihr System auch Turing-Komplettsysteme ist.

Angenommen, Sie möchten beweisen, dass Snakes & Leitern vollständig ist, wenn ein Brett mit einem unendlich wiederholten Gittermuster (mit einer anderen Version oben) vorliegt und linke Seite). Wenn Sie wissen, dass die 2-Zähler-Minsky-Maschine Turing vollständig ist (mit 2 unbegrenzten Zählern und 1 Zustand aus einer endlichen Zahl), können Sie eine äquivalente Karte erstellen, bei der die X- und Y-Position im Raster der aktuelle Wert der 2 Zähler ist und der aktuelle Pfad ist der aktuelle Zustand. Knall! Sie haben gerade bewiesen, dass Schlangen & Leitern vollständig sind.

Kommentare

• Ich habe keine ‚ kaufe dieses Argument nicht. Nur weil das Stoppproblem für Turing-Maschinen unentscheidbar ist, bedeutet dies nicht direkt, dass jede Notation, mit der Sie ein Programm angeben können, für das das Stoppproblem unentscheidbar ist, Turing vollständig ist. Nur die Umkehrung ist offensichtlich wahr: Wenn die Notation Turing vollständig ist, ist es natürlich möglich, Programme zu schreiben, für die das Stoppproblem unentscheidbar ist.
• Es ‚ eine notwendige Bedingung. Wenn Sie für jedes Programm entscheiden können, ob es angehalten wird, lautet die Sprache nicht ‚ t Turing complete.

Eine notwendige Bedingung ist eine Schleife mit einer maximalen Iterationszahl, die nicht vor der Iteration bestimmt wird, oder eine Rekursion, bei der die maximale Rekursionstiefe nicht vorab bestimmt wird. Zum Beispiel sind … in … Schleifen, wie Sie sie in vielen neueren Sprachen finden, nicht genug, um die Sprachprüfung zu vervollständigen (aber sie haben andere Mittel). Beachten Sie, dass dies nicht eine begrenzte Anzahl von Iterationen oder eine begrenzte Rekursionstiefe bedeutet, sondern dass die maximale Iteration und Rekursionstiefe im Voraus berechnet werden muss.

Beispielsweise kann die Ackermann-Funktion nicht in einer Sprache ohne berechnet werden Diese Funktionen Auf der anderen Seite kann eine Menge hochkomplexer und äußerst nützlicher Software geschrieben werden, ohne dass diese Funktionen erforderlich sind.

Andererseits wird nicht nur jede Iterationszahl und jede Rekursionstiefe im Voraus berechnet Kann entschieden werden, ob ein Programm angehalten wird oder nicht, aber es wird angehalten.

Ich weiß, dass dies nicht die formal korrekte Antwort ist, aber wenn Sie das „Minimal“ aus „Turing-complete“ herausnehmen und „praktisch“ wieder dahin bringen, wo es hingehört, werden Sie die wichtigsten Merkmale sehen, von denen sich eine Programmiersprache unterscheidet Eine Auszeichnungssprache sind

• Variablen
• Bedingungen (wenn / dann …)
• Schleife (Schleife / Pause, während …)

next com e

• anonyme und benannte Funktionen

Um diese Behauptungen zu testen, beginnen Sie mit einer Auszeichnungssprache, z. B. HTML. Wir könnten ein HTML + nur mit Variablen oder nur mit Bedingungen (MS hat das mit bedingten Kommentaren gemacht) oder eine Art Schleifenkonstrukt (das ohne Bedingungen wahrscheinlich als <repeat n="4">...</repeat>). Wenn Sie eine dieser Methoden ausführen, wird HTML + erheblich (?) leistungsfähiger als einfaches HTML, aber es wäre immer noch eher ein Markup als eine Programmiersprache. Mit jedem neuen Feature machen Sie es weniger zu einer deklarativen als zu einer imperativen Sprache.

Das Streben nach Minimalität in Logik und Programmierung ist sicher wichtig und interessant, aber wenn ich n00bies jung oder alt beibringen müsste, „was ist Programmieren“ und „wie man Programmieren lernt“, würde ich kaum anfangen Mit der vollen Breite und Breite der theoretischen Grundlagen der Vollständigkeit von Turing. Die ganze Essenz des Kochens und Programmierens besteht darin, Dinge in der richtigen Reihenfolge zu tun und sie zu wiederholen, bis sie fertig sind, wie es deine Mutter getan hat. Das fasst es für mich zusammen / p>

Andererseits habe ich meine CS nie fertiggestellt.

Kommentare

• Wenn Sie sich nicht sicher sind, sollten Sie sie zuerst untersuchen. Fraktran ist vollständig , ebenso wie brainf * ck . Beachten Sie auch, dass HTML 5 + CSS 3 Turing abgeschlossen ist, da es Regel 110 .
• yesyesyes ich weiß. aber alle Beispiele sind mehr oder weniger esoterisch (obwohl vielleicht interessant oder überraschend), m Ihre Antwort war pragmatisch und höchstwahrscheinlich überhaupt nicht minimal. Ich denke, es ist wichtig, ‚ darauf hinzuweisen – diese Seite war die Nummer 1 bei der Suche nach Turing-Vollständigkeit bei Google. Die Antworten hier sind meiner Meinung nach für einen n00bie wenig nützlich Wer möchte wissen, was HTML von PHP oder Python unterscheidet? Ich meine, brainf ck wird nicht ohne Grund brainf ck genannt.