Was sind praktische Richtlinien für die Bewertung der „Vollständigkeit“ einer Sprache?

https://stackoverflow.com/questions/449014

19-08-2019
|

Frage

Ich habe gelesen "Was-is-Turing-Complete" Und die Wikipedia -Seite, aber ich interessiere mich weniger für einen formellen Beweis als an den praktischen Auswirkungen, um vollständig zu turenden.

Ich versuche tatsächlich zu entscheiden, ob die Spielzeugsprache, die ich gerade entworfen habe, als allgemeine Sprache verwendet werden könnte. Ich weiß, dass ich beweisen kann, dass ich damit eine Turing -Maschine schreiben kann. Aber ich möchte diese Übung nicht durchlaufen, bis ich mich ziemlich sicher bin.

Gibt es eine Mindestfunktion, ohne dass die Vollständigkeit der Turing unmöglich ist? Gibt es eine Reihe von Funktionen, die die Vollständigkeit praktisch garantiert?

(Ich vermute, diese bedingte Verzweigung und ein lesbarer/schriftlicher Speicher bringen mich den größten Teil des Weges dorthin.)

BEARBEITEN:

Ich glaube, ich habe eine Tangente gemacht, indem ich "vollständig" gesagt habe. Ich versuche mit vernünftigem Vertrauen zu erraten, dass eine neu erfundene Sprache mit einem bestimmten Feature -Set (oder abwechselnd eine VM mit einem bestimmten Anweisungssatz) alles berechnen könnte, was es wert ist, Computer zu berechnen. Ich weiß, dass Sie beweisen können, dass Sie eine Turing -Maschine damit bauen können, ist ein Weg, aber nicht der einzige Weg.

Was ich gehofft hatte, war eine Reihe von Richtlinien wie: "Wenn es x, y und z tun kann, kann es wahrscheinlich mach alles ".

Lösung

Sie benötigen irgendeine Form von dynamischem Allokationskonstrukt (malloc odernew oder cons wird tun) und entweder rekursive Funktionen oder eine andere Möglichkeit, eine unendliche Schleife zu schreiben. Wenn Sie diese haben und überhaupt etwas Interessantes tun können, sind Sie mit ziemlicher Sicherheit abgeschlossen.

Der Lambda Calculus entspricht einer Turing -Maschine. Wenn Sie Lambda Calculus implementieren, macht es eigentlich ziemlich viel Spaß, Lambda Calculus -Programme zu schreiben. Weg Mehr Spaß als das Schreiben von Programm für eine Turing -Maschine!

Die einzige praktische Implikation der Turing-Vervollständigung, die mir bekannt ist, ist, dass Sie Programme schreiben können, die nicht enden. Ich habe ein paar Spezialsprachen verwendet, die die Kündigung garantieren und daher sind nicht Turing-Complete. Manchmal ist es nützlich, die zusätzliche Ausdruckskraft im Austausch für garantierte Kündigungen aufzugeben.

Andere Tipps

"Vollständigkeit" beschreibt die Eigenschaft, beliebige willkürliche Ausdruck zu machen Algorithmische Berechnung, Welches war der Punkt von Turings Maschine an erster Stelle. Ein Sprache oder ein logisches System kann als "vollständig" beschrieben werden, wenn es diese Eigenschaft hat. Aus praktischer Sicht können alle allgemeinen Programmiersprachen - und eine überraschend große Anzahl von speziellen Zwecken - dies für eine angemessen lose Definition tun (siehe unten).

Eine strenge Definition der Vollständigkeit impliziert jedoch unendliche Speicherkapazität, was natürlich nicht physisch möglich ist. In Anbetracht dessen kann möglicherweise keine physische Maschine vollständig abgeschlossen werden, aber diese Einschränkung wird normalerweise (zumindest informell) entspannt, wenn es einer Programmiersprache die Vollständigkeit der Vollständigkeit zuschreibt. Ein trivialer Test für die Vollständigkeit einer Sprache ist, ob die Sprache zur Implementierung eines Turing -Maschinensimulators verwendet werden kann.

Ein Beispiel für ein weit verbreitetes System, das nicht vollständig abgeschlossen ist Ein relationales Modell für große gemeinsame Datenbanken. Die relationale Algebra hat das Eigentum von Godel Vollständigkeit, was bedeutet, dass es jede Berechnung ausdrücken kann, die in Bezug auf definiert werden kann Prädikat erster Ordnung (dh gewöhnliche logische Ausdrücke). Es ist jedoch nicht vervollständigt, da es keine willkürliche algorithmische Berechnung ausdrücken kann.

Beachten Sie, dass die meisten, wenn nicht alle praktischen SQL -Dialekte das reine relationale Modell mit prozeduralen Konstrukten so weit erweitern, dass sie durch die Definition abgeschlossen sind, die normalerweise für Programmiersprachen angewendet werden. Eine einzelne SQL -Abfrage im Großen und Ganzen ist jedoch nicht.

Einige ungeheuerlichere Beispiele für die vollständigen domänenspezifischen Sprachen sind Tex und sendmail.cf,. Im letzteren Fall gibt es tatsächlich ein berühmtes Beispiel für jemanden, der sendmail.cf zu benutzt Implementieren Sie einen universellen Turing Machine -Simulator.

Wenn Sie a schreiben können Brainf $ &# Interpreter in Ihrer Sprache, es ist eine Turing-Complete. Lolcode Es wurde erwiesen, dass es genau auf diese Weise zu vervollständigen ist.

Beispiele für Sprachen, die nicht häufig zu vervollständigen sind begrenzte Schleifen, wie:

for i=1 to N {...}

Aber Mangel ungebunden Schleifen, die einen allgemeineren Zustand überprüfen, wie:

while bool_expr {...}

Wenn alle möglichen Schleifenkonstrukte begrenzt sind, wird Ihr Programm garantiert beendet. Und obwohl eine bedingungslose Kündigungsgarantie potenziell nützlich ist, ist es auch ein Hinweis darauf, dass die Sprache nicht abgeschlossen ist.

Beachten Sie auch, dass das Nageln abnagelt alles möglich Looping -Konstrukte können schwierig sein; Ich bin mir ziemlich sicher, dass C ++-Vorlagen nicht als Turing-Vervollständigung gedacht waren ...

Ich bin mir nicht sicher, ob es "Mindestfunktionen" gibt, aber um zu beweisen, dass eine Sprache vollständig ist, müssen Sie nur beweisen, dass sie ein anderes Turing -vollständiges System (nicht unbedingt eine Turing -Maschine) nachahmen kann, solange das Es ist bekannt, dass ein anderes System vollständig ist. http://en.wikipedia.org/wiki/turing_complete#examples hat eine ganze Liste von Turing Complete Systems. Einige von ihnen sind einfacher als Turing -Maschinen.

Ich möchte dem, was Norman Ramsey sagte, einen Einschränkung hinzufügen: Eine Turing -Maschine hat unendlichem Gedächtnis, und daher sind die Programmiersprachen, die als vollständig angesehen werden, nur unter der Annahme, dass das Gedächtnis auch unendlich ist.

Brainfuck ist vollständig und verfügt nur über Schleifenstrukturen und Speicherinkrementierung/-Delementierung, so dass dies ausreicht.

Andererseits gibt es keine Möglichkeit, einen Wert im Lambda -Kalkül zu ändern, aber es ist vollständig, sodass es eindeutig möglich ist, dies ohne veränderlichem Speicher zu tun.

Höchstwahrscheinlich hat Ihr Programm nichts mit dem Lambda -Kalkül zu tun, daher muss das Minimum für eine praktische Antwort sein

Eine Möglichkeit, in eine Variable zu schreiben
Eine Möglichkeit, eine Variable zu lesen
Eine Form der bedingten GOTO (falls Anweisung, während der Schleife usw.)

Ich kann mich nicht erinnern, so etwas zu sehen Mindestmerkmale zur Vollständigkeit der Turing. Wenn Ihre Sprache jedoch Schleifen und bedingte Zweige unterstützt, ist die Wahrscheinlichkeit, dass sie vollständig ist, gut. Der einzige Weg, um es zu beweisen, besteht jedoch immer noch darin, eine Turing -Maschine oder eine andere Turing -vollständige Sprache zu similieren.

Wenn Sie eine Turing -Maschine implementieren können (soweit sie implementiert werden können, da sie mathematische Konstrukte mit unbegrenztem Speicher sind [die Klebebandgröße ist infiziert]) können Sie sicher sein, dass sie vollständig ist.

Einige Hinweise:

Sie können den Speicher überprüfen und basierend auf dem aktuellen Wert bearbeiten und den Programmfluss steuern.
Dieser Speicher kann Speicher zugewiesen werden, Zeichenfolgen, an die Sie anhängen können, einen Stapel, auf den Sie Speicher durch Rekursion usw. zuweisen können.
Der Programmfluss kann durch Iteration oder durch ausgewählte Rekursion erfolgen.

Jede Sprache, die nicht terminiert werden kann, ist so ziemlich vollständig. Sie können eine nicht terminierende Sprache in der Lage machen, sie unbegrenzte Schleifenstrukturen zu geben (wie während Schleifen oder ein Goto, das sich selbst wieder erreichen kann) oder indem sie ihr allgemeiner Rekursion geben (indem sie sich eine Funktion ohne Einschränkung anrufen lassen).

Wenn du sind Turing Complete können Dinge wie andere Turing -vollständige Sprachen, einschließlich Ihrer eigenen, interpretieren.

Die eigentliche Frage ist "Was nützt es?" Wenn Ihre Sprache in einer bestimmten Domäne verwendet wird, um bestimmte Probleme zu lösen, ist es möglicherweise besser, einen Weg zu finden, um die Lösungen in einer Sprache zu formulieren, die nicht vollständig ist, und somit garantiert eine Antwort geben.

Sie können immer die Vollständigkeit hinzufügen, indem Sie "Tun Sie dies, oder was auch immer; aber mit dem von x" bereitgestellten Ergebnis in jeder anderen Turing-vollständige Sprache, in der X durch eine nicht-Turing-vollständige Sprache bereitgestellt wird.

Natürlich, wenn Sie nur eine Sprache verwenden möchten, war es natürlich besser zu vollständigen ...

Sie können versuchen, eine zu emulieren Oisc (Ein Anweisungscomputer). Wenn Sie eine der Anweisungen dort nachahmen können, dann haben Sie nachgewiesen, dass Ihre Sprache auch vollständig abgeschlossen sein muss.

Gibt es eine Mindestfunktion, ohne dass die Vollständigkeit der Turing unmöglich ist? Gibt es eine Reihe von Funktionen, die die Vollständigkeit praktisch garantiert?

Ja, Sie müssen den Kontrollfluss auf Daten bedingt haben: Was wird oft ausgedrückt als if. Zum Beispiel a +-*/ Taschenrechner ist nicht abgeschlossen, da es keine Möglichkeit gibt, Bedingungen auszudrücken.

Sie müssen auch in der Lage sein, einen Sprung zurück zu einem früheren Punkt im Programm auszudrücken, über den Sie eine Schleife implementieren können. Zum Beispiel ist BPF, das rückwärts den Sprüngen verbietet, um zu garantieren, dass das Programm endet, auch nicht vollständig.

Sie benötigen einen Speicher, der sowohl lesbar als auch beschreibbar und willkürlich groß ist. Beispielsweise ist eine Sprache mit nur zwei 32-Bit-Variablen in dem, was sie berechnen kann, begrenzt. Sie haben viele Möglichkeiten, wie der Speicher strukturiert ist: Speicher wird von Zeigern, Arrays, Stapeln, Cons -Zellen, reinen Datenstrukturen usw. angesprochen.

Darüber hinaus können Sie jede andere Programmiersprache erstellen: Es ist vielleicht nicht einfach oder schnell, aber es reicht aus.

... als in den praktischen Auswirkungen, um vollständig zu turenden.

Ich bezweifle, dass es praktische Auswirkungen auf die vollständige Verfassung gibt.

Wenn Sie sich einige der Beispiele für Turing -komplette Maschinen ansehen, z. B. das Original Turing Maschine, Sie werden sehen, dass es so weit davon entfernt ist, für reale Berechnungen nützlich zu sein, dass das Konzept nur von theoretischen Interesse sein darf.

Lizenziert unter: CC-BY-SA mit Zuschreibung

Nicht verbunden mit StackOverflow