Turing-Vollständigkeit nachweisen
-
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.
