MATHEMATISCHES INSTITUT DER UNIVERSITÄT BONN Prof. Dr. Philip Welch

Bonn, den 05.06.2002

Berechenbarkeitstheorie Aufgabenblatt 7

Aufgabe 1 Zeigen Sie, daß es rekursive Funktionen f, g : ℕ^{2} → ℕ gibt, so daß gilt:

W_{x} ∪ W_{y} = W_{f(x,y)} und W_{x} ∩ W_{y} = W_{g(x,y)}.

Aufgabe 2 Zeigen Sie: Es existiert ein n mit E_{n} = {n}. (Erinnerung: E_{n} = ran φ_{n}.)

Aufgabe 3 Beweisen oder widerlegen Sie die folgenden Aussagen:

(a) Es existiert eine n mit W_{n} = {2n}.

(b) Es existiert eine n mit W_{n} = ℕ\{n}.

(c) Es existiert eine n mit W_{n} = {x | φ_{n}(x) ↑}.

(d) Es existiert eine n mit W_{n} = {x | ∃y[x = 2y ∧ φ_{n}(y) ↓]} und W_{n} ≠ ∅.

(e) Es existiert eine n mit W_{n} = {x | ∃y[x = 2y ∧ φ_{n}(y) ↓]} und W_{n} = {3}.

Aufgabe 4 Beweisen oder widerlegen Sie: Es gibt ein f mit W_{f(x)} = {f(x) + x}.

Aufgabe 5 Zeigen Sie: Es existiert kein φ_{e} ∈ C mit: Wenn φ_{x} die charakteristische Funktion χ_{F} einer endlichen Menge F ist, dann gilt φ_{e}(x) ↓ max F. Hinweis: Definieren Sie eine Funktion φ_{n} mit

φ_{n}(t + 1) = \begin{cases}1 & für t = μs[φ_{e,s}(n) ↓], \\ 0 & sonst. \end{cases}

Homepage der Vorlesung:

http://www.math.uni-bonn.de/people/logic/Lectures/SoSe2002/Welch.html
Newsgroup: uni-bonn.math.logik