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

Berechenbarkeitstheorie Aufgabenblatt 5

Aufgabe 1 (a) Zeigen Sie: Es existiert eine partiell rekursive Funktion ψ, so daß

φ(x) ≃ μy[ψ(x, y) = 0] nicht partiell rekursiv ist.

(b) Warum widerspricht dieses Resultat nicht der μ-Abgeschlossenheit von Crm?

Hinweis: Überprüfen Sie die Definition von „μ-abgeschlossen“. Definieren Sie ψ(x, y) durch

ψ(x, y) := \begin{cases}0 & falls y = 1 oder (y = 0 ∧ φ_{x}(x) ↓) gilt. \\ ↑ & sonst. \end{cases}

Zeigen Sie dann, daß K rekursiv ist, wenn φ ∈ Crm gilt.

Aufgabe 2 Es sei E_{n} definiert durch

E_{n} :=_{df} {x | ∃y φ_{n}(y) = x} = ran φ_{n}.

Zeigen Sie, daß „n ∈ E_{n}“ nicht entscheidbar ist.

Aufgabe 3 Zeigen Sie:

(a) Es existiert kein Algorithmus, der entscheidet, ob ein Programm P_{e} eine Crm-Funktion φ_{e}^{(1)} mit φ_{e}^{(1)}(x) = x^{2} definiert.

(b) Es existiert kein Algorithmus, der für ein Paar von Indizes u, v ∈ ℕ entscheidet, ob

φ_{u}^{(1)}(x) = φ_{v}^{(1)}(x) gilt für alle x.

Homepage der Vorlesung:

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