[BuK] Unterprogrammtechnik für {<M1><M2> | L(M1) = L(M2)}

[Matthew]

Hallo,

es geht um den Beweiß, dass folgende Sprache nicht rekursiv ist:
A eq = {<M1><M2> | L(M1) = L(M2)}
In den Musterlösungen wurde immer das Halteproblem ({<M>w | M hält auf w}) angewendet.

Kann man auch das allgemeine Halteproblem für den Beweiß anwenden?
Und zwar so, dass die TM H aus der Eingabe w = <M> einfach <M><M> konstruiert und diese an A eq übergibt?

Dies erscheint mir wesentlich intuitiver und einfacher.
Da ich öfters Fehler bei der Unterprogrammtechnik mache, würde ich mir das hier gerne bestätigen lassen

Grüße
Matthias

[Lanchid]

Prinzipiell ist das möglich, aber nicht so wie du es hier konstruierst.

Kann man auch das allgemeine Halteproblem für den Beweiß anwenden?
Und zwar so, dass die TM H aus der Eingabe w = <M> einfach <M><M> konstruiert und diese an A eq übergibt?

Du willst ja eine Turingmaschine konstruieren, die das Halteproblem löst; dazu benutzt du eine (hypothetische) TM , die entscheidet. Aber L(M) = L(M) ist (trivialerweise) immer erfüllt, also bringt dir die Anwendung von auf <M><M> gar nichts.
Du müsstest aus der Eingabe <M> für das Halteproblem eine Eingabe <M1><M2> konstruieren, sodass <M> auf jeder Eingabe terminiert, wenn L(M1) = L(M2) ist.

Kleiner Tipp: M2 könnte zum Beispiel immer eine Turing-Maschine sein, die jedes Wort akzeptiert...

[Matthew]

Danke.
Stimmt, da man ja einfach die Gödelnummern vergleichen könnte..
Um bei der Idee zu bleiben, wäre es denn möglich wenn ich <M><M'> übergebe, wobei M' zu Beginn den Kopf zunächst nach links und dann wieder nach rechts bewegt?
Die Gödelnummern wären dann unterschiedlich und folglich müssten beide L(M) und L(M') wieder komplett ausgewertet werden.

Oder geht es nur auf deine Weiße, da ich eine Funktionsweiße in der Art "Wenn M auf der Eingabe hält, dann akzeptiert (oder in einem anderen Fall verwirft) M" brauche?

Grüße
Matthias

[Lanchid]

Danke.
Stimmt, da man ja einfach die Gödelnummern vergleichen könnte..
Um bei der Idee zu bleiben, wäre es denn möglich wenn ich <M><M'> übergebe, wobei M' zu Beginn den Kopf zunächst nach links und dann wieder nach rechts bewegt?
Die Gödelnummern wären dann unterschiedlich und folglich müssten beide L(M) und L(M') wieder komplett ausgewertet werden.

Nein, weil du dann wieder zwei Turingmaschinen mit der selben Sprache hättest.
Bei der Unterprogrammtechnik geht es nicht darum, wie tatsächlich arbeitet: Du stellst keine Anforderungen an diese TM, außer dass sie entscheidet. Das heißt, du weißt nicht, ob tatsächlich die Sprachen immer komplett auswertet, oder zum Beispiel nur die Struktur von M1 und M2 analysiert. Du benutzt nur das Ergebnis von , daher musst du die Eingabe so konstruieren, dass nicht immer wahr zurück gegeben wird.

Wenn man mal von Turingmaschinen zu Programmiersprachen geht, wäre der Ansatz bei der Unterprogrammtechnik ist folgender: Du nimmst an, dass du eine Funktion Equality hast, die genau dann true zurück gibt, wenn zwei Turingmaschinen die gleiche Sprache erkennen (Wie sie das genau macht, ist dabei egal; du willst ja zeigen, dass es sie auf keinen Fall geben kann, deswegen nimmst du für diese Funktion so wenig wie möglich an). Du führst die Existenz dieser Funktion zum Widerspruch, indem du eine andere Funktion konstruierst, die das Halteproblem löst, und dabei Equality aufruft.
Das sähe dann ungefähr so aus:

Code: Alles auswählen

bool HaltingProblem(TuringMachine M) {
   TuringMachine* M1, *M2;
   bool eq_result, result;
   /* some code ... */
   eq_result = Equality(M1, M2);
   /* some other code */
   return result;
}


Deine Aufgabe ist es nun, die Kommentarblöcke mit passendem Code zu füllen.
(Wenn du hier M1 und M2 so konstruierst, dass Equality(M1,M2) immer true zurück gibt, dann könntest du eq_result einfach auf true setzen und hättest damit den Bezug zu der "interessanten" Funktion komplett verloren, das geht also nicht)
In BuK benutzt man dazu natürlich die Turingmaschinen, aber prinzipiell geht das genau so. Du wandelst die Eingabe "irgendwie" um, gibst sie an , und interpretierst das Ergebnis.

Oder geht es nur auf deine Weiße, da ich eine Funktionsweiße in der Art "Wenn M auf der Eingabe hält, dann akzeptiert (oder in einem anderen Fall verwirft) M" brauche?

Ich bin mir nicht ganz sicher, was du damit meinst... Kannst du das nochmal etwas weiter ausformulieren?

[Matthew]

Aha, ich bin bis jetzt immer davon ausgegangen das L(M) definitiv ausgewertet wird.
Jetzt erscheint das ganze im ganz neuen Licht

Danke dir, das war der Denkfehler der sich in meinen Konstruktion versteckt hat!