Was macht eine Sprache Turing-complete?

79

Was sind die minimalen Sprachmerkmale / -strukturen, die Turing komplett machen?

Neugierige Katze
quelle
21
Ist es nicht besser, einfach zu googeln? en.wikipedia.org/wiki/Turing_completeness
aml90
2
Hallo neugierige Katze, willkommen zu den Programmierern! Anrufe für Listen sind hier nicht zum Thema: Ich habe diesen Teil aus Ihrer Frage entfernt. Das heißt, diese Suche ist extrem weit gefasst: Gibt es ein spezifisches Problem, an dem Sie arbeiten und das Sie über die Vollständigkeit von Turing nachdenken?
3
@amalantony: Nur als Fußnote .
Bobby
Eine Informatik-Perspektive finden Sie hier .
Raphael

Antworten:

73

Ein Turing-Tarpit ist eine Art esoterische Programmiersprache, die bestrebt ist, Turing-vollständig zu sein und dabei so wenig Elemente wie möglich zu verwenden. Brainfuck ist vielleicht das bekannteste Tarpit, aber es gibt viele.

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

  • OISC ( One Instruction Set Computer ) bezeichnet eine Art von Imperativberechnung, für die nur ein Befehl eines oder mehrerer Argumente erforderlich ist, normalerweise "subtrahieren und verzweigen, wenn sie kleiner oder gleich Null sind" oder "umkehren, subtrahieren und überspringen, wenn sie ausleihen". Die x86-MMU setzt den bisherigen Befehl um und ist damit Turing-komplett.

Im Allgemeinen benötigt eine imperative Sprache Folgendes, um vollständig zu sein:

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

  2. Eine Möglichkeit zum Lesen und Schreiben einer Speicherform (z. B. Variablen, Band)

Damit eine Lambda-Kalkül- basierte funktionale Sprache TC ist, benötigt sie:

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

  2. Die Fähigkeit, Funktionen auf Argumente anzuwenden (zB Reduktion)

Es gibt natürlich auch andere Betrachtungsweisen für Berechnungen, aber dies sind gängige Modelle für Turing-Tarpits. Beachten Sie, dass echte Computer keine universellen Turing-Maschinen sind, da sie keinen unbegrenzten Speicher haben. Streng genommen handelt es sich um „gebundene Speichermaschinen“. Wenn Sie ihnen weiterhin Speicher hinzufügen, nähern sie sich asymptotisch den Turing-Maschinen mit Strom. Sogar begrenzte Speichermaschinen und endliche Zustandsmaschinen sind für die Berechnung nützlich. Sie sind einfach nicht universell .

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

Jon Purdy
quelle
Reichen einfache Variablen für imperative Sprachen aus? Ich hatte den Eindruck, dass eine Art Sammlung (z. B. Arrays oder verknüpfte Listen) notwendig sein würde.
Luiscubal
1
@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 Datenelemente darstellen müssen? Man könnte argumentieren, dass man es mit Tricks wie Fractran-Spielen sogar mit einfachen Variablen machen kann ... aber das ist nicht ganz das, wonach Sie fragen.
Ist es nicht erforderlich, dass die Sprache ENDLESS- Schleifen unterstützt?
Sergiol
Betreff: "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. Aber ich möchte mich hiermit jeder Diskussion entziehen, ob Algol 60 "nützlich" war oder nicht.
Solomon Slow
15

Aus praktischer Sicht: Wenn Sie alle Programme in einer Turing-vollständigen Sprache in Ihre Sprache übersetzen können, muss Ihre Sprache (soweit ich weiß) Turing-vollständig sein. Wenn Sie überprüfen möchten, ob eine von Ihnen entworfene Sprache vollständig ist, können Sie einfach ein Brainf *** an den YourLanguage-Compiler schreiben und nachweisen / demonstrieren, dass es alle zulässigen BF-Programme kompilieren kann.

Zur Verdeutlichung meine ich, 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).

Anton Golov
quelle
11
Ja, das wäre definitiv der praktischste Weg, sich dem anzunähern. </sarcasm>
Robert Harvey
13
@RobertHarvey hat einen Punkt, aber die allgemeine Idee ist sehr wichtig. Brainfuck ist nachweislich vollständig und in allen Programmiersprachen sehr einfach. Für nicht-esoterische Programmiersprachen ist das Implementieren eines Brainfuck-Interpreters möglicherweise viel einfacher und schneller als das Erstellen eines strengen Beweises aus dem Nichts (ich kann BF in einigen Zeilen von Python implementieren, bin mir jedoch nicht sicher, wo ich mit einem formalen beginnen soll Beweis, dass Python vollständig ist); und Dutzende von esoterischen Brainfuck-inspirierten Sprachen sind dafür bekannt, dass sie vollständig sind, weil bekannt ist, wie sie Brainfuck zuordnen.
7
@RobertHarvey: Warum nicht? Sicherlich könnte jemand, der seine eigene Sprache entwirft, einen BF-Compiler dafür schreiben (wenn es unabdingbar ist und ansonsten eine geeignete andere Sprache findet).
Anton Golov
5
@delnan: Sie wird beweisen müssen, jedoch, dass die BF - Interpreter korrekt die BF - Spezifikation implementiert, IOW müssen Sie beweisen , dass Ihr BF - Interpreter ist in der Tat ein BF - Interpreter und nicht ein Dolmetscher für eine BF-ähnliche Sprache , die könnte oder könnte nicht Turing-vollständig sein.
Jörg W Mittag
2
@ DarekNędza, das ist nur eine natürliche Folge der Definition von Turing Completeness. Jede Erweiterung einer Turing Complete-Sprache bleibt weiterhin Turing Complete.
Anton Golov
8

Ein System kann nur dann als vollständig angesehen werden, wenn es alles kann, was eine universelle Turingmaschine kann. Da die universelle Turing-Maschine in der Lage sein soll, jede berechenbare Funktion innerhalb eines bestimmten Zeitraums zu lösen, können Turing-Komplettsysteme dies auch tun.

Um zu überprüfen, ob Turing vollständig ist, können Sie eine Turing-Maschine darin implementieren. Mit anderen Worten, überprü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 Fähigkeit, das Bewegen des Schreib- / Lesekopfs zu simulieren : 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 andere Variablen zu referenzieren. Dies kann häufig in Programmiersprachen unter Verwendung von Array-Datenstrukturen (oder gleichwertigen) oder bei bestimmten Sprachen wie Maschinencode durch Verwendung von "Zeigern" (oder gleichwertigen) zur Referenzierung anderer Variablen simuliert werden.
  3. Die Fähigkeit, eine endliche Zustandsmaschine zu simulieren : Obwohl nicht oft erwähnt, sind Turing-Maschinen tatsächlich eine Variation der endlichen Zustandsmaschinen, die in der AI-Entwicklung häufig verwendet werden. Alan Turing sagte, der Zweck der Staaten sei es, die "verschiedenen Arten der Problemlösung" einer Person zu simulieren.
  4. Ein "Halt" -Zustand : Obwohl oft erwähnt wird, dass ein Satz von Regeln sich wiederholen können muss, um als vollständig zu gelten, ist dies kein wirklich gutes Kriterium, da die formale Definition, was ein Algorithmus ist, immer Zustandsalgorithmen sein muss Schlussendlich. Wenn sie nicht auf irgendeine Weise schließen können, ist entweder Turing nicht vollständig oder der Algorithmus ist keine berechenbare Funktion. Turing-Komplettsysteme, die aufgrund ihrer Funktionsweise (wie beispielsweise Spielekonsolen) technisch nicht abgeschlossen werden können, umgehen diese Einschränkung, indem sie in gewisser Weise einen Haltezustand "simulieren" können. Nicht zu verwechseln mit dem "Halteproblem", eine unentscheidbare Funktion, die es beweist. "

Dies sind die tatsächlichen Mindestanforderungen an ein System, die als vollständig angesehen werden können. 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 bieten.

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

user3067516
quelle
4

Eine Programmiersprache ist vollständig, wenn Sie damit rechnen können. Es gibt nicht nur eine Reihe von Funktionen, die eine vollständige Sprachwiedergabe ermöglichen. Daher sind die Antworten, die besagen, dass Sie Schleifen benötigen oder dass Sie Variablen benötigen, falsch, da es Sprachen gibt, die weder eine noch eine vollständige Sprachwiedergabe haben .

Alan Turing hat die Universal-Turing-Maschine entwickelt. Wenn Sie ein Programm übersetzen können, das für die Ausführung auf der Universal-Maschine entwickelt wurde, ist auch Turing vollständig. Dies funktioniert auch indirekt, so dass 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 räumliche Komplexität, das einfache Eingabe- / Ausgabeformat und das einfache Schreiben von Programmen sind nicht in der Gleichung enthalten, sodass eine solche Maschine theoretisch alle Berechnungen durchführen kann, wenn die Berechnungen nicht durch Leistungsverlust oder durch die Sonne verschluckte Erde gestoppt werden.

Um die Vollständigkeit der Sprache zu beweisen, wird normalerweise ein Dolmetscher für jede nachweislich vollständige Sprache erstellt. Damit dies funktioniert, sind jedoch Ein- und Ausgabemethoden erforderlich, zwei Dinge, die für eine vollständige Sprache eigentlich nicht erforderlich sind. Es ist ausreichend, dass Ihr Programm seinen Status beim Start ändern kann und dass Sie den Speicher nach dem Anhalten des Programms überprüfen können.

Um eine erfolgreiche Sprache zu erstellen, muss sie jedoch mehr als nur vollständig sein. Dies gilt auch für Tarpits. Ich glaube nicht, dass BrainFuck ohne ,und populär gewesen wäre ..

Sylwester
quelle
2
"Eine Programmiersprache ist vollständig, wenn Sie damit rechnen können." Das ist die Church-Turing-These, nicht was eine Sprache Turing-vollständig macht.
Rhymoid
@ Rhymoid Du meinst also, nichts ist vollständig, wenn du keinen Dolmetscher machen kannst? Dh Lambda-Kalkül ist nicht vollständig, auch wenn es gleich ist?
Sylwester
1
Ich bin immer noch auf der Suche nach einer verbindlichen Definition der Begriffe "Turing-Äquivalent" und "Turing-Vollständig" (und "Turing-Mächtig"). 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.
Rhymoid
Wie auch immer, ich interpretiere 'Turing-complete' als Simulation, die einer Universal Turing Machine (UTM) äquivalent ist. Diese wiederum kann jede Turing-Maschine simulieren - daher 'universal'. In Turings Aufsatz von 1936, in dem er seine Maschinen vorstellte, definierte er den Begriff der UTM und skizzierte einen Beweis dafür, dass UTM eine Simulation sind, die der Lambda-Rechnung von Church entspricht. Auf diese Weise bewies er, dass sie die gleiche Rechenleistung hatten. Die These von Church-Turing besagt, einfach ausgedrückt, dass "das die gesamte Rechenleistung ist, die Sie jemals bekommen werden".
Rhymoid
Es gibt zwei formale Definitionen für die Vollständigkeitsseite von Wikipedia . Einer benötigt I / O, der andere nicht. Diejenige, die nicht sagt, dass eine Maschine vollständig ist, wenn sie jede Turing-berechenbare Funktion berechnen kann. Damit ist der Lambda-Kalkül wieder vollständig, da Sie mit dem Lambda-Kalkül auf einfache Weise ein gleichwertiges Programm erstellen können, das dasselbe wie alle anderen Programme für Drehmaschinen berechnet.
Sylwester
4

Sie können nicht sagen, ob es eine Endlosschleife ausführt oder aufhört.

-------------

Erklärung: Bei einigen Eingaben ist es unmöglich in jedem Fall (mit einer anderen Turing-Maschine) zu sagen, ob das Ding eine Endlosschleife durchläuft oder irgendwann anhält, es sei denn, Sie führen es aus (was Ihnen eine Antwort gibt, wenn es anhält, aber nicht wenn es schleifen!).

Das bedeutet, dass Sie in der Lage sein müssen, eine möglicherweise unbegrenzte Menge an Daten zu speichern - es muss ein Äquivalent zum unendlichen Band geben, egal wie verworren! (Andernfalls gibt es nur eine begrenzte Anzahl von Zuständen, und Sie können dann ü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 durch kontrollierbare Mittel vergrößern oder verkleinern.

Da die ursprüngliche Universal-Turing-Maschine von Turing ein unlösbares Anhalteproblem hat, muss auch Ihre eigene Turing-Komplettmaschine ein unlösbares Anhalteproblem haben.

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-Komplettsystem ist.

Angenommen, Sie möchten beweisen, dass Snakes & Ladders vollständig ist, wenn Sie ein Brett mit einem sich unendlich wiederholenden Gittermuster (mit einer anderen Version oben und links) verwenden. Wenn Sie wissen, dass die Minsky-Maschine mit 2 Zählern vollständig ist (mit 2 unbegrenzten Zählern und 1 Zustand aus einer endlichen Zahl), können Sie eine entsprechende Karte konstruieren, bei der die X- und Y-Position auf dem Gitter der aktuelle Wert der 2 Zähler ist und der aktuelle Pfad ist der aktuelle Zustand. Knall! Sie haben gerade bewiesen, dass Snakes & Ladders Turing vollständig sind.

Hubert Lamontagne
quelle
1
Ich kaufe dieses Argument nicht. Nur weil das Problem des Anhaltens für Turing-Maschinen nicht direkt entschieden werden kann, bedeutet dies nicht, dass jede Notation, mit der Sie ein Programm angeben können, für das das Problem des Anhaltens nicht entschieden werden kann, vollständig ist. Nur die Umkehrung ist offensichtlich wahr: Wenn die Notation vollständig ist, ist es natürlich möglich, Programme zu schreiben, für die das Halteproblem unentscheidbar ist.
5gon12eder
Es ist eine notwendige Bedingung. Wenn Sie für jedes Programm entscheiden können, ob es anhält, ist die Sprache nicht vollständig.
gnasher729
4

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 vor der Iteration bestimmt wird. Zum Beispiel reichen für ... in ... -Loops, wie Sie sie in vielen neueren Sprachen finden, nicht aus, um die Sprache vollständig zu machen (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 ohne diese Merkmale nicht in einer Sprache berechnet werden. Andererseits kann eine Menge hochkomplexer und sehr nützlicher Software geschrieben werden, ohne dass diese Funktionen erforderlich sind.

Andererseits kann mit jeder Iterationszahl und jeder vorausberechneten Rekursionstiefe nicht nur entschieden werden, ob ein Programm anhält oder nicht, sondern es wird anhalten.

gnasher729
quelle
-1

Ich weiß, dass dies nicht die formal korrekte Antwort ist, aber wenn Sie das 'Minimum' aus 'Turing-complete' herausnehmen und 'Practical' wieder dorthin setzen, wo es hingehört, werden Sie die wichtigsten Merkmale erkennen, die eine Programmiersprache von einer unterscheiden Auszeichnungssprache sind

  • Variablen
  • Bedingungen (wenn / dann ...)
  • loopage (loop / break, während ...)

als nächstes kommen

  • 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 erfinden (MS tat dies mit bedingten Kommentaren), oder eine Art Schleifenkonstrukt (das ohne Bedingungen wahrscheinlich so etwas wie enden würde <repeat n='4'>...</repeat>). Wenn Sie einen dieser Schritte ausführen, wird HTML + erheblich leistungsfähiger als normales HTML, aber es ist dennoch 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 Programmieren ist und wie man Programmieren lernt, würde ich kaum mit der vollen Breite und Breite anfangen der theoretischen Grundlagen der Turing-Vollständigkeit. Die ganze Essenz des Kochens und Programmierens besteht darin, Dinge in der richtigen Reihenfolge zu tun und sie zu wiederholen, bis sie fertig sind, so wie es deine Mutter getan hat. das fasst es für mich zusammen.

Andererseits habe ich mein CS nie beendet.

fließen
quelle
2
Wenn Sie sich nicht sicher sind, sollten Sie zuerst nachforschen. fractran ist fertig , ebenso wie brainf * ck . Beachten Sie auch, dass HTML 5 + CSS 3 vollständig ist, da es Regel 110 implementieren kann .
1
Ja, ja, ich weiß. Aber alle Beispiele sind mehr oder weniger esoterisch (obwohl sie vielleicht interessant oder überraschend sind). Meine Antwort war pragmatisch und höchstwahrscheinlich überhaupt nicht minimal. Ich denke, es ist wichtig darauf hinzuweisen - diese Seite war die Nr. 1 bei der Suche nach Turing-Vollständigkeit bei Google. Die Antworten hier sind meiner Meinung nach für einen n00bie, der wissen möchte, was HTML von PHP oder Python unterscheidet, von geringem Nutzen. Ich meine, brainf ck heißt nicht ohne Grund brainf ck.
Flow