Übungen zur Vorlesung Mathematische Logik

SS 2009, Blatt 3

Aufgabe 1.

(a) Sei Σ = {a_{0}, …, a_{m}}. Zu W ⊆ Σ^{∗} sei

χ_{W} : Σ^{∗} ⟶ Σ^{∗} mit χ_{W} (x) = \{ \begin{matrix}λ & , x ∈ W \\ a_{0} & , x ∉ W \end{matrix}

die charakteristische Funktion von W. Zeigen Sie, daß W genau dann R-entscheidbar ist, wenn χ_{W} berechenbar ist.

(b) Für eine Funktion f mit df(f), bd(f) ⊆ Σ^{∗} sei

G_{f} := {(x, f(x)) | x ∈ df(f)}

der Graph von f. Zeigen Sie, daß G_{f} genau dann R-aufzählbar ist, wenn f berechenbar ist.

Aufgabe 2. Sei Π_{λ} := {x_{P} | P angesetzt auf λ druckt irgendwann λ aus}. Zeigen Sie, daß Π_{λ} nicht R-entscheidbar ist.

Aufgabe 3. Seien die beiden Funktionen f, g : ℕ⟶ℕ definiert durch

f(n) := \{ \begin{matrix}\frac{n}{2} & , n gerade \\ 3n + 1 & , n ungerade \end{matrix}

g(n) := \{ \begin{matrix}1 & , falls n = 0 \\ 1 & , falls f^{k}(n) = 1 für ein k ≥ 1 \\ undefiniert & , sonst \end{matrix}

Dabei ist f^{1} := f und f^{ℓ+1} := f ∘ f^{ℓ}.

1. Ist g berechenbar?

2. Ist g total? (vermutlich sehr schwierig)

3. (Freiwillig:) Berechnen Sie für n ∈ {15, 31, 85} das kleinste k mit f^{k}(n) = 1. Den Rechenweg brauchen Sie nicht mit abzugeben.

Aufgabe 4. Zeigen Sie, daß die folgenden Funktionen μ-rekursiv sind. Geben Sie dazu jeweils an, wie diese Funktionen aus den Ausgangsfunktionen durch die entsprechenden Prozesse gewonnen werden können.

1. Die Funktion c_{3} : ℕ⟶ℕ mit c_{3}(n) := 3.

2. Die Addition ⊕ : ℕ^{2}⟶ℕ mit ⊕(n, m) := n + m.

3. Die modifizierte Differenz ⊖ : ℕ^{2}⟶ℕ mit ⊖(n, m) := max{0, n − m}.

Aufgabe 5. Seien Σ und Π Alphabete und V ⊆ (Σ^{∗})^{r}, W ⊆ (Π^{∗})^{s} mit r, s ≥ 1. V heißt auf W polynomiell reduzierbar (V ≤_{p} W) genau dann, wenn es PTIME-Funktionen f_{1}, …, f_{s} von (Σ^{∗})^{r} nach Π^{∗} gibt, so daß für alle r-Tupel x̄ ∈ (Σ^{∗})^{r} gilt:

x̄ ∈ V ⟺ (f_{1}(x̄), …, f_{s}(x̄)) ∈ W.

Sei Γ ein weiteres Alphabet und U ⊆ (Γ^{∗})^{t} für t ≥ 1. Zeigen Sie:

1. Ist U ≤_{p} V und V ≤_{p} W, so ist U ≤_{p} W.

2. Ist V ≤_{p} W und W ∈ PTIME, so ist V ∈ PTIME.

3. Ist V ≤_{p} W und W ∈ NPTIME, so ist V ∈ NPTIME.

W ⊆ (Π^{∗})^{s} heißt NP-vollständig genau dann, wenn W ∈ NPTIME und für alle V ∈ NPTIME gilt V ≤_{p} W. Folgern Sie:

PTIME = NPTIME ⟺ W ∈ PTIME.

Abgabe: Mittwoch, 13. Mai, vor der Vorlesung.

Die Übungsblätter und die Einteilung der Übungen findet man auch unter

http://home.mathematik.uni-freiburg.de/bjoern/lehre/logik09/logik09.html