sitosalz

Aus ProgrammingWiki
< BuK < IIm11 < Studenten
Archivierte Version vom 2012-04-03T16:38:41+00:00. Aktuelle Version

Inhaltsverzeichnis

Übung 2

Aufgabe 2

\sum\limits_{k=1}^{n} F_{2k} = F_{2n+1} - 1

IA:

Für n = 1 ergibt sich:

F_2 = F_{2*1+1} - 1 F_2 = F_{3} - 1 1 = 2 - 1 1 = 1 \Rightarrow OK

IS:

Wenn \sum\limits_{k=1}^{i} F_{2k} = F_{2i+1} - 1 (IV), dann gilt auch:

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


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

Übung 3


Aufgabe 5

Sitosalz_Übersicht_Mengenklassen.png
Übersicht: Mengenklassen
Eine Menge M \subseteq A^* ist semi-entscheidbar, wenn die partielle (semi-charakteristische) Funktion \chi'_M : A^* \mapsto \{wahr\} mit

\chi'_M(w) = \begin{cases} wahr, & \text{wenn } w \in M;\\ \bot, & sonst. \end{cases}

berechenbar ist.

ÜA: Weisen Sie nach, dass die Menge M aller "Wörter aus {a, b}*, die mit a beginnen, semi-entscheidbar ist.

Wie in der Übersicht zu den Mengenklassen ersichtlich, ist eine Menge auch semi-entscheidbar, wenn Sie entscheidbar ist.
In Aufgabe 2 wurde die Entscheidbarkeit dieser Menge gezeigt, daraus folgt das Sie auch semi-entscheidbar sein muss.

Weiterhin kann auch eine partielle semi-charakteristische Funktion angegeben werden:





ÜA: Das Halteproblem ist semi-entscheidbar. Beweisen Sie diese Aussage.
Man kann eine Prozedur haelt? angeben, welche angewand auf eine Prozedur f true zurück gibt falls f terminiert und ansosnten ewig weiter läuft, für diesen Fall also nicht definiert ist. 

Das Halteproblem  ist somit semi-entscheidbar, weil eine partielle Funktion hierfür angegeben werden kann.