MATHEMATISCHES INSTITUT Bonn, den 07.05.2002 DER UNIVERSITÄT BONN Prof. Dr. Philip Welch

Berechenbarkeitstheorie Aufgabenblatt 4

Aufgabe 1 Beweisen Sie Proposition 18: Die Relationen P und Q sind primitiv rekursiv. Dabei sind P und Q wie folgt definiert:

P (e, s, x⃗, z) :⇔ ϕ_{e,s}(x⃗) ≃ z,

Q(e, s, x⃗, z) :⇔ ϕ_{e,s}(x⃗) ↓ .

Aufgabe 2 Die Funktion f(x_{1}, x_{2}) sei partiell rekursiv. Finden Sie eine rekursive (d.h. \underline{total} rekursive) Funktion g(x_{1}, x_{2}), so daß gilt:

ϕ_{g(e_{1},e_{2})}(x_{1}) = f(ϕ_{e_{1}}(x_{1}), ϕ_{e_{2}}(x_{1})).

Aufgabe 3 Zeigen Sie, daß eine primitiv rekursive Funktion g(x_{1}, x_{2}, x_{3}) existiert, so daß gilt:

ϕ_{e}^{(3)}(x_{1}, x_{2}, x_{3}) = ϕ_{g(x_{1},x_{2},x_{3})}^{(1)}(e)

Aufgabe 4 Zeigen Sie, daß keine rekursive Funktion f(x) existiert, so daß gilt:

ϕ_{e}(e) ↓ ⇒ f(e) = ϕ_{e}(e) + 1.

Aufgabe^{∗} 5 Eine partiell rekursive Funktion g(x) heißt genau dann erweiterbar(=„extendable“), wenn eine total rekursive Funktion f(x) existiert, so daß g(x) ↓ ⇒ f(x) = g(x) gilt. Zeigen Sie unter Benutzung der Aussage von Aufgabe 4):

Es existiert keine rekursive Funktion f(x), so daß gilt:

f(e) = \begin{cases}1 & , wenn ϕ_{e}(x_{1}) erweiterbar ist. \\ 0 & , sonst. \end{cases}

Hinweis: Finden Sie eine erweiterbare Funktion k(x), so daß h(x, t) partiell rekursiv ist, wobei h(x, t) definiert ist durch

h(x, t) = \begin{cases}ϕ_{e}(x) + 1 & , wenn ϕ_{t}(t) ↓. \\ k(x) & , sonst. \end{cases}

Homepage der Vorlesung:

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