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.

Schreibe für alle Eingabewörter aus \Sigma^{*} die Kodierung der Maschine M, d.h. <m>, sowie w \in \Sigma^{*} auf das Band einer Maschine M_2. Die Maschine M_2 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. Die Besonderheit von M' ist, dass diese Maschine mit dem Eingabewort y stoppt, wenn M(w) stoppen würde. Dabei ist y nur ein Platzhalter, denn y hat auf die Terminierung von M' keinen Einfluss. Als nächstes wird <m> und y auf das Band einer UTM M_1 geschrieben. M_1 führt die Kodierung der Maschine M' mit dem Wort y aus. Dabei verwirft die Maschine M' als erstes ihr Eingabewort y, so dass ihr Band leer ist. Wenn die durch M_1 ausgeführte Maschine M' mit ihrem leeren Band hält, so heißt das, dass auch die Maschine M mit dem Wort w akzeptieren würde. Wenn die durch die Maschine M_1 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. <m> ist \in L_{\Sigma^{*}} genau dann, wenn M' termiert.</m></m></m></m></m>

Reduktionsreihenfolge (Ingo Körner, Christof Ochmann)

• Zeigen Sie dass es von der Reduktionsreihenfolge abhängen kann, ob die für ((\lambda y. z)((\lambda x. (x x))(\lambda x. (x x)))) existierende Normalform z gefunden wird oder nicht.

Linksaußen-Reduktion \beta_0: ((\lambda y.z)((\lambda x.(x \text{ } x))(\lambda x.(x \text{ } x)))) \xrightarrow{\beta_0} z

Linksinnen-Reduktion \beta_i: $((\lambda y.z)((\lambda x.(x \text{ } x))(\lambda x.(x \text{ } x)))) \xrightarrow{\beta_i} ((\lambda y.z)((((\lambda x.(x \text{ } x))(\lambda x.(x \text{ } x))))))$

Da sich durch die Linksinnen-Reduktion an der Formel nichts verändert hat, ist sie endlos reduzierbar.

• Verwenden Sie zur Berechnung von ((\lambdax. ((x d)((\lambda y. (x y)) a))) b) unterschiedliche Reduktionsreihenfolgen.

Linksaußen-Reduktion \beta_0: $((\lambda x.((x \text{ } d)((\lambda y.(x \text{ } y))a)))b) \xrightarrow{\beta_0}

((b \text{ } d)((\lambda y.(b \text{ } y))a)) \xrightarrow{\beta_0} ((b \text{ } d)(((b \text{ } a))))$

Linksinnen-Reduktion \beta_i: $((\lambda x.((x \text{ } d)((\lambda y.(x \text{ } y))a)))b) \xrightarrow{\beta_0} ((\lambda x.((x \text{ } d)(((x \text{ } a))))) b) \xrightarrow{\beta_0} ((b \text{ } d)(((b \text{ } a))))$