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

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(0),f(1),f(2),f(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.

Entscheidbarkeit und Aufzählbarkeit

Satz 3: Wenn die Menge M entscheidbar ist, dann ist M 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.

Kreativaufgaben