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

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.