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

Berechenbarkeitstheorie Aufgabe 2

1. Zeigen Sie, dass die durch

σ(x) = Anzahl der Divisoren von x,
π(x) = Anzahl der Primzahlen kleiner oder gleich x

definierten Funktionen σ, π: ℕ → ℕ p.r. sind.

2. Finden Sie eine p.r. Funktion f: ℕ × ℕ → ℕ, so dass x ∗ y ≤ f(x, y) gilt. Hieraus folgt, dass wir ∗ p.r. definieren können durch

x ∗ y = min_{z≤f(x,y)}(Seq(z) ∧ …).

Hinweis: Finden Sie zunächst eine Funktion h: ℕ × ℕ → ℕ mit x ∗ y ≤ p_{lh(x)+lh(y)}^{h(x,y)}.

3. (Simultane Definition durch Rekursion) Die Funktionen g_{1}, g_{2}, h_{1} und h_{2} seien p.r. Wir definieren f_{1} und f_{2} durch

f_{1}(0, x⃗) = g_{1}(x⃗),
f_{2}(0, x⃗) = g_{2}(x⃗),
f_{1}(y + 1, x⃗) = h_{1}(x⃗, y, f_{1}(y, x⃗), f_{2}(y, x⃗)),
f_{2}(y + 1, x⃗) = h_{2}(x⃗, y, f_{1}(y, x⃗), f_{2}(y, x⃗)).

Zeigen Sie, dass f_{1} und f_{2} p.r. sind. Hinweis: Beweisen Sie, dass f̄(y, x⃗) = ≺f_{1}(y, x⃗), f_{2}(y, x⃗)≻ p.r. ist. Die Funktionen f_{1} und f_{2} können durch p.r mit f̄ und Komposition mit ℓ und r gewonnen werden.

4.^{∗} (Wertverlaufsrekursion) Die Funktion f sei total rekursiv. Wir definieren

f̄(y, x⃗) = ⟨f(0, x⃗), …, f(y − 1, x⃗)⟩.

Dies ist (noch) keine explizite Definition von f̄, weil sie von der Größe des Wertes y abhängig ist. Wir definieren statt dessen

f̄(y, x⃗) ≃ μz (Seq(z) ∧ lh(z) = y ∧ (∀i < y)((z)_{i+1} = f(i, x⃗))).

Beachten Sie, dass dann f(y − 1, x⃗) ≃ (f̄(y, x⃗))_{y} gilt. Betrachten Sie nun eine beliebige total rekursive Funktion g. Zeigen Sie:

(a) Durch

f(0, x⃗) = k,
f(y, x⃗) ≃ g(f̄(y, x⃗), y, x⃗)

(k ∈ ℕ eine Konstante) ist eine rekursive Funktion f definiert. Hinweis: Es reicht zu bemerken, dass f̄ rekursiv ist.

(b) Falls g p.r. ist, ist auch f p.r.