Aufgabe 13.1

[Christian S.]

Hallo,
Ich bin mir hier nicht ganz sicher, was zu tun ist. Momentan habe ich folgende Ansätze:

PRIME_BBCODE_SPOILER_SHOW PRIME_BBCODE_SPOILER: auf Anzeigen klicken

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

[elTybbq]

zur c)

PRIME_BBCODE_SPOILER_SHOW PRIME_BBCODE_SPOILER: auf Anzeigen klicken

Denke mal, das soll man so machen wie in der b) beschrieben. Also f(n) := 1 - b(T)(n). Dann ist f != b(T)

[Christian S.]

zur c)

PRIME_BBCODE_SPOILER_SHOW PRIME_BBCODE_SPOILER: auf Anzeigen klicken

Denke mal, das soll man so machen wie in der b) beschrieben. Also f(n) := 1 - b(T)(n). Dann ist f != b(T)

PRIME_BBCODE_SPOILER_SHOW PRIME_BBCODE_SPOILER: auf Anzeigen klicken

Hast recht, kommt aber auf das gleiche raus wie wenn ich das mit mod 2 ausdrücke.

[SLS]

zur c)

PRIME_BBCODE_SPOILER_SHOW PRIME_BBCODE_SPOILER: auf Anzeigen klicken

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:

PRIME_BBCODE_SPOILER_SHOW PRIME_BBCODE_SPOILER: auf Anzeigen klicken

1. Zunächst alle Turingmaschinen durchnummerieren (etwa durch 13.1a))
2. Erst dann setzen. (Beachte den Index bei T)

Es ist dann zu zeigen:
Also:
Beweisen kann man die Eigenschaft von f folgendermassen:
Sei beliebig und habe die Nummer .
Man zeigt (sehr leicht), dass die Funktionen und für das Argument unterschiedliche Werte haben, und somit ungleich sind.
Da T beliebig war, gilt das für alle T

[Christian S.]

zur c)

PRIME_BBCODE_SPOILER_SHOW PRIME_BBCODE_SPOILER: auf Anzeigen klicken

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?

PRIME_BBCODE_SPOILER_SHOW PRIME_BBCODE_SPOILER: auf Anzeigen klicken

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.

[SLS]

PRIME_BBCODE_SPOILER_SHOW PRIME_BBCODE_SPOILER: auf Anzeigen klicken

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.

PRIME_BBCODE_SPOILER_SHOW PRIME_BBCODE_SPOILER: auf Anzeigen klicken

Ich verstehe was du meinst, bin aber immer noch nicht mit dir einverstanden, dass es ohne Durchnummerieren geht.
Es ist ja in der Aufgabe folgendes zu beweisen:

und nicht (Reihenfolge der Quantoren!):

Also bei der Konstruktion von f darf man nicht von einem festen T ausgehen! Und mit einem unfesten mach kein Sinn (T ist mehrdeutig, somit auch b(T)).

MfG

[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..