C/C++ Forum :: Turing-Vollständigkeit nachweisen

Unregistrierter

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!

knivil Mitglied 23:19:59 20.01.2012 Titel:

Zitat:

es gibt keine Kontrollstrukturen, dafür aber Rekursion

Dann ist sie wahrscheinlich nicht turingvollstaendig.

Zitat:

würde gerne die Turing-Vollständigkeit meiner kleinen Programmiersprache nachweisen

Implementiere eine allgemein Turingmaschine.

nachtfeuer Mitglied 23:35:11 20.01.2012 Titel:

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.

Unregistrierter

knivil schrieb:

Zitat:

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.

Zitat:

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.

µ Mitglied 13:09:23 21.01.2012 Titel:

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-Programm

Labels, Variablen, Inkrementieren, Dekrementieren, bedingte Sprünge. Mehr braucht's nicht :eek:

GyroGearloose Mitglied 14:26:19 21.01.2012 Titel:

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.de/forum/292057

Unregistrierter

µ schrieb:

http://de.wikipedia.org/wiki/WHILE-Programm

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.

µ Mitglied 15:01:30 21.01.2012 Titel:

@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.

Prof84 Mitglied 15:04:13 21.01.2012 Titel:

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%C3%A4t
http://de.wikipedia.org/wiki/Zellul%C3%A4re_Automaten
http://de.wikipedia.org/wiki/Boltzmann

µ Mitglied 15:10:33 21.01.2012 Titel:

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?

Bashar Mitglied 15:14:15 21.01.2012 Titel:

µ 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

Prof84 Mitglied 15:15:23 21.01.2012 Titel:

µ 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

µ Mitglied 15:18:37 21.01.2012 Titel:

Und du hast den Ausdruck "durch und nur durch" nicht verstanden.

Prof84 Mitglied 15:29:45 21.01.2012 Titel:

µ schrieb:

Und du hast den Ausdruck "durch und nur durch" nicht verstanden.

So? Dann erklär es mir.

µ Mitglied 19:39:50 21.01.2012 Titel:

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.

Ben04 Autor 00:58:51 22.01.2012 Titel:

Wenn ich das richtig im Kopf habe, dann kannst du alternativ auch das Lambda-Kalül nachbauen um Turingmächtigkeit zu zeigen.

Unregistrierter

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.