blatt #6
Re: blatt #6
M1 == M2 wär ja irgendwie zu einfach,
ich glaube die wollen schon M1 != M2
ich glaube die wollen schon M1 != M2
Re: blatt #6
Das wäre eine sehr gute Frage für offizielles Forum!Patric hat geschrieben: ich glaube die wollen schon M1 != M2
-
- Administrator
- Beiträge: 383
- Registriert: Do 23. Okt 2008, 20:16
- Wohnort: Karlsruhe
- Kontaktdaten:
Re: blatt #6
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?
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?
Re: blatt #6
also ich hatte die selbe idee....
-
- Administrator
- Beiträge: 383
- Registriert: Do 23. Okt 2008, 20:16
- Wohnort: Karlsruhe
- Kontaktdaten:
Re: blatt #6
hat zufällig schon jemand was zur 2. aufgabe, find mich da noch nicht wirklich zu recht...
Re: blatt #6
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...
Re: blatt #6
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?Thomas hat geschrieben: 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?
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
M2 = 1. Eigene Codierung <M2> per RT erhalten 2. q(<M2>) = <P(<M2>)> = <M1> berechnen 3. <M1> ausgeben
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!elTybbq hat geschrieben: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...
Zuletzt geändert von Johann am Mi 9. Dez 2009, 04:21, insgesamt 1-mal geändert.
338364: <Alanna> Saying that Java is nice because it works on all OS's is like saying that anal sex is nice because it works on all genders
Re: blatt #6
Was ist P?M1 = P(<M2>)
Re: blatt #6
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!
338364: <Alanna> Saying that Java is nice because it works on all OS's is like saying that anal sex is nice because it works on all genders