Theoretische Informatik

Aufzählbarkeit über einstellige Funktionen
Geben Sie eine totale, berechenbare Funktion h : N → N mit Wh = B an. Beweisen Sie ausführlich die Gültigkeit der Inklusionen Wh ⊆ B und Wh ⊇ B.
B = {n ∈ N | es existieren Primzahlen p, q ≥ 2 mit n = p − q}

Allgemeines Halteproblem
Beweisen Sie: Das allgemeine Halteproblem K ist aufzählbar, aber nicht entscheidbar.

Entscheidbarkeit und Aufz ̈ahlbarkeit von Mengen

1. Sei f : N → N eine beliebige Funktion. Beweisen Sie die Entscheidbarkeit der Menge A1 ={m∈N|es existiert ein n∈N mit f(n) definiert und f(n)≥m}.
2. Beweisen Sie die Entscheidbarkeit der Menge A2 ={n∈N|es existieren Primzahlen p,q≥2 mit n=p+q}.
3. Sei f : N → N berechenbar. Beweisen Sie die Aufzählbarkeit der Menge A3 ={y∈N|∃x∈N mit f(x)=y}.
4. Sei M0, M1, . . . eine Gödelisierung aller RAMs. Beweisen Sie die Unentscheidbarkeit von A4 ={i∈N|Mi berechnet die Funktion g:N→N mit g(x)=x2}.
5. Sei M0, M1, . . . eine Gödelisierung aller RAMs. Beweisen Sie die Unentscheidbarkeit von A5 = {i ∈ N | Mi hält auf mindestens 3 Eingaben aus N}.

Loop-Programm für prim
Gesucht ist ein Loop-Programm (mit Syntaxprüfer testen!) für die auf Seite 45 definierte Funktion prim : Z → Z. Beweisen Sie, dass Ihr Programm die gewünschte Funktion berechnet. Begründen Sie dabei alle Aussagen und verweisen Sie möglichst nicht auf existierende, mathematische Sätze.

Entscheidbarkeit/Unentscheidbarkeit von Mengen
Sei M0,M1,... die in der Vorlesung definierte Gödelisierung aller RAMs. Für k ∈ N sei
A_k ={(i,j)∈N×N | i≤k und M_i(j)hält}.
Diskutieren Sie die Entscheidbarkeit/Unentscheidbarkeit der Mengen A₀, A₁, . . .! Begründen Sie Ihre Behauptungen!

unendliche entscheidbare Teilmenge
Beweisen Sie: Jede unendliche aufzählbare Menge A ⊆ N besitzt eine unendliche entscheidbare Teilmenge.