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 =

<language>Scheme</language>
== Aufgabe 5 ==
[[Bild:Sitosalz_Übersicht_Mengenklassen.png| miniatur |Ü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.

<language>Scheme</language>
=== Ü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="4f7b27dc2b0b9">
(define chi-a
  (lambda (w)
    (if (char=? (string-ref w 0) #\a)
    #t
    (chi-a w))))
</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. <br />
Das Halteproblem  ist somit semi-entscheidbar, weil eine partielle Funktion hierfür angegeben werden kann.


<code id="4f7b198fc5ee5">
(define (haelt? f n)
  (f n) #t)

(define eternity
  (lambda (n) 
    (eternity n)))

(define (square n)
  (* n n))
</code>

<run id="4f7b198fc5f50">
(haelt? square 4)
</run>

<run id="4f7b198fc5fa7">
(haelt? eternity 4)
</run>