s3tomack

Übungsaufgaben

Dieses Kapitel enthält die Übungsaufgaben geordnet nach den Vorlesungen.

Vorlesung 1: Vorbereitungen

Vorlesung 2: Berechenbarkeitsbegriff

abzählbar unendliche Mengen

Zeigen Sie, dass die folgenden Mengen abzählbar unendlich sind: \Z, \Q, die Menge der Primzahlen, die geraden Zahlen.

Für \Z:

z.z.: Die Menge \Z ist abzählbar unendlich.

• abzählbar, d.h. \exists f : \N \rightarrow \Z | \text{ bijektiv }

Für \Q:

z.z.: Die Menge \Q ist abzählbar unendlich.

• abzählbar, d.h. \exists f : \N \rightarrow \Q | \text{ bijektiv }
• Elemente von \Q sind darstellbar durch: \frac{p}{q} | q \neq 0 \text{ und } p, q \in \Z

Unter Zuhilfenahme des Cantorschen Diagonalisierungsverfahren 1. Art lassen sich alle Elemente erreichen.

Für die Menge der Primzahlen P:

z.z.: Die Menge P ist abzählbar unendlich.

• abzählbar, d.h. \exists f : \N \rightarrow P | \text{ bijektiv }
• Die Menge der Primzahlen P ist nach dem Satz von Euklid unendlich.
• Die Menge der Primzahlen P ist abzählbar, da gilt P \subset \N (nach Definition der Primzahlen).

Für die Menge der geraden Zahlen G:

z.z.: Die Menge P ist abzählbar unendlich.

• abzählbar, d.h. \exists f : \N \rightarrow G | \text{ bijektiv }
• Die Menge der geraden Zahlen G ist abzählbar, da gilt G \subset \Z.

Vorlesung 3: Entscheidbarkeit und Aufzählbarkeit

Vorlesung 4: Sätze und Zusammenhänge <wip></wip>

Aufzählbarkeit und Semi-Entscheidbarkeit

Satz 1: Eine Menge M ist genau dann aufzählbar, wenn sie semi-entscheidbar ist.

z.z.:

• Wenn M aufzählbar ist, dann ist M semi-entscheidbar. (Teil 1)
• Wenn M semi-entscheidbar ist, dann ist M aufzählbar. (Teil 2)

Teil 1:

Gegeben ist eine aufzählbare Menge M. Hieraus folgt, es gibt eine Aufzählprozedur f_M für M, die die Menge der natülichen Zahlen \N surjektiv auf M abbildet: f:\N \mapsto M.

Semi-entscheidbar ist eine Menge M, wenn ihre semi-charakteristische Funtion \chi'_M:A^*\mapsto\{wahr\} berechenbar ist, also wenn es eine Prozedur gibt die wahr zurückgibt, falls ein übergebenens Wort w ein Element von A^* ist und ansonsten ewig weiter läuft.

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

Unter Verwendung der Aufzählprozedur f_M kann entschieden werden, ob ein übergebenen Wort w \in A^* ein Element von M ist. Hierbei wird f_M der Reihe nach für jedes i \mid i \in \N aufgerufen (f_M(0),f_M(1),f_M(2),f_M(3),\ldots). Ist dabei f_M(i) = w, gibt \chi'_M wahr zurück, andernfalls läuft die Prozedur ewig weiter, d.h. nach Definition ist M semi-entscheidbar.

\chi'_M(w)= \begin{cases} wahr, & \quad \text{wenn } f_M(i)=w \mid i \in \N\\ \bot, & \quad \text{sonst} \end{cases}

Teil2:

Gegeben ist eine semi-entscheidbare Menge M. Somit steht eine partiell berechenbare Funktion \chi'_M:A^*\mapsto\{wahr\} zur Verfügung.

Gesucht ist eine surjektive, total berechenbare Aufzählfunktion: f_M:\N\mapsto M.
Problem: Ob für ein beliebiges Wort w \in A^* entweder w \in M oder w \notin M gilt, kann nur mit chi-strich ermittelt werden. Zur Berechung von f_M(i), nimmt man das i-te Element aus A^* (aufzählbare Menge) und berechnet \chi'_M(w_i). Falls das Ergebnis wahr ist, terminiert \chi'_M(w_i), andernfalls läuft die Funktion ewig weiter.
Gegenmaßnahme: bijektive, total berechenbare Paarungsfunktion \pi:\N\times\N\mapsto\N
Cantorsche Paarungsfunktion: \pi(x,y)=\sum_{i=0}^{x+y}i+y Unter der Verwendung von \chi'_M(w_x) mit der Aufzählprozedur g(x) = w_x für A^* und z = \pi(x,y) kann f_M nun folgendermaßen definiert werden:

f_M(z)=\begin{cases} g(x), & \quad \text{wenn } \chi'_M(g(x))[= wahr] \text{ innerhalb von } y \text{ Zeiteinheiten}\\ a, & \quad \text{wenn Proz. für } \chi'_M(g(x)) \text{ innerhalb von } y \text{ Zeiteinheiten ohne Ergebnis}\\ \end{cases} \mid M \neq \emptyset, a \in M, z \in \N

Vervollständigen Sie die Herleitung der Funktionen für x und y aus z = \pi(x, y).

z=\frac{(x+y)(x+y+1)}{2}+y=t+y
w=x+y
t,x,y,z,w \in \N

t=z-y=\frac{w(w+1)}{2}=\frac{w^2+w}{2}
Lösung von w^2+w-2t=0:
allgemeine Form: w^2+pw-q=0
pq-Formel: 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{8t+1}{4}}
w_{1,2}=-\frac{1}{2}\pm\frac{\sqrt{8t+1}}{2}
Für positive w ergibt sich w_1:
w_1=-\frac{1}{2}+\frac{\sqrt{8t+1}}{2}
w_1=\frac{\sqrt{8t+1}-1}{2}

Außerdem gilt:
t \leq z, \text{ da } z = t + y
z = t + w - x, \text{ da } z = t + y \text{ und } y = w - x
z \leq t + w < t + w + 1
t + w + 1 = \frac{w^2 + w}{2} + w +1 = \frac{w^2+w+2x+2}{2} = \frac{(w^2+2x+1)+(w+1)}{2} = \frac{(w+1)^2+(w+1)}{2}
z < \frac{(w+1)^2+(w+1)}{2}

Unter Verwendung von z < \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} < w + 1

Für z wird \frac{(w+1)^2+(w+1)}{2} eingesetz:
\frac{\sqrt{8\left(\frac{(w+1)^2+(w+1)}{2}\right) + 1} - 1}{2}
\frac{\sqrt{8\left(\frac{w^2+3w+2}{2}\right) + 1} - 1}{2}
\frac{\sqrt{\left(\frac{8w^2+24w+16}{2}\right) + 1} - 1}{2}
\frac{\sqrt{4w^2+12w+9} - 1}{2}
\frac{\sqrt{(2w+3)^2} - 1}{2}
\frac{2w+2}{2}=w+1
Daher ergibt sich w=\lfloor \frac{\sqrt{8z + 1} - 1}{2} \rfloor \in \N

Um die beiden natürlichen Zahlen x und y aus z zu gewinnen, ist als erstes w=\lfloor \frac{\sqrt{8z + 1} - 1}{2} \rfloor zu berechnen.
Danach ergeben sich:
t = \frac{w (w + 1)}{2}
y = z - t
x = w - y

Geben Sie als Beispiel die Ermittlung von x und y aus z = \pi(1, 3) = 13 an:

w = \lfloor \frac{\sqrt{8z + 1} - 1}{2} \rfloor = \lfloor \frac{\sqrt{8 * 13 + 1} - 1}{2} \rfloor = \lfloor 4,6235 \rfloor = 4
t = \frac{w (w + 1)}{2} = \frac{4 (4 + 1)}{2} = \frac{20}{2} = 10
y = z - t = 13 - 10 = \underline{3}
x = w - y = 4 - 3 = \underline{1}

Abzählbarkeit vs. Aufzählbarkeit

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

z.z.:

• Wenn M_1 eine abzählbare Menge ist, dann ist jede Teilmenge M_2 \subseteq M_1 abzählbar. (Teil 1)
• Wenn M_1 eine aufzählbare Menge ist, dann sind nicht alle Teilmengen M_2 \subseteq M_1 aufzählbar. (Teil2)

Teil 1:

Gegeben ist eine bijektive Funktion f_1 : \N \mapsto M_1, da M_1 abzählbar ist.
Es ist zu zeigen , dass die Abzählbarkeit von M_2 daraus folgt. Gesucht ist also mindestens eine surjektive Funktion f_2 : \N \mapsto M_2 für eine beliebige Teilmenge M_2. Man gewinnt f_2 aus f_1:

f_2(n)=\begin{cases} f_1(n), & \quad \text{wenn } f_1(n)\in M_2\\ a, & \quad \text{sonst}\\ \end{cases} \mid M_2 \neq \emptyset, a \in M_2

Teil 2:

Annahme: Für eine aufzählbare Menge M_1 sind alle Teilmengen M_2 \subseteq M_1 aufzählbar.
Laut dieser Annahme ist die Menge M_2 aufzählbar, darausfolgt das M_2 semi-entscheidbar ist.
Gegeben ist eine surjektive, berechenbare Funktion f_1 : \N \mapsto M_1, da laut Voraussetzung die Menge M_1 aufzählbar ist. Laut der Annahmen existiert auch eine surjektive, berechenbare Funktion f_2 : \N \mapsto M_2. Die Funktion f_2 kann unter Verwendung von f_1 definiert werden:

f_2(n)=\begin{cases} f_1(n), & \quad \text{wenn } f_1(n)\in M_2\\ a, & \quad \text{wenn } f_1(n)\in M_1 \backslash M_2\\ \end{cases} \mid a \in M_2

Damit f_2 berechenbar ist, muss die charakteristische Funktion \chi_{M_2,M_1} : M_2 \mapsto \{wahr, falsch\} berechenbar sein.

\chi_{M_2,M_1}(w)=\begin{cases} wahr, & \quad \text{wenn } f_1(n)\in M_2\\ falsch, & \quad \text{wenn } f_1(n)\in M_1 \backslash M_2\\ \end{cases}

Aus der Berechenbarkeit von \chi_{M_2,M_1}(w) folgt, das M_2 entscheidbar ist. Dies steht im Widerspruch zu der aus der Annahme resultierenden Semi-Entscheidbarkeit. Folglich ist die Annahme falsch und der Satz korrekt.

Entscheidbarkeit und Aufzählbarkeit <wip></wip>

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

• Laut Voraussetzung ist M entscheidbar, daraus folgt das M auch semi-entscheidbar ist.
• In Satz 1 wurde bewiesen das semi-entscheidbare Mengen aufzählbar sind, daraus folgt die entscheidbare Menge M ist auch aufzählbar.

Satz 4: Eine Menge M, mit M \subseteq A^*, ist entscheidbar genau dann, wenn M und A^* \ M (Komplementmenge) aufzählbare Mengen sind.

z.z.:

• Wenn M eine entscheidbare Menge ist, dann sind M und A^*\backslash M aufzählbare Mengen. (Teil 1)
• Wenn M und A^*\backslash M aufzählbare Mengen sind, dann ist M eine entscheidbare Menge. (Teil 2)

Teil 1

Da M laut Voraussetzung eine entscheidbare Menge ist, muss die charakteristische Funktion \chi_{M,A^*}:A^* \mapsto \{wahr, falsch\} berechenbar sein. Da A^* eine aufzählbare Menge ist, muss es eine Aufzählprozedur f_{A^*}:\N\mapsto A^* für A^* geben.
Gegeben:

\chi_{M,A^*}(w)=\begin{cases} wahr, & \quad \text{wenn } w \in M\\ falsch, & \quad \text{wenn } w \in A^*\backslash M\\ \end{cases}

Gesucht: \begin{align} f_M & :\N\mapsto M & \mid surjektiv, berechenbar\\ f_{A^*\backslash M} & :\N\mapsto A^*\backslash M & \mid surjektiv, berechenbar \end{align} Unter der Verwendung der Funktion \chi_{M,A^*}(w) und der Aufzählprozedur f_{A^*} von A^* lassen sich die Aufzählprozeduren für M und A^*\backslash M wie folgt definieren: \begin{align} f_M(n) & =\begin{cases} f_{A^*}(n), & \quad \text{wenn } \chi_{M,A^*}(f_{A^*}(n)) = wahr\\ a, & \quad \text{sonst}\\ \end{cases}\\ f_{A^*\backslash M}(n) & =\begin{cases} f_{A^*}(n), & \quad \text{wenn } \chi_{M,A^*}(f_{A^*}(n)) = falsch\\ b, & \quad \text{sonst}\\ \end{cases}\\ \end{align} wobei gilt: a \in M, M \neq \emptyset und b \in A^*\backslash M, A^*\backslash M \neq \emptyset.

Teil 2

Laut Voraussetzung sind M und A^*\backslash M aufzählbare Mengen, d.h. gibt es surjektive und total berechenbare Funktionen f_M:\N\mapsto M und f_{A^*\backslash M}:\N\mapsto A^*\backslash M.
Gegeben:

Gesucht:

\chi_{M,A^*}(w)=\begin{cases} wahr, & \quad \text{wenn } w \in M\\ falsch, & \quad \text{wenn } w \in A^*\backslash M\\ \end{cases}

Ein Algorithmus für \chi_{M,A^*} muss für jedes übergebene Wort w genau ein i finden, mit entweder w=f(i) oder w=g(i).

Da M \cap (A^*\backslash M) = \emptyset ist der Fall f(i) = g(i) = w ausgeschlossen. Da w \in A^* wegen M \cup (A^*\backslash M) = A^* in einer der beiden Mengen enthalten sein muss, terminiert der Suchprozess von w.

Kreativaufgaben

RAM Programm