Turing-Vollständigkeit nachweisen
-
Hallo, ich würde gerne die Turing-Vollständigkeit meiner kleinen Programmiersprache nachweisen. Vom Prinzip her ist sie so ähnlich wie die constexpr-Funktionen von C++ (jede Funktion ist ein Einzeiler, d.h. es gibt keine Kontrollstrukturen, dafür aber Rekursion).
Weiss jemand, wie man da am besten vorgeht bzw. wo das Vorgehen erklärt wird? Im Internet konnte ich dazu nichts Verständliches finden.
Vielen Dank!
-
es gibt keine Kontrollstrukturen, dafür aber Rekursion
Dann ist sie wahrscheinlich nicht turingvollstaendig.
würde gerne die Turing-Vollständigkeit meiner kleinen Programmiersprache nachweisen
Implementiere eine allgemein Turingmaschine.
-
Ich meine, hier ist auch ein wenig geschichtliches Zusammenhangsverständis hilfreich.
Wikipedia bietet eine ganze Reihe Hinweise zum Thema
u.a.http://de.wikipedia.org/wiki/Hilbertprogramm
http://de.wikipedia.org/wiki/Turingmaschine
http://de.wikipedia.org/wiki/Turing-Vollständigkeit
http://de.wikipedia.org/wiki/Entscheidbar
http://de.wikipedia.org/wiki/Gödelscher_Vollständigkeitssatz
usw.
Und vielleicht auch mal lesen, was Turing selber im Zusammenhang geschrieben hatte.
-
knivil schrieb:
es gibt keine Kontrollstrukturen, dafür aber Rekursion
Dann ist sie wahrscheinlich nicht turingvollstaendig.
Sie hat auch sowas wie SFINAE in C++ oder Patterns in Haskell. Also quasi ein if. Und beliebig grosse Felder hat sie auch.
Implementiere eine allgemein Turingmaschine.
Wie ich nur übersehen konnte, dass eine allgemeine Turingmaschine ein Turingmaschineninterpreter ist ... danke, das hilft schon mal. Die paar, die ich mir schon angesehen habe, waren unglaublich kompliziert, jetzt habe ich aber eine einfachere in Haskell gefunden. Werde es damit mal versuchen.
Ich dachte halt, es wäre leichter zu zeigen, äquivalent zu irgendeiner anderen Sprache (oder einem Subset davon) zu sein anstatt sich direkt mit Turing herumzuschlagen. Zuerst wollte ich einen Brainfuck-Interpreter schreiben, das ist mir aber zu umständlich vorgekommen.
nachtfeuer schrieb:
Ich meine, hier ist auch ein wenig geschichtliches Zusammenhangsverständis hilfreich.
Geschichtlich ist das sehr interessant und da habe ich auch einen groben Überblick. Als Noch-nicht-Student fehlt es mir allerdings noch etwas an Mathematik um die grundlegenden Beweise zu verstehen.
-
klein-thüring schrieb:
Ich dachte halt, es wäre leichter zu zeigen, äquivalent zu irgendeiner anderen Sprache (oder einem Subset davon) zu sein anstatt sich direkt mit Turing herumzuschlagen.
Du musst dich nicht mit Turing-Maschinen rumschlagen. Du kannst auch zeigen, dass Du die Konstrukte von While- oder Goto-Programmen nachbilden kannst.
http://de.wikipedia.org/wiki/WHILE-Programm
http://de.wikipedia.org/wiki/GOTO-ProgrammLabels, Variablen, Inkrementieren, Dekrementieren, bedingte Sprünge. Mehr braucht's nicht
-
klein-thüring schrieb:
Zuerst wollte ich einen Brainfuck-Interpreter schreiben, das ist mir aber zu umständlich vorgekommen.
Das ist gar nicht so umständlich bzw. schwer, wie man vielleicht denkt. Siehe dazu hier: http://www.c-plusplus.net/forum/292057
-
µ schrieb:
Super, so etwas hatte ich gesucht. Damit ist es ganz leicht.
Vielleicht sollte ich doch etwas häufiger die deutsche Wikipedia anschauen.Jedenfalls: Problem gelöst.
@GyroGearloose: lol, vielleicht versuch ich es jetzt doch.
-
@klein-thüring
Prima
Möchtest Du Deine kleine Sprache hier vielleicht mal ein wenig näher Beschreiben und auch das eine oder andere Beispiel vorstellen? Vielleicht auch wie Du den Parser und Interpreter/Compiler umgesetzt hast.
-
nachtfeuer schrieb:
Ich meine, hier ist auch ein wenig geschichtliches Zusammenhangsverständis hilfreich.
Wikipedia bietet eine ganze Reihe Hinweise zum Thema
u.a.http://de.wikipedia.org/wiki/Hilbertprogramm
http://de.wikipedia.org/wiki/Turingmaschine
http://de.wikipedia.org/wiki/Turing-Vollständigkeit
http://de.wikipedia.org/wiki/Entscheidbar
http://de.wikipedia.org/wiki/Gödelscher_Vollständigkeitssatz
usw.
Und vielleicht auch mal lesen, was Turing selber im Zusammenhang geschrieben hatte.http://de.wikipedia.org/wiki/Chomsky-Hierarchie
@OTE:
Eigentlich genügt es die Gültigkeit der Axiome des Typ-0 zu beweisen, was allerdings nicht trivial ist.http://de.wikipedia.org/wiki/Gregory_Chaitin
http://de.wikipedia.org/wiki/Claude_Shannon
http://de.wikipedia.org/wiki/Kolmogorow-Komplexität
http://de.wikipedia.org/wiki/Zelluläre_Automaten
http://de.wikipedia.org/wiki/Boltzmann
-
Prof84 schrieb:
Eigentlich genügt es die Gültigkeit der Axiome des Typ-0 zu beweisen, was allerdings nicht trivial ist.
Du schlägst jetzt aber nicht vor nachzuweisen, dass seine Sprache durch und nur durch eine Typ-0 Grammatik beschrieben werden kann, oder?
-
µ schrieb:
Prof84 schrieb:
Eigentlich genügt es die Gültigkeit der Axiome des Typ-0 zu beweisen, was allerdings nicht trivial ist.
Du schlägst jetzt aber nicht vor nachzuweisen, dass seine Sprache durch und nur durch eine Typ-0 Grammatik beschrieben werden kann, oder?
Nein, dass man in seiner Sprache jede Typ-0-Sprache parsen (bzw. erzeugen) kann. Etwas weltfremder Vorschlag
-
µ schrieb:
Prof84 schrieb:
Eigentlich genügt es die Gültigkeit der Axiome des Typ-0 zu beweisen, was allerdings nicht trivial ist.
Du schlägst jetzt aber nicht vor nachzuweisen, dass seine Sprache durch und nur durch eine Typ-0 Grammatik beschrieben werden kann, oder?
Nö! - Dann hättest Du die Hierarchie nicht verstanden.
http://de.wikipedia.org/w/index.php?title=Datei:Chomsky-Hierarchie.svg&filetimestamp=20110715183925
-
Und du hast den Ausdruck "durch und nur durch" nicht verstanden.
-
µ schrieb:
Und du hast den Ausdruck "durch und nur durch" nicht verstanden.
So? Dann erklär es mir.
-
Prof, bitte. Stell' Dich nicht noch dümmer als Du eh schon bist.
"dann wenn", "wenn dann", "nur dann wenn", "dann und nur dann wenn" ... übertragen sie nun das Gelernte in den Kontext der aktuellen Problemstellung.
Das ist eigentlich auch alles vollkommen unerheblich, falls Du es wirklich so gemeint hast wie von Bashar erklärt. Aber bei der gewohnten Mischung aus Link-Shitstorm und Buzzword-Halbwissen musste ich nachfragen.
-
Wenn ich das richtig im Kopf habe, dann kannst du alternativ auch das Lambda-Kalül nachbauen um Turingmächtigkeit zu zeigen.
-
Prof84 schrieb:
@OTE:
Eigentlich genügt es die Gültigkeit der Axiome des Typ-0 zu beweisen, was allerdings nicht trivial ist.Da passt doch was nicht zusammen? Du leitest den Satz ein, als ob du eine einfache Möglichkeit kennst, dann endest du ihn aber mit dem Hinweis, dass das nicht trivial, also schwer ist.
