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:

Implementierung der Funktion f:

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