blatt #6

[wurstus]

hi,

geh ich bei der nummer eins richtig davon aus,

dass es 2 fälle gibt?

also einmal M1 != M2 und einmal M1 == M2 ?

greez patrick

[Patric]

M1 == M2 wär ja irgendwie zu einfach,
ich glaube die wollen schon M1 != M2

[DavidHume]

ich glaube die wollen schon M1 != M2

Das wäre eine sehr gute Frage für offizielles Forum!

[Thomas]

Ich hätte mal ne Idee zur Aufgabe:

PRIME_BBCODE_SPOILER_SHOW PRIME_BBCODE_SPOILER: auf Anzeigen klicken

Und zwar definiert man sich 2 Funktionen t1 und t2 mit:
t1(<M2>, w) = <M2>
und t2(<M1>,w) = <M1>

Dann gibt es ja nach dem Rekursiontheorem jeweils eine TM R1 mit einer Funktion r1(w) = t1(<M2>, w) = <M2>
bzw R2 mit einer Funktion r2(w) = t2(<M1>,w) = <M1>
Definiert man sich jetzt M1 so, dass M1 r1 berechnet und M2 r2 berechnet, würde M1 immer <M2> und M2 immer <M1> ausgeben

Eine 2. Möglichkeit sehe ich in der 2. Version des Rekursionstheorems der VL:
Man definiert sich eine Funktion t mit t(<M1>) = <M2> und t(<M2>) = <M1>

Dann holt sich M1 seine eigene Gödelnummer, was ja möglich ist, berechnet t und gibt das Ergebnis aus.
M2 verfährt dann genau so.
Hab aber keine Ahnung, ob das so geht, was meint ihr?

[angel]

also ich hatte die selbe idee....

[Thomas]

hat zufällig schon jemand was zur 2. aufgabe, find mich da noch nicht wirklich zu recht...

[elTybbq]

kann man bei der 2) nicht einfach denselben Beweis bringen, der in der VL für die ganze Menge benutzt wurde? Weil die Teilmenge ja auch unendlich sein soll...

[Johann]

Eine 2. Möglichkeit sehe ich in der 2. Version des Rekursionstheorems der VL:
Man definiert sich eine Funktion t mit t(<M1>) = <M2> und t(<M2>) = <M1>

Dann holt sich M1 seine eigene Gödelnummer, was ja möglich ist, berechnet t und gibt das Ergebnis aus.
M2 verfährt dann genau so.
Hab aber keine Ahnung, ob das so geht, was meint ihr?

Ich hab gerade versucht, das nachzuvollziehen, allerdings seh ich nicht ganz den Bezug zur 2. Version des Rekursionstheorems. Die "2. Version" ist soweit ich das verstehe doch nur die Aussage, dass es Fixpunkte gibt. Wir haben eine beliebige (berechenbar) Funktion. Dann gibt es eine Turingmaschine, die unter Anwendung von t() wieder die Turingmaschine selbst (genauer: eine äquivalente) ausgibt, also eben ein Fixpunkt der Abbildung. Also: Für eine berechenbare Funktion t() gilt: Es gibt ein M so dass: t(<M>) = <M>. Was genau hat das hier mit dem Beweis zu tun?

Edit: Mein Ansatz für die 1:

PRIME_BBCODE_SPOILER_SHOW PRIME_BBCODE_SPOILER: auf Anzeigen klicken

M1 = P(<M2>)

M2 = 1. Eigene Codierung <M2> per RT erhalten 2. q(<M2>) = <P(<M2>)> = <M1> berechnen 3. <M1> ausgeben

kann man bei der 2) nicht einfach denselben Beweis bringen, der in der VL für die ganze Menge benutzt wurde? Weil die Teilmenge ja auch unendlich sein soll...

Hab ich mir auch überlegt, allerdings ist es eine Teilmenge, ich bin mir nicht sicher ob garantiert ist, dass dann auch für eine beliebige Turingmaschine jemals eine größere gefunden wird, da ja sein kann, dass sie gerade nicht in dieser Teilmenge ist. Hat da jemand sonst noch eine Idee? <- Das war Blödsinn. Wir suchen ja lediglich eine größere. Da unsere suchende TM C ja endlicher Länge ist, MUSS es eine größere geben. Damit dürfte allerdings die gefundene nicht in der Teilmenge sein, da sie keine minimale TM ist. Ich glaube das funktioniert also schon identisch!

[DavidHume]

M1 = P(<M2>)

Was ist P?

[Johann]

Das ist die Turingmaschine, die das Wort <M2> ausgibt (das <M2> sollte im Index stehen, ich habs ausdrückt als sei es eine Funktion, nicht ganz richtig). Im Sipser war das mit der Funktion q(), also q(<M1>) = <P(<M1>)> = Code einer TM, die <M1> in einer Tabelle hartkodiert enthält und ausgibt. Danke für den Hinweis, das hab ich oben in der Lösung nicht korrekt ausgedrückt!