siinkoer

Aufgabe 3 (Ingo Körner, Christof Ochmann)

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

Für \Z:

Für \Q:

Es werden mit Hilfe des ersten Cantorschen Diagonalisierungsverfahren alle Zahlen erreicht.

Für die Menge der Primzahlen:

1. Die Menge der Primzahlen P ist unendlich (nach Satz von Euklid).

2. Die Menge der Primzahlen P ist abzählbar unendlich, da gilt: P \subset \N.

Für die Menge der geraden Zahlen:

1. Die geraden Zahlen G sind unendlich (per Definition) und abzählbar unendlich, da gilt: G \subset \Z.

Aufgabe 4 (Ingo Körner, Christof Ochmann)

ÜA: Zeigen Sie, dass jede endliche Menge M aufzählbar ist.

aufzählbar = abzählbar + berechenbar

1) Jede endliche Menge ist aufzählbar (per Definition).

2) Jede endliche Menge ist berechenbar.

Es gibt eine Funktion f, die als Eingabe die natürlichen Zahlen N nimmt und auf jedes Element der endlichen Menge M abbildet. f ist berechenbar, da es eine total berechenbare surjektive Funktion f : N -> M gibt. Es wird der Reihe nach jedes Element aus N einem Element aus M zugeordnet. Ist f sujektiv, können die restlichen Elemente aus N auf ein beliebiges Element von M abgebildet werden. Somit ist f surjektiv, total und berechenbar.

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

Übersicht: 2D-Ebene

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

2 Definieren Sie eine Ordnungsrelation p_< in G.

(G, p_<) = {(0,0) < (0,1) < (1,0) < (2,0) < (1,1) < (0,2) < (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.

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

Teilaufgabe 1 - Beweis Teil 1 (Ingo Körner, Christof Ochmann)

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. Sie wird auch Contorsche Paarungsfunktion genannt.

wobei a \in M, wenn M \neq \emptyset

Turing-Aufzählbarkeit, Turing-Entscheidbarkeit (Max Wielsch, Raik Bieniek, Ingo Körner, Christof Ochmann)

Definieren Sie die Begriffe Turing-aufzählbar und Turing-entscheidbar analog zur Turing-Berechenbarkeit.

Sei A ein Alphabet, M \subseteq A^*. M heißt Turing-entscheidbar, falls die charakteristische Funktion \chi_M Turing-berechenbar ist.

M heißt Turing-aufzählbar, wenn es eine Funktion f: N \rightarrow M gibt, die surjektiv und Turing-berechenbar ist.

Aufgabe 1 (Ingo Körner, Christoph Ochmann)

(Aufgabe siehe: VL Slide 13)

Zeigen Sie die Unentscheidbarkeit (Semi-Entscheidbarkeit) von L_{\Sigma^{*}}:=\{\left\langle M \right\rangle | L(M) = \Sigma^{*} \} durch Reduktion der Sprache L_{\Sigma^{*}} auf das Halteproblem.

Lösungsansatz: Schreibe die Kodierung der Maschine M, d.h. <m>, zusammen mit dem aktuellen Eingabewort w \in \Sigma^{*} auf das Band einer UTM. Die UTM ist so konstruiert, dass sie aus ihrer Eingabe <M> und w die Kodierung einer Maschine M', d.h. <M'>, zusammen mit einem Eingabewort y auf ihr Band als Ausgabe schreibt. Als nächstes führt die UTM die Kodierung der Maschine M' mit dem Wort y aus. Dabei verwirft die Maschine M' als erstes ihr Eingabewort y. Wenn die durch die UTM ausgeführte Maschine M' auf dem anfangs leeren Band hält, so heißt das, dass auch die Maschine M mit dem Wort w akzeptieren würde. Wenn die durch die UTM ausgeführte Maschine M' auf dem anfangs leeren Band nicht in einem Endzustand hält, dann stoppt auch die Maschine M mit dem Wort w nicht in einem Endzustand. Berechne aus der Eingabe <M> die Kodierung der Maschine M'. M' ist die Maschine, die ihre Eingabe löscht, dann <M> auf das Band schreibt und dann auf <M> weiterrechnet. <M> ist \in L_{\Sigma^{*}}$ genau dann, wenn M' termiert.</m>