BuK/IIm11/BuK-Übung04

Wiki-Quelltext dieser Seite.

<language>Scheme</language>
== Aufgabe 1 ==
Satz 1: Eine Menge M ist genau dann aufzählbar, wenn sie semi-entscheidbar ist.

=== Teilaufgabe 1 <tt>(Jens Heider, Daniel Tasche, Felix Nitsche, Stefan Lüttke)</tt> ===
zu zeigen: Wenn $M$ aufzählbar, dann $M$ semi-entscheidbar.

Gegeben ist eine aufzählbare Menge. Daraus folgt, dass es eine Aufzählprozedur $f$ für $M$ gibt, welche die natürlichen Zahlen auf die Elemente von $M$ abbildet. $f : \N \mapsto M $

zu zeigen: $M$ ist semi-entscheidbar

Wenn $M$ semi-entscheidbar ist, dann gibt es eine Prozedur $\chi'_M$, die für ein Wort aus der Menge $M$ über dem Alphabet $A^*$ ''wahr'' zurückgibt, wenn das Wort in der Menge enthalten ist und ansonsten ewig weiter läuft. $\chi'_M(w) : A^* \mapsto \{\text{wahr}\}$

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

Durch Verwendung der Prozedur $f$ kann entschieden werden, ob ein gegebenes Element in der Menge $M$ enthalten ist. Dabei wird $f$ für jedes $i$; mit $i \in \N$ aufgerufen, $f(0)$, $f(1)$, $f(2)$, ...
Ergibt $f(i)$ das Wort, dann gibt $\chi'_M$ ''wahr'' zurück, ansonsten läuft die Prozedur ewig weiter.

$$
\chi'_M(w) = \begin{cases}
wahr; & \text{wenn } f(i) = w; i \in \N;\\
\bot; & sonst
\end{cases}
$$

=== Teilaufgabe 2 <tt>(Tobias Salzmann, Ronald Krause, Robert Rosenberger, Stefan Scheumann)</tt> ===
ÜA: Vervollständigen Sie die Herleitung der Funktionen für x und y aus $z = π(x, y)$ und geben Sie als Beispiel die Ermittlung von x und y aus $z = π(1, 3) = 13$ an.

Herleitung der Funktionen für $x$ und $y$ aus $z = (x; y)$

$z =\frac{(x+y)(x+y+1)}{2} +y = t + y;$ <br />
$w = x + y;$ <br />
$x,y,z \in \N, w,t \in \R_{0}^{+}$


$t = z - y = \frac{w(w+1)}{2} = \frac{w^{2}+w}{2} $

Die Lösung von $w^{2} + w + 2t = 0$

$w_{1,2}=-\frac{p}{2} \pm \sqrt{\left(\frac{p}{2}\right)^2-q}$

$w_{1,2}=-\frac{1}{2} \pm \sqrt{\left(\frac{1}{2}\right)^2+2t}$

$w_{1,2}=-\frac{1}{2} \pm \sqrt{\frac{1}{4}+\frac{8t}{4}}$

$w_{1,2}=-\frac{1}{2} \pm \sqrt{\frac{1+8t}{4}}$

$w_{1,2}=-\frac{1}{2} \pm \frac{\sqrt{1+8t}}{2}$

für positives $w$ ist $w_1 = \frac{\sqrt{8t+1}-1}{2}$

<br />Außerdem gilt:<br />
$t \leq z $, weil $z=t+y$<br />
$z= t + w - x$, weil $z=t+y$ und $y=w-x$<br />
$z \leq t + w \leq t + w + 1 = \frac{w^{2}+w}{2} + w + 1 = \frac{(w+1)^{2} + (w+1)}{2}$

<br />Unter Verwendung von $z \leq  \frac{(w+1)^{2} + (w+1)}{2}$ können wir $w$ nach oben abschätzen.

$w = \frac{\sqrt{8t+1}-1}{2} \leq \frac{\sqrt{8z+1}-1}{2} \leq w+1 $

<br />Für $z$ wird $\frac{(w+1)^{2} + (w+1)}{2}$ eingesetzt:

$\frac{\sqrt{8\frac{(w+1)^{2} + (w+1)}{2}+1}-1}{2}$

$\frac{\sqrt{8\frac{w^2+3w+2}{2}+1}-1}{2}$

$\frac{\sqrt{\frac{8w^2+24w+16}{2}+1}-1}{2}$

$\frac{\sqrt{4w^2+12w+9}-1}{2}$ = $\frac{\sqrt{(2w+3)^2}-1}{2}$ = $\frac{2w+2}{2}$ = $\frac{2(w+1)}{2}$ = $w+1$

<br />Um die beiden natürlichen Zahlen x und y aus z zu gewinnen, ist
als erstes $w = \left\lfloor \frac{\sqrt{8z+1}-1}{2} \right\rfloor $ zu berechnen. Dann ergeben sich

$t = \frac{w(w+1)}{2}$ und
$y = z -t$ sowie 
$x = w - y$

'''Beispiel: Ermittelung von $x$ und $y$ aus $z=\pi(1,3) = 13$'''

$w = \left\lfloor \frac{\sqrt{8z+1}-1}{2} \right\rfloor = \left\lfloor \frac{\sqrt{8 \cdot 13+1}-1}{2} \right\rfloor = 4.623 = 4  $ 

$y=13-\frac{w(w+1)}{2} = 13-\frac{4(4+v1)}{2} = 13 - 10 = 3$

$x=w-y = 4 - 3 = 1$

<popup name="Alternative Herleitung mittels Dreiecksfläche">
Um die beiden natürlichen Zahlen $x$ und $y$ aus $z$ zu gewinnen, wird die Umkehrfunktion benötigt. Dazu gibt es folgende Überlegung:

[[Bild:S3erjaeh_Umkehr_Cantor1.png|mini|250px|rechts]]

Die fortlaufende Zahl $z$ kann als Zählung von Flächenquadraten in einem Dreieck angesehen werden. Somit kann über die Berechnung der Dreiecksfläche $A=\frac{a^2}{2}$ die Seitenlänge ermittelt werden. Würde man nun 10 solcher Flächenquadrate zählen (blau), wäre diese Fläche größer als das rote kleine Dreick mit einer Seitenlänge von 4 und kleiner als das rote große Dreieck mit einer Seitenlänge von 5. Liegt die errechnete Seitenlänge nun unter 4,5 handelt es sich um ein Dreieck mit der Seitenlänge 4. Ist die Seitenlänge größer als 4,5 besitzt das Dreieck eine Seitenlänge von 5. Um dies zu vereinfachen kann zu der errechneten Seitenlänge 0,5 addiert werden. Der Abgerundete Wert der errechneten Seitenlänge enspricht nun genau der größtmöglichen $x$ bzw. $y$ Koordinate in dem jeweiligen Dreieck.

$$ A=\frac{a^2}{2} $$
$$a=\sqrt{A*2}$$
$$a=\lfloor\sqrt{A*2}+0,5\rfloor$$
$$f(z)=\lfloor\sqrt{z*2}+0,5\rfloor$$

Ist die Seitenlänge bekannt, kann die Anzahl an Flächenquadraten für das ganze Dreieck errechnet werden. Dazu kann die Cantorschen Paarungsfunktion genutzt werden und mit $y=0$ vereinfacht werden, da bei $y=0$ sich die größten Werte von $z$ befinden. Durch subtraktion des ermittelten Flächenmaxima mit der gegebenen Fläche $z$ kann $x$ errechnet werden. Die Differenz von der Seitenlänge und $x$ entspricht nun $y$. Für die Korrektur des Indexes aufgrund der 0-Basis von $y$ wird zusätzlich 1 subtrahiert.

$$\pi(x,y)=\frac{(x+y)(x+y+1)}{2}+y$$
$$\textrm{mit } y=0 \textrm{ :}$$
$$\pi(x)=\frac{(x)(x+1)}{2}$$

$$x(z) = \pi(f(z)) - z$$
$$y(z) = f(z) - n(z) - 1$$

Da im Model aufgrund der einfacheren Herleitung von 1 angefangen wird zu zählen, müssen wir in der Funktion alle Werte von $z$ mit $z+1$ ersetzen. Daraus ergiebt sich folgende Scheme Prozedur:

<code id="5359427923d9d">
(define getCoord 
  (lambda (z)
    (let* ([a (floor (+ (sqrt (* (+ z 1) 2)) 0.5 ))] 
           [x (- (/ (* a (+ a 1)) 2) (+ z 1))]
           [y (- a x 1)])
    (cons (inexact->exact x) (cons (inexact->exact y) '())))))
</code>
<run id="5359427923ea0">
(getCoord 176)
</run>
 </popup>

== Aufgabe 2 ==
Satz 2: Jede Teilmenge einer abzählbaren Menge ist abzählbar, aber nicht jede Teilmenge einer aufzählbaren Menge ist aufzählbar.

=== Teilaufgabe 1 - Beweis <tt>(Felix Nitsche, Stefan Lüttke)</tt> ===
zu zeigen: Jede Teilmenge $M_2$ einer abzählbaren Menge $M_1$ ist abzählbar.
Wenn $M_1$ eine abzählbare Menge ist, dann ist jede Teilmenge $M_2 \subseteq M_1$ abzählbar.


Da für $M_2 = \emptyset$ die Aussage offensichtlich zutrifft kann angenommen werden dass wenigstens ein Element $a \in  M_2$ existiert.


Für $M_1$ als abzählbare Menge existiert eine Funktion


$f(x) = n \in M_1$


welche die Menge der natürlichen Zahlen auf $ M_1 $ abbildet.


Dadurch kann man nun für $M_2$ die folgende Funktion angeben:


$
g(x) = \begin{cases}
f(x); & f(x) \in M_2;\\
a; & sonst
\end{cases}
$


Durch diese Funktion wird nun jedem Element der natürlichen Zahlen eindeutig ein Element der Menge $M_2$ zugeordnet, wodurch deren Abzählbarkeit bewiesen ist.

=== Teilaufgabe 2 - Indirekter Beweis <tt>(Max Wielsch, Raik Bieniek)</tt> ===

zu zeigen: Nicht jede Teilmenge $M_2$ einer aufzählbaren Menge $M_1$ ist aufzählbar.

oder: Wenn M1 eine aufzählbare Menge ist, dann gilt nicht für alle Teilmengen $M_2$ ⊆ $M_1$, dass sie aufzählbar sind.

Indirekter Beweis: Behauptung:  Wenn $M_1$ aufzählbar, dann jede Teilmenge $M_2$ ⊆ $M_1$ ist aufzählbar.

Gegeben:
* f: ℕ ↦ $M_1$; aufzählbar (surjektiv; berechenbar)
* $M_2$ ⊆ $M_1$
* Satz 1: Wenn $M_2$ entscheidbar ⇔ $M_2$ und $M_1 \setminus M_2$ aufzählbar.
* Satz 2: Wenn $M_2$ aufzählbar → dann ist $M_2$ semientscheidbar.

Gesucht:
* g: ℕ ↦ $M_2$; aufzählbar (surjektiv; berechenbar), d. h. es gilt Satz 1.

$g(x) =  \left\{\begin{array}{cc}
f(x), wenn\ f(x) ∈ M_2\\
a, wenn f(x) ∈ M1\setminus M_2\\
\end{array}\right.
$

laut Satz 2:

$Χ'_{M_2,M_1}(w) =  \left\{\begin{array}{cc}
wahr, (f(i) = w) ∈ M_2; für\ i\ von\ 0\ bis\ ∞\\
⊥, sonst\\
\end{array}\right.
$

$Χ_{M_2,M_1}(w) =  \left\{\begin{array}{cc}
wahr, (f(i) = w) ∈ M_2; für\ i\ von\ 0\ bis\ ∞\\
falsch, (f(i) = w) ∈ M_1\setminus M_2 \\
\end{array}\right.
$

$Χ'_{M_2,M_1}$ vs. $Χ_{M_2,M_1}$; entscheidbar ☇ semi-entscheidbar. → Behauptung falsch → Satz wahr.

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

== Aufgabe 3 ==
Satz 3: Wenn die Menge $M$ entscheidbar ist, dann ist $M$ aufzählbar.

'''Beweis:'''

Es ist gegeben, dass $M$ entscheidbar ist. Damit ist $M$ auch semi-entscheidbar. Wie in Satz 1 bereits bewiesen wurde gilt, dass jede semi-entscheidbare Menge auch aufzählbar ist.

== Aufgabe 4 ==
Eine Menge M, mit $M \subseteq A^*$ ist entscheidbar genau dann, wenn M und $A^* \setminus $M aufzählbare Mengen sind.

=== Teilaufgabe 1 - Beweis Teil 1 <tt>(Ingo Körner, Christof Ochmann)</tt> ===
Hinrichtung des Satzes: Wenn M eine entscheidbare Menge ist, dann sind M und $A^*$\M aufzählbare Mengen.

Beweis:
Aus der Entscheidbarkeit von M folg semi-Entscheidbarkeit von M und \M.
Jede semi-entscheidbare Menge M ist aufzählbar. Es gibt eine Aufzählfunktion f für M und auch die Cantorsche Paarungsfunktion.

$$f(z) = \begin{cases}
g(x), & \text{wenn $\chi'_M$(g(x)) = wahr innerhalb von Zeit y};\\
a, & \text{wenn Proz. für $\chi'_M$(g(x)) innerhalb y ohne Ergebnis}.\\
\end{cases}$$
wobei a $\in$ M, wenn $M \neq \emptyset$

$$g(x) = \begin{cases}
w, & \text{w $\in$ M};\\
\perp, & \text{sonst}.\\
\end{cases}$$

=== Teilaufgabe 2 - Beweis Teil 2 <tt>(Tobias Salzmann, Ronald Krause)</tt> ===
[[Bild:Sitosalz_Entscheidbarkeit_aufzaehlbarkeit.png| miniatur | Abbildung]]

zu zeigen: Wenn M und $A^*$\M aufzählbare Mengen sind, dann ist M eine entscheidbare Menge.

Da M und $A^*$\M aufzählbare Mengen sind, gibt es total berechenbare surjektive Funktionen für diese.

Für M lautet die Auzählfunktion $f: \N \mapsto M$:

$$f(n) = \begin{cases}
f(n), & \text{wenn } f(n) \in M;\\
a, & sonst
\end{cases}$$

'''Hinweis:''' $a \in M$ .

Für $A^*$\M lautet die Auzählfunktion $g: \N \mapsto A^*$\M:

$$g(n) = \begin{cases}
g(n), & \text{wenn } g(n) \in A^*\text{ \M};\\
b, & sonst
\end{cases}$$

'''Hinweis:''' $b \in A^*$\M .

==== Beweis ====

Da der Beweis erbracht werden soll, dass die Menge M entscheidbar ist, so muss eine total berechenbare Funktion $\chi_M$ existieren.

$$\chi_M(w) = \begin{cases}
wahr, & \text{wenn } w \in M;\\
falsch, & \text{wenn } w \in A^*\text{ \ M}
\end{cases}$$

Des Weiteren sollte es eine Prozedur ''chi'' geben, welche für jedes Wort $w$ in endlicher Zeit für ein $i$ mit w = f(i) oder w = g(i) findet.

Da die Schnittmenge von M und $A^*$\M eine leere Menge ist, kann es kein Wort ''w'' geben, welches in beiden Mengen vorkommt, sodass genau gesagt werden kann, ob $w$ in der Menge M oder der Menge $A^*$\ M liegt.

$$M \cap (A^*\text{ \ M}) = \empty,\text{ gilt} f(i) = g(j) = w \text{ ausgeschlossen}$$

Das Wort $w$, welches aus der Wortmenge $A^*$ stammt, und die Vereinigung der beiden Mengen, die Wortmenge ist, so muss das Wort $w$ in diesen beiden Mengen liegen. Um die Abzählbarkeit zu gewährleisten, wird abwechselnd das $i$-te-Wort aus $f$ und $g$ gesucht, sodass kein Wort vergessen wird.

$$\chi_M(w) = \begin{cases}
wahr, & \text{wenn } f(i) = w;\\
falsch, & \text{wenn } g(i) = w
\end{cases}$$

=== Teilaufgabe 3 - Illustration <tt>(Robert Rosenberger, Stefan Scheumann)</tt> ===

= Übung 4, Aufgabe 4 (Teilaufgabe 3) =

Illustrieren Sie den Beweis (Aufgabe 4.2) durch ein Scheme-Programm. 

<code id="4f8dcb1c442d7" hidden>
(define stream-car car)

(define stream-cdr
  (lambda (stm)
    (force (cdr stm))))

(define-syntax stream-cons
  (syntax-rules ()
    ((_ head tail) (cons head (delay tail)))))


  
(define stream-item
  (lambda (str k)
    (if (= k 0)
      (stream-car str)
      (stream-item (stream-cdr str) (- k 1)))))

(define stream->list
  (lambda (str n)
    (if (<= n 0)
      '()
      (cons 
        (stream-car str) 
        (stream->list (stream-cdr str) (- n 1))))))


(define print-stream
  (lambda (stm n)
    (cond
      ((<= n 0) (display "...\n"))
      (else
       (display (stream-car stm))
       (display ", ")
       (print-stream (stream-cdr stm) (- n 1))))))

(define stream-map
  (lambda (stm proc)
    (stream-cons
     (proc (string->number (stream-car stm)))
     (stream-map (stream-cdr stm) proc))))

(define natstream
  (lambda (start)
    (stream-cons (number->string start) (natstream (+ 1 start)))))

(define natzahlstream (stream-cons (number->string 0) (natstream 1)))
</code>

<code id="4f8dcae2c8d51">
; Aufzählfunktion f für alle ungerade Zahlen (hier für M)
(define f
  (lambda (n)
    (number->string (+ 1 (* n 2)))))

; Aufzählfunktion g für alle gerade Zahle (hier für A*/M)
(define g
  (lambda (n)
    (number->string (* 2 n))))

(define generiere_aufzaehlbare_menge 
  (lambda (f)
    (stream-map natzahlstream f)))

(define menge-bis print-stream)

(define M (generiere_aufzaehlbare_menge f))
(define A*-M (generiere_aufzaehlbare_menge g))

(define chi_M
  (lambda (w)
    (letrec
        ((chihelper
          (lambda (i)
            (cond
              ((string=? (f i) w) #t)
              ((string=? (g i) w) #f)
              (else
               (chihelper (+ i 1)))))))
         (chihelper 0))))
</code>

<run id="4f8dcae2c8dc4">(menge-bis M 10)</run>

<run id="4f8dcae2c8e22">(menge-bis A*-M 10) </run>

<run id="4f8dcae2c8e84">(chi_M "9199")</run>