sirokrau
Inhaltsverzeichnis |
Übung 2
Aufgabe 1
\sum\limits_{k=1}^{n} F_{k} = F_{n+2} - 1Induktionsanfang (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:
f(n) = \begin{cases} g(n), & \text{wenn } g(n) \in \text{ M};\\ 0, & sonst. \end{cases}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.
g(n) = \begin{cases} 0, & \text{wenn } n=0;\\ 1, & \text{wenn } n=1;\\ (n-1) + (n-2), & sonst. \end{cases}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
\chi'_{M}(w) = \begin{cases} wahr, & \text{wenn } w \in \text{ M};\\ \bot, & sonst. \end{cases}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:
f(n) = \begin{cases} g(n), & \text{wenn } g(n) \in \text{ M};\\ 1, & sonst. \end{cases}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: