BuK/IIm18/Vorlesung3

Wiki-Quelltext dieser Seite.

<language>SchemeJS</language>
=Entscheidbarkeit und Aufzählbarkeit=
<language>SchemeJS</language>
==Aufgabe 1 ==
Zeigen Sie, dass die beiden Mengen aus den Beispielen entscheidbar sind. Schreiben Sie je eine entsprechende Prozedur für die jeweilige charakteristische Funktion (ProgrammingWiki).

'''Beispiel 1''': endliche Menge

geg.: Menge M aller Wörter aus <math> A^* = \{a,b\}</math> und <math>M \subset A^* =\{w | w \in A^* \text{ und } |w|=3 \}</math>

z.z.: M entscheidbar

Lösung:

<math>
\chi_{M}(w) = \begin{cases}
true, & \text{wenn } w \in M \\
false, & \text{sonst}
\end{cases}
</math>

<math> w \in M  \text{ wenn } w==aaa || w==aba || w==aab || w==baa || w==bab || w==abb || w==bba || w==bbb; </math>

Die Menge M ist somit entscheidbar.

<code id="5c9f6c0fe0161">
(define m1
  (lambda (n)
    (let ((l (string->list n)))
       (letrec
           ((helper
             (lambda (a)
               (if (or (char=? #\a (car a)) (char=? #\b (car a)))
                   (if (not (null? (cdr a)))
                       (helper (cdr a))
                       #t
                       )
                   #f
                   )
               )
             )
            )
         (if (= (string-length n) 3)
             (helper (cdr l))
             #f
             )
         )
      )
    )
  )
</code>

<run id="5c9f8e46956ed">
(m1 "aba")
</run>


'''Beispiel 2''': abzählbar unendliche Menge

geg.: Menge M aller Wörter aus <math> A^* = \{a,b\}</math> und <math>M \subset A^* =\{aw' | w' \in A^* \}</math>

z.z.: M entscheidbar

Lösung:

<math>
\chi_{M}(w) = \begin{cases}
true, & \text{wenn } w \text{ mit a beginnt und } w \in M \\
false, & \text{sonst}
\end{cases}
</math>

Die Menge M ist entscheidbar.

<code id="5c9f6c0fe01ed">
(define m2
  (lambda (n)
    (let ((l (string->list n)))
      (letrec
          ((helper
            (lambda (a)
              (if (or (char=? #\a (car a)) (char=? #\b (car a)))
                   (if (not (null? (cdr a)))
                   (helper (cdr a))
                   #t
                   )
                   #f
                   )
              )
            )
           )
        (if (and (not (null? l)) (char=? #\a (car l)))
            (if (null? (cdr l))
                #t
                (helper (cdr l)))
            #f
            )
        )
      )
    )
  )
</code>

<run>(m2 "abba")</run>

==Aufgabe 2==
Wie viele berechenbare charakteristische Funktionen gibt es?

Hinweis: Potenzmenge unendlicher Mengen

<math>A^*</math> ist eine abzählbar unendliche Menge, d.h. alle <math> M \subseteq A^*</math> sind abzählbar Mengen, entweder endlich oder unendlich.

Die Potenzmenge von <math>A^*</math> ist eine überabzählbar unendliche Menge, wodurch es überabzählbar unendlich viele Mengen <math>M</math> gibt. 

<math>\chi_{M}</math> kann die Werte <math>true \text{ oder } false</math> annehmen.

Die überabzählbare Menge <math>M</math> bildet den Definitionsbereich der Funktionen <math>\chi_{M}</math>.

Das heißt es gibt überabzählbar viele charakteristische Funktionen <math>\chi_{M}</math>, für jede Teilmenge <math>M</math> von <math>A^*</math>.

Da es jedoch nur abzählbar unendlich viele Algorithmen gibt, verbleiben überabzählbar unendlich viele <math>\chi</math>-Funktionen, die nicht berechnet werden können. Nur abzählbar unendlich viele charakteristische Funktionen sind somit berechenbar.

==Aufgabe 3 ==
Zeigen Sie, dass die Menge der geraden Zahlen G eine aufzählbare Menge ist.

geg.: <math>M_{G}</math> die Menge der geraden Zahlen und <math>M_{G} \in \mathbb{Z}</math> 

z.z.: <math>M_{G}</math> abzählbar, <math>M_{G}</math> berechenbar

Lösung:

Abzählbarkeit:

Da <math>M_{G} \in \mathbb{Z}</math>.

Der Beweis für die Aufzählbarkeit der ganzen Zahlen <math>\mathbb{Z}</math> ist die Existenz der bijektiven Funktion

Mit der bijektiven Funktion 

<math>f(i)=\begin{cases}-\frac{i}{2} & \text{, wenn }i\text{ gerade}\\\frac{i+1}{2} & \text{, sonst}\end{cases}</math>, mit <math>i \in \mathbb{N}</math> 

können die natürlichen Zahlen auf die ganzen Zahlen <math>\mathbb{Z}</math> abgebildet werden.

{| border="1" cellpadding="5" cellspacing="0"
|-
||<math>\mathbb{N}</math>|| 0 || 1 || 2 || 3 || 4 || 5 || ...
|-
||<math>\mathbb{Z}</math>|| 0 || 1 || -1 || 2 || -2 || 3 || ...
|-
|}

Das zeigt, dass die ganzen Zahlen abzählbar unendlich sind.

==Aufgabe 4==
Zeigen Sie, dass die Menge der Primzahlen P aufzählbar ist.


==Aufgabe 5==
Wir wissen, dass $A^*$ eine abzählbar unendliche Menge ist. Zeigen Sie, dass $A^*$ auch aufzählbar ist.

Hinweis: Hierzu ist es notwendig ein Aufbauschema für $A^*$ zu entwerfen und anschließend eine Prozedur dafür zu implementieren.


[[Bild:S3romuel_Aufbauschema_60.png]]

== Aufgabe 6 ==
Zeigen Sie, dass jede endliche Menge $M$ aufzählbar ist.




==Aufgabe 7==

Die Menge $G$ der Gitterpunkte $(0,0),(0,1),...$ einer x-y-Ebene ist aufzählbar.

1.Geben Sie eine Funktion f an, die $\N$ bijektiv auf $G$ abbildet.

f ist die Umkehrfunktion der Cantorschen Paarungsfunktion in Teilaufgabe 3. 

$$f(n):\begin{cases}
  y = n-t \\
  x =w-y \\
\end{cases}
$$

mit $$w(n)=
  \dfrac{sqrt(8*n+1)-1}{2}  
$$ 

und mit $$t=
  \dfrac{w(w-1)}{2}  
$$ 

2.Definieren Sie eine Ordnungsrelation $p<$ in G

Mittels der in Teilaufgabe 1 gezeigten Funktion können nun jeder natürlichen Zahl ein Koordinatenpaar zugeordnet werden. Diese Zuordnung findet sich in der nachfolgenden Tabelle.

{| border="1" cellpadding="5" cellspacing="0"
|+ 
! Position               || 0    || 1   ||   2 ||   3 || 4   || 5   || 6   || 7   || 8   || 9   || 10  || 11  || 12  || 13  || 14  || 15  
|-
| Gitterpunkt (x,y)      || (0,0)||(0,1)||(1,0)||(0,2)||(1,1)||(2,0)||(0,3)||(1,2)||(2,1)||(3,0)||(0,4)||(1,3)||(2,2)||(3,1)||(4,0)||(0,5)
|-
|}
Daraus kann man nun eine Ordnungsrelation festlegen mit aufsteigenden x- und y-Koordinaten:

$(G, p_<)$ = {(0,0) < (0,1) < (1,0) < (0,2) < (1,1) < (2,0) < (0,3) < (1,2) < (2,1) < ...}

3. Geben Sie eine Funktion k zur Berechnung der Platznummer $k(x,y)$ des betrachteten Gitterpunktes $(x,y)$ an.

Eine Funktion k zur Berechnung der Platznummer ist die Cantorsche Paarungsfunktion, die folgendermaßen definiert ist:

<math>k(x,y) = \frac{(x+y)+(x+y+1)}{2} + y.</math>



4. Geben Sie eine Aufzählprozedur für $G$ an und begründen Sie deren Berechenbarkeit.

==Aufgabe 8==
Das Halteproblem ist semi-entscheidbar. Beweisen Sie diese Aussage.


==Aufgabe 9==
Geben Sie für 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.

==Aufgabe 10==
Übertragen Sie die vorhergehende Übungsaufgabe sinngemäß auf die Menge der Quadratzahlen $QZ = \{n^2 | n\in\N\}$.

Lösung:

Eine Aufzählfunktion kann folgendermaßen angegeben werden:

<math>
f(n) = \begin{cases}
n, & \text{wenn sqrt(n)}  \in \mathbb{N} \\
2, & \text{sonst}
\end{cases}
</math>

Für die Entscheidbarkeit kann eine charakteristische Funktion angeben werden, die total berechenbar ist:

<math>
\chi_{QZ}(n) = \begin{cases}
true, & \text{wenn } sqrt(n) \in \mathbb{N} \\
false, & \text{sonst}
\end{cases}
</math>

==Aufgabe 11==
Weisen Sie nach, dass die Menge $M$ aller "Wörter" aus $\{a,b\}^*$, die mit a beginnen, semi-entscheidbar ist.

In Aufgabe 2 wurde die Entscheidbarkeit der Menge $M$ nachgewiesen. Wenn eine Menge entscheidbar ist, ist diese folglich auch semientscheidbar.

==Aufgabe 12==
Definieren Sie die Menge der geraden Zahlen (Zahlwörter) und die der ungeraden Zahlen (Zahlwörter) und veranlassen Sie das ProgrammingWiki 30 Elemente der Vereinigungsmenge auszugeben.