BuK/IIm11/Studenten/sitosalz

Wiki-Quelltext dieser Seite.

<language>Scheme</language>
= Ü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 $

<div align="right">$\square $</div>

= Übung 3 =

== Aufgabe 5 ==
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.


[[Bild:Sitosalz_Übersicht_Mengenklassen.png| miniatur |Übersicht: Mengenklassen]]

=== Ü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. <br />
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:

<code id="4f7aa7165160a">
(define eternity 
  (lambda () 
    (eternity)))

(define chi-a
  (lambda (w)
    (if (char=? (string-ref w 0) #\a)
    #t
    (eternity))))
</code>
<run id="4f7aa7165169c">
(chi-a "abbbbaaabbbb")
</run>
<run id="4f7aa7165170b">
(chi-a "babbbaaabbbb")
</run>


===Ü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.