sirokrau

Übung 2

Aufgabe 1

Induktionsanfang (IA):

z.z. Für n = 1 gilt:

F_{1} = F_{1+2}-1

F_{1} = F_{3}-1 (F_{3} = 2)

1 = 2-1

1 = 1 \Rightarrow OK

Induktionsschritt (IS):

Wenn \sum\limits_{k=1}^{i} F_{k} = F_{i+2} - 1 (Induktionsvoraussetzung, kurz IV),

dann gilt auch: \sum\limits_{k=1}^{i+1} F_{k} = F_{i+3} - 1 (Induktionsbehauptung, kurz IB).

\sum\limits_{k=1}^{i+1} F_{k} = \sum\limits_{k=1}^{i} F_{k} + F_{i+1} \quad \stackrel{IV}{=} F_{i+2} -1 + F_{i+1} = F_{i+3} - 1 (Ergebnis = IB)

Übung 3

Aufzählbarkeit und Entscheidbarkeit (Aufgabe 5)

ÜA: Geben Sie fur die Menge FIBS der Fibonacci-Zahlwörter eine Aufzählfunktion an und begründen Sie deren Berechenbarkeit. Weisen Sie nach, dass FIBS eine semi-entscheidbare Menge ist. Zeigen Sie, dass FIBS sogar entscheidbar ist.

Laut der Definition aus der Vorlesung Berechenbarkeitstheorie und Kreativität ist eine Menge aufzählbar, wenn es eine totale berechenbare Funktion f gibt, welche die Menge \N auf eine Menge M abbildet.

In diesem Beispiel handelt es sich bei der Menge M um die Fibonacci-Zahlwörter. Die Aufzählprozedur f lautet wie folgt:

Damit die Funktion f eine surjektiv Abbildung der natürlichen Zahlen auf die Menge der Fibonacci-Zahlwörter und berechenbar ist, wird die Aufzählfunktion g benötigt.

Scheme-Prozedur für die Aufzählfunktion g:

Erzeugen der Menge M an Fibonacci-Zahlwörter:

Um nachweisen zu können, dass die Funktion f semi-entscheidbar ist, muss es wie oben definiert folgende Funktion geben

welche berechenbar ist. Mit Hilfe der Prozedur semi_chi_fib ist dies nachweisbar.

ÜA: Übertragen Sie die vorhergehende Übungsaufgabe sinngemäß auf die Menge der Quadratzahlen QZ = \{n^2 |n \in \N\}.

Analog zur vorhergehenden Übungsaufgabe lässt sich folgende Aufzählprozedur f aufstellen:

Die Auzählfunktion g2, welche die Menge der quadtratischen Zahlen zurückgibt ist folgende:

Erzeugen der Menge M an Quadratzahlen:

Nachweis das die Funktion f semi-entscheidbar ist: Prozedur semi_chi_quad

Nachweis das die Funktion ebenfalls entscheidbar ist:

Übung 4

Teilaufgabe 2 - Beweis Teil 2 (Tobias Salzmann, Ronald Krause)

Abbildung

zu zeigen: Wenn M und A^*\M aufzählbare Mengen sind, dann ist M eine entscheidbare Menge.

Da M und A^*\M aufzählbare Mengen sind, gibt es total berechenbare surjektive Funktionen für diese.

Für M lautet die Auzählfunktion f: \N \mapsto M:

Hinweis: a \in M .

Für A^*\M lautet die Auzählfunktion g: \N \mapsto A^*\M:

Hinweis: b \in A^*\M .

Beweis

Da zu zeigen ist, dass M entscheidbar sein soll, muss es eine total berechenbare Funktion \chi_M geben.

Es muss also eine Prozedur chi geben, welche für jedes Wort w in endlicher Zeit für ein i mit w = f(i) oder w = g(i) findet.

Da die Schnittmenge von M und A^*\M eine leere Menge ist, kann es kein i geben, welches in beiden Mengen vorkommt, sodass man genau sagen kann, ob i in der Menge M oder der Menge A^*\M liegt.

Da das Wort w aus der Wortmenge A^* stammt und die Vereinigung der beiden Menge die Wortmenge ist, muss das Wort in diesen beiden Mengen liegen. Um die Abzählbarkeit zu gewährleisten, wird abwechseln das i-te-Element aus f und g gesucht, sodass kein Wort vergessen wird.