Seite 1 von 1
Aufgabe 13.1
Verfasst: Do 5. Feb 2009, 10:06
von Christian S.
Hallo,
Ich bin mir hier nicht ganz sicher, was zu tun ist. Momentan habe ich folgende Ansätze:
a) Die Turingmaschine wird als Abfolge von {[, ], 0, 1} codiert. Diese Codierung wird dann umgewandelt, indem die Klammern z.B. die Werte 7 und 8 erhalten. Das Ergebnis entsteht dann durch Konkatenation der Werte, was ja eine Zahl € N0 ist, oder?
b) Hier habe ich dieses h(n)(n) als ein (g~)(n) interpretiert, also das hintere n als Funktionswert und dann in die Gleichung eingesetzt.
c) Hier habe ich mithilfe von modulo eine Funktion bestimmt, die immer auf andere Werte abbildet.
Viele Grüße,
Christian
Re: Aufgabe 13.1
Verfasst: Do 5. Feb 2009, 14:27
von elTybbq
zur c)
Denke mal, das soll man so machen wie in der b) beschrieben. Also f(n) := 1 - b(T)(n). Dann ist f != b(T)
Re: Aufgabe 13.1
Verfasst: Do 5. Feb 2009, 15:16
von Christian S.
elTybbq hat geschrieben:zur c)
Denke mal, das soll man so machen wie in der b) beschrieben. Also f(n) := 1 - b(T)(n). Dann ist f != b(T)
Hast recht, kommt aber auf das gleiche raus wie wenn ich das mit mod 2 ausdrücke.
Re: Aufgabe 13.1
Verfasst: Fr 6. Feb 2009, 03:05
von SLS
elTybbq hat geschrieben:zur c)
Denke mal, das soll man so machen wie in der b) beschrieben. Also f(n) := 1 - b(T)(n). Dann ist f != b(T)
Ich glaube, so genau stimmt das
nicht! Was ist nämlich f(2) ? Wie soll ich das ausrechnen nach dieser Definition, wenn dieses T für mich nichts bedeutet an der Stelle?
Mein Vorschlag:
1. Zunächst alle Turingmaschinen durchnummerieren (etwa durch 13.1a))
2. Erst dann
 := 1 - (b(T_n))(n))
setzen. (Beachte den Index bei T)
Es ist dann zu zeigen:
 \neq f)
Also:
)(n) \neq f(n))
Beweisen kann man die Eigenschaft von f folgendermassen:
Sei
beliebig und habe die Nummer
.
Man zeigt (sehr leicht), dass die Funktionen
und
=b(T_n))
für das Argument
unterschiedliche Werte haben, und somit ungleich sind.
Da T beliebig war, gilt das für alle T
Re: Aufgabe 13.1
Verfasst: Fr 6. Feb 2009, 08:17
von Christian S.
SLS hat geschrieben:elTybbq hat geschrieben:zur c)
Denke mal, das soll man so machen wie in der b) beschrieben. Also f(n) := 1 - b(T)(n). Dann ist f != b(T)
Ich glaube, so genau stimmt das
nicht! Was ist nämlich f(2) ? Wie soll ich das ausrechnen nach dieser Definition, wenn dieses T für mich nichts bedeutet an der Stelle?
Dazu folgendes: f(2) wäre dann 1 - (b(T))(2). Das b(T) ist eine Funktion, die auf 0 oder 1 abbildet. Also bildet diese Funktion an der Stelle 2 und an jeder weiteren Stelle auf 0 oder 1 ab. Somit ist f(x) immer dann 0, wenn b(t)(n) = 1 und immer 1, wenn b(t)(n) = 0.
Re: Aufgabe 13.1
Verfasst: Fr 6. Feb 2009, 12:44
von SLS
Christian S. hat geschrieben:
Dazu folgendes: f(2) wäre dann 1 - (b(T))(2). Das b(T) ist eine Funktion, die auf 0 oder 1 abbildet. Also bildet diese Funktion an der Stelle 2 und an jeder weiteren Stelle auf 0 oder 1 ab. Somit ist f(x) immer dann 0, wenn b(t)(n) = 1 und immer 1, wenn b(t)(n) = 0.
MfG
Re: Aufgabe 13.1
Verfasst: Fr 6. Mär 2009, 16:01
von localhorst
zu c): Ist das Problem bei den Ansätzen (und auch bei der Musterlösung) nicht dass die Quantoren vertauscht werden? Also nicht:
"Es gibt eine Funktion, für die gilt: Für alle Turingmaschienen gilt: b(T) != f"
sondern
"Für alle Turingmaschienen gilt: Es gibt eine Funktion, für die gilt: b(T) != f"
In der Musterlösung hängt ja |d von b(T) ab, also gibt es nicht eine für jedes b sondern eine für jedes b und jedes T..