Rekursionstheorie

GeTEXt von Johannes Renner 13. Oktober 2003

Mitschrift zur Vorlesung von Prof.Dr.W.Thomas an der RWTH-Aachen im SS2003:

• Vertiefung von B.u.K.

• Tieferes Verständnis von ”Algorithmus“

• Attraktive Theorie

• Historische Quelle der Informatik

Fehler und Vorschläge bitte an johannes.renner@rwth-aachen.de. Auch falls jemand Lust hat zu helfen das Skript zu vervollständigen (handschriftliche Unterlagen vorhanden).

Inhaltsverzeichnis

1 Nummerierung von Programmen, Funktionen, Mengen 5 1.1 Grundlage 1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 1.2 Grundlage 2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6 1.3 Grundlage 3 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7

2 Primitiv rekursive und μ-rekursive Funktionen 9 2.1 Schema der primitiven Rekursion . . . . . . . . . . . . . . . . . . . . . . . 9 2.2 Schema der Einsetzung . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10 2.3 Beschränkte Summen, Produkte . . . . . . . . . . . . . . . . . . . . . . . 11 2.4 Primitiv rekursive Relationen . . . . . . . . . . . . . . . . . . . . . . . . . 12 2.5 Beschränkte Quantifizierung . . . . . . . . . . . . . . . . . . . . . . . . . . 12 2.6 Beschränkte Minimierung . . . . . . . . . . . . . . . . . . . . . . . . . . . 12 2.7 Bemerkungen zu prim.rek. Funktionen . . . . . . . . . . . . . . . . . . . . 13 2.8 μ-rekursive Funktionen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15 2.9 Kleene’sches Normalformtheorem (KNFT) . . . . . . . . . . . . . . . . . . 16 2.10 Existenz nicht-rekursiver Mengen . . . . . . . . . . . . . . . . . . . . . . . 18

3 Universelle Funktionen und Selbstbezüglichkeit 20 3.1 s-m-n-Theorem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21 3.2 Der Satz von Rice . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21 3.3 Rekursionssatz . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22

3.4 Bemerkungen zur Selbstbezüglichkeit . . . . . . . . . . . . . . . . . . . . . 23

4 Elementare Sachverhalte über aufzählbare Mengen 25 4.1 Reduktionsbeziehungen ≤_{1}, ≤_{m} . . . . . . . . . . . . . . . . . . . . . . . . 26

5 Reduktionsbegriffe und Grade 28 5.1 Satz von Myhill . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28 5.2 Satz von Cantor-Schröder-Bernstein . . . . . . . . . . . . . . . . . . . . . 28 5.3 Produktive und kreative Mengen . . . . . . . . . . . . . . . . . . . . . . . 30 5.4 Verbindungen zum Studium arithmetischer Theorien . . . . . . . . . . . . 31

1 Nummerierung von Programmen, Funktionen, Mengen

1.1 Grundlage 1

Drei Verwendungen von Algorithmen:

• als Berechnungsverfahren für (partielle) Funktionen

• als Entscheidungsverfahren für Mengen

• als Aufzählungsverfahren für Mengen Objekte, die manipuliert werden: endlich (z.B. Wörter, Zahlen). Hier: Bereich IN der natürlichen Zahlen

• Ein Algorithmus A berechnet die partielle Funktion f : IN^{n} → IN ⟺ bei Eingabe x̄ ∈ IN^{n} terminiert A, gdw. x̄ ∈ Def(f) und A liefert f(x̄) als Wert.

• A entscheidet A ⊆ IN^{n} ⟺ bei Eingabe x̄ ∈ IN^{n} terminiert A, und zwar mit Ausgabe 1(Ja), falls x̄ ∈ A und 0(Nein), sonst.

• A zählt A ⊆ IN^{n} auf ⟺ A liefert (gestartet ohne Eingabe) nach und nach in

irgendeiner Reihenfolge als Ausgaben genau die Elemente von A. Bei Existenz solcher Algorithmen sagen wir:

• f ”berechenbar“

• A ”entscheidbar“

• A ”aufzählbar“ 1.Bemerkung(Charakterisierung von ”entscheidbar“ durch ”aufzählbar“): A ⊆ IN^{n} entscheidbar ⟺ A aufzählbar und IN\A aufzählbar. Beweis: Folie.

2.Bemerkung(Charakterisierung von ”aufzählbar“ durch ”berechenbar“): A ⊆ IN^{n} aufzählbar ⟺ A = Def(f) für eine berechenbare Funktion f : IN^{n} → IN.

1.2 Grundlage 2

Der Begriff Algorithmus (zur Berechnung von Fkt.) ist mathematisch präzisierbar durch folgende Formalismen:

• λ-Kalkül (Church, 1936)

• Rekursive Funktionen (Gödel, Herbrand, Kleene, 1930-1936)

• Turingmaschinen (Turing, 1936)

• Post-Systeme (Post, 1936)

• Registermaschinen (Shepherdson, Sturgis, 1963)

f : IN^{n} → IN heisst rekursiv, wenn f durch einen dieser fünf Formalismen definierbar/berechenbar ist. Analog: ”rekursiv aufzählbar“ für ”aufzählbar“, ”rekursiv“ für ”entscheidbar“.

Im folgenden: Registermaschinen (unbeschränkte Registermaschinen, URM)

• Variablen X_{1}, X_{2}, … mit Werten in IN

• Ein URM-Programm ist eine Liste P = (I_{1}, …, I_{k}) von Instruktionen mit I_{k} = k stop und für 1 ≤ j ≤ k:

I_{j} = j Incr(X_{i}), oder

I_{j} = j Decr(X_{i}), oder

I_{j} = j if X_{i} > 0 goto l [else goto j + 1], 1 ≤ l ≤ k.

• Konfiguration K ist Folge (Progr. Zeilennummer, Wert v. X_{1}, Wert v. X_{2},…): K = (k_{0}, k_{1}, k_{2}, …), mit k_{i} = Wert von X_{i}, i > 0 und 1 ≤ k_{0} ≤ k.

• Folgekonfiguration K′ von K ist wie üblich definiert.

• P (x_{1}, …, x_{n}) ↓⟺ beginnend mit Konfiguration (1, x_{1}, …, x_{n}, 0, …) terminiert P, d.h. erreicht Konfiguration (k, y_{1}, y_{2}, …), wobei y_{1} das Ergebnis ist. In diesem Fall schreibe: P (x_{1}, …, x_{n}) ↓ y_{1}, sonst P (x_{1}, …, x_{n}) ↑.

• f : IN^{n} → IN ist URM-berechenbar ⟺ es existiert ein URM-Programm P, das f berechnet. D.h. für x̄ ∈ Def(f) gilt P (x_{1}, …, x_{n}) ↓ f(x̄), sonst P (x_{1}, …, x_{n}) ↑.

1.3 Grundlage 3

Programme (TM,…) sind endliche Objekte und damit nummerierbar.

1. Paarfunktion:

[ ] : IN^{2} → IN bijektiv, mit

[x, y] = 2^{x} · (2y + 1) − 1

Beachte: Jede Zahl ≥ 1 ist in Primfaktorenzerlegung schreibbar als 2^{x}·<Produkt ungerader Primzahlen>. [z]_{1} = Ergebnis von 2 in PFZ von z + 1, [z]_{2} analog.

2. Folgenkodierung: Sei p_{i} die i-te Primzahl (p_{0} = 2, p_{1} = 3, …) Bsp.: Kodiere (3, 0, 2) durch p_{0}^{4} · p_{1}^{1} · p_{2}^{3} = 2^{4} · 3 · 5^{3} Allgemeine Definition: <>: IN^{∗} → IN durch

< ϵ > = 1
< x_{0}, …, x_{n} > = p_{0}^{x_{0}+1} · · · · · p_{n}^{x_{n}+1}

Bem.: <> ist eine Bijektion.

Definition(URM-Programm-Codierung):

code(Incr(X_{i})) = [0, i]
code(Decr(X_{i})) = [i, 0]
code(if X_{i} > 0 goto l) = [i, l]
code(stop) = 0

Für P = (I_{1}, …, I_{k}) setze code(P) =< code(I_{1}), …, code(I_{k}) >.

Beispiel:

P_{∞}: 1 Incr(X_{1})

2 if X_{1} > 0 goto 1 3 stop

→ code(P_{∞}) =< [0, 1], [1, 1], 0 >=< 2, 5, 0 >= 2^{3} · 3^{6} · 5^{1}

Nicht jede Zahl kodiert ein Programm.

Definition: Für e ∈ IN, setze

P_{e} = \{ \begin{matrix}P, & falls code(P) = e \\ P_{∞}, & sonst \end{matrix}

Für e ∈ IN, n ≥ 1 definiere φ_{e}^{(n)} : IN^{n} → IN durch

φ_{e}^{(n)}(x_{1}, …, x_{n}) = \{ \begin{matrix}y, & falls P_{e}(x_{1}, …, x_{n}) ↓ y \\ ⊥, & falls P_{e}(x_{1}, …, x_{n}) ↑ \end{matrix}

Für n = 1 schreibe φ_{e}.

Bemerkung: Jede URM-berechenbare Funktion f hat die Form

f = f_{e}^{(n)}, (e Index von f)

Daraus: Nummerierung der aufzählbaren Mengen ⊆ IN^{n}:

W_{e}^{(n)} := Def(φ_{e}^{(n)})

Dann: Jede aufzählbare Menge M ⊆ IN^{n} hat die Form

M = W_{e}^{(n)}, (n = 1 : W_{e})

Interessante aufzählbare Menge:

K = {e ∈ IN|e ∈ W_{e}} = {e|P_{e}(e) ↓}

2 Primitiv rekursive und μ-rekursive Funktionen

Grassmann, Dedekind 1888 • x + 0 = x, x · 0 = 0

• x + S(y) = S(x + y)

• x · S(y) = (x · y) + x S Nachfolgerfunktion: 0! = 1, S(y)! = y! · S(y)

2.1 Schema der primitiven Rekursion

Aus g : IN^{n} → IN und h : IN^{n+2} → IN entsteht f : IN^{n+1} → IN durch primitive Rekursion (prim.Rek.), wenn

\begin{matrix}f(x̄, 0) & = & g(x̄) \\ f(x̄, S(y)) & = & h(x̄, y, f(x̄, y)) \end{matrix} \} (∗)

Bemerkung:

1. (∗) definiert f eindeutig.

2. Anwendung des Schemas auf partielle Funktionen möglich.

f(x̄, y) =⊥, falls einer der Werte f(x̄, 0), …, f(x̄, y − 1) oder h(x̄, y, f(x̄, y − 1)) undefiniert ist.

Beispiele:

1. ’+’ entsteht aus g = id_{IN} und folgendem h durch prim.Rek.: h(x, y, z) = S(z).

2. ’ · ’ entsteht aus der 1-stelligen Konstante 0 und folgendem h durch prim.Rek.: h(x, y, z) = z + x.

2.2 Schema der Einsetzung

Aus h : IN^{m} → IN und g_{1}, …, g_{m} : IN^{n} → IN entsteht f : IN^{n} → IN durch Einsetzung, falls f(x̄) = h(g_{1}(x̄), …, g_{m}(x̄)).

Bemerkung: Anwendung auf partielle Funktionen möglich: f(x̄) undefiniert, falls ein g_{i}(x̄) undefiniert oder alle g_{i}(x̄) definiert und h(g_{1}(x̄), …, g_{m}(x̄)) undefiniert.

Basisfunktionen sind:

• Nachfolgerfunktion S,

• für n ≥ 0 jeweils die n-stellige Konstante, 0 : c_{0}^{(n)},

• für n ≥ 1, 1 ≤ i ≤ n, die i-te n-stellige Projektion p_{i}^{(n)}(x̄) = x_{i}.

Definition: Eine Funktion heisst primitiv rekursiv (prim.rek.), falls sie aus Basisfunktionen durch endlichmalige Anwendung von Einsetzung und primitiver Rekursion entsteht.

Beispiele:

1. ’+’ ist prim.rek.

’+’ entsteht aus g = p_{1}^{(1)}(= id_{IN}) und h(x, y, z) = S(z) durch prim.Rek.

genauer: h(x, y, z) = S(p_{3}^{(3)}(x, y, z)), h entsteht aus S und p_{3}^{(3)} durch Einsetzung, ist also prim.rek.

2. ’ · ’ entsteht aus c_{0}^{(1)} und h(x, y, z) = z + x durch prim.Rek. h(x, y, z) = + (p_{3}^{(3)}(x, y, z), p_{1}^{(3)}(x, y, z)), also ist h prim.rek.

Argument-Lemma: Sei f(x_{1}, …, x_{n}) = g(x_{i_{1}}, …, x_{i_{m}})({i_{1}, …, i_{m}} ⊆ {1, …, n}). Wenn g prim.rek., dann ist auch f prim.rek. Begründung: f(x̄) = g(p_{i_{1}}^{(n)}(x̄), …, p_{i_{m}}^{(n)}(x̄)), Einsetzung mit prim.rek. Funktionen.

Beispiele:

1. Potenzfunktion:

pot(x, y) = x^{y}
pot(x, 0) = c_{1}^{(1)}
pot(x, S(y)) = \underbrace{pot(x, y) · x}_{prim.rek. analog ’ · ’} [x^{4+1} = x^{4} · x]

Zu c_{1}^{(1)}(x) = S(c_{0}^{(1)}(x)) analog: Jede Konstante c_{k}^{(n)} ist prim.rek.

2. Vorgängerfunktion: V : IN → IN, mit

V (x) = \{ \begin{matrix}x − 1, & falls x > 0 \\ 0, & sonst \end{matrix}

Notation: x ˙−1

V (0) = c_{0}^{(0)}
V (S(y)) = h(y, V (y))

wähle h = p_{1}^{(2)}

3. x ˙−y über

4. |x − y| = (x ˙−y) + (y ˙−x)

5. Signum-Funktion:

sg(x) = \{ \begin{matrix}0, & falls x = 0 \\ 1, & falls x > 0 \end{matrix}

prim.rek.:

sg(0) = c_{0}^{(0)}
sg(S(y)) = c_{1}^{(2)}(y, sg(y))

\overline{sg}(x) = \{ \begin{matrix}0, & falls x > 0 \\ 1, & falls x = 0 \end{matrix}

analog mit c_{1}^{(0)}, c_{0}^{(2)}.

2.3 Beschränkte Summen, Produkte

Zu g : IN^{n+2} → IN bilde

sum_{g}(x̄, y) := ∑_{z=0}^{y} g(x̄, y, z)

Ist g prim.rek., so auch sum_{g}. Analog für Π.

Beweis: Betrachte F (x̄, y, t) := ∑_{z=0}^{t} g(x̄, y, z):

F (x̄, y, 0) = g(x̄, y, 0) = G(x̄, y)
F (x̄, y, S(t)) = \underbrace{F (x̄, y, t) + g(x̄, y, S(t))}_{H(x̄,y,F (x̄,y,t)) prim.rek.}

sum_{g}(x̄, y) = F (x̄, y, y)

2.4 Primitiv rekursive Relationen

Zu R ⊆ IN^{n} sei χ_{R} : IN^{n} → IN die charakteristische Funktion von R:

χ_{R}(x̄) = \{ \begin{matrix}1, & falls x̄ ∈ R \\ 0, & falls x̄ ∉ R \end{matrix}

R heisst prim.rek., falls χ_{R} prim.rek. Beispiele:

• x ≠ y prim.rek.: χ_{≠}(x, y) = sg(|x − y|)

(< ähnlich)

• x = y prim.rek.: χ_{=}(x, y) = \overline{sg}(|x − y|)

• Sind R_{1}, R_{2} ⊆ IN^{n} prim.rek., so auch R_{1} ∪ R_{2}, R_{1} ∩ R_{2}, IN^{n}\R_{1}:

χ_{R_{1}∪R_{2}}(x̄) = sg(χ_{R_{1}}(x̄) + χ_{R_{2}}(x̄))

(∩, \ ähnlich)

2.5 Beschränkte Quantifizierung

Zu R ⊆ IN^{n+2} bilde Q_{E} ⊆ IN^{n+1} und Q_{A} ⊆ IN^{n+1}:

Q_{E} x̄, y ⟺ ∃ z ≤ y, so dass R x̄yz

Ist R prim.rek., so auch Q_{E}, Q_{A}. Begründung: χ_{Q_{E}}(x̄, y) = sg(∑_{z=0}^{y} χ_{R}(x̄, y, z)). Für Q_{A} analog mit Π. Beispiele:

• x|y ist prim.rek.: x|y ⟺ ∃z x · z = y.

• P x(x ist Primzahl) ist prim.rek.:

P x ⟺ x ≠ 0 ∧ x ≠ 1 ∧ ∀z ≤ x (z = 1 ∨ z = x ∨ ¬z|x)

2.6 Beschränkte Minimierung

[R prim.rek. → f prim.rek.] Zu R ⊆ IN^{n+1} definiere f : IN^{n+1} → IN durch

f(x̄, y) = \{ \begin{matrix}kleinstes z ≤ y mit R x̄yz, & falls solches z existiert \\ y, & sonst. \end{matrix} kurz f(x̄, y) = μz ≤ y Rx̄yz.

Behauptung: R prim.rek. ⟹ f prim.rek.

Beweis: F (x̄, y, t) = μz ≤ t R x̄yz F prim.rek., dann auch f, fertig.

F (x̄, y, 0)  = 0 = c_{0}^{(n+1)}(x̄, y)
F (x̄, y, S(t)) = \{ \begin{matrix}F (x̄, y, t), & falls ∃z ≤ t Rx̄yz \\ S(t), & sonst. \end{matrix}
= F (x̄, y, t) · χ_{Q}(x̄, y, t) + S(t) · χQ̄(x̄, y, t)
=: h(x̄, y, t, F (x̄, y, t)) prim.rek.

2.7 Bemerkungen zu prim.rek. Funktionen

1. f prim.rek. ⟺ f ist LOOP-berechenbar, d.h. durch ein sog. LOOP-Programm berechenbar. LOOP-Programme haben

• Wertzuweisungen: X_{i} := X_{i} + 1, X_{i} := X_{i} − 1

• Tests: X_{i} > 0?

< LP >::= W ertzuweisung| < LP >; < LP > |if T est then < LP > else < LP > | loop X_{i} begin < LP > end

Semantik von ”loop X_{i} begin P end“: führe P so oft durch wie anfangs Wert von X_{i} Beispiel: X_{1} := X_{1} + X_{2} ≡ ” loop X_{2} begin X_{1} := X_{1} + 1 end“ Bem.: WHILE-Programme entstehen durch Hinzunahme von

W hile T est do P end

2. Es gibt viele Varianten von Rekursionsschemata, die auf prim.Rek. zurückführbar sind:

a) Wertverlaufsrekursion:

f(x̄, 0) = g(x̄)
f(x̄, S(y)) = h(x̄, y, < f(x̄, 0) >, …, < f(x̄, y) >)

b) Simultane Rekursion:

f_{1}(x̄, 0) = g_{1}(x̄)
f_{2}(x̄, 0) = g_{2}(x̄)
f_{1}(x̄, S(y)) = h_{1}(x̄, y, f_{1}(x̄, y), f_{2}(x̄, y))
f_{2}(x̄, S(y)) = h_{2}(x̄, y, f_{1}(x̄, y), f_{2}(x̄, y))

g_{1}, g_{2}, h_{1}, h_{2} prim.rek. ⟹ f_{1}, f_{2} prim.rek.

c) Rekursion mit Parameterwechsel:

f(x, 0) = g(x)
f(x, S(y)) = h(x, y, f(w(x), y))

g, h, w prim.rek. ⟹ f prim.rek.

3. Ackermann-Funktion A : IN^{2} → IN, eine durch Rekursion definierte totale, nicht prim.rek. Funktion.

A(0, y) = S(y)
A(S(x), 0) = A(x, 1)
A(S(x), S(y)) = A(x, A(S(x), y))

Auswertungsbeispiel:

A(1, 3) = A(0, A(1, 2))
= A(0, A(0, A(1, 1)))
= A(0, A(0, A(0, A(1, 0))))
= A(0, A(0, A(0, A(0, 1))))
= 5

Behauptung: Die Auswertung ist eindeutig und terminiert für alle x,y.

Wertabschätzungen:

A(0, y) > y A(3, y) > 2^{y}

A(1, y) > S(y) A(4, y) > 2^{2^{·^{·^{2}}} }y} A(2, y) > 2y A(5, 4) > 10^{10000}

Satz: A ist nicht prim.rek.

Beweisansatz: Lemma: Zu jeder prim.rek. Funktion f : IN^{n} → IN existiert k_{f} mit A(k_{f}, max(x̄)) > f(x̄). (Beweis über Aufbau der prim.rek. Funktionen.)

Es gibt Hierarchie der ”mehrfach rekursiven Funktionen“ (Rekursion in m Argumenten für m ≥ 2), siehe Buch von R.Peter.

2.8 μ-rekursive Funktionen

Zu g : IN^{n+1} → IN entsteht f : IN^{n} → IN durch Anwendung des μ-Operators (unbeschränktes Minimun), falls

f(x̄) = \{ \begin{matrix}kleinstes y mit g(x̄, y) = 0, & falls ∀z < y : g(x̄, y) definiert und y ≠ 0 \\ ⊥, & sonst. \end{matrix}

kurz: f(x̄) = μy g(x̄, y) = 0. Beispiele:

• g(x, y) = |x − y| f(x) = μy |x − y| = 0

f(x) = x

• g(x, y) = x + y f(x) = μy x + y = 0

f(x) = \{ \begin{matrix}0, & x = 0 \\ ⊥, & x ≠ 0 \end{matrix}

f heisst μ-rekursiv, falls f aus den Basisfunktionen durch Anwendung von Einsetzung, prim.Rek. und μ-Operator entsteht. Beispiel: ”3x + 1“-Funktion

h(x) = \{ \begin{matrix}x/2, & falls x gerade \\ 3x + 1, & falls x ungerade \end{matrix}
g(x, y) = h^{y}(x) ˙−1
f(x) = μy g(x, y) = 0

Offen: Ist f total? Bemerkung: f μ-rekursiv ⟺ f durch ein WHILE-Programm berechenbar? Intuitive Korrespondenz:

Einsetzung ∼ Verkettung
prim.Rek. ∼ LOOP
μ-Operator ∼ WHILE

Bemerkung: Die Ackermann-Funktion ist μ-rekursiv. Frage 1: Erfassen die μ-rekursiven Funktionen alle URM-berechenbaren Funktionen? Frage 2: Nötige Anwendungen des μ-Operators in Anzahl beschränkbar?

2.9 Kleene’sches Normalformtheorem (KNFT)

Es gibt eine prim.rek. Funktion U : IN → IN und zu n ≥ 1 jeweils ein n + 2-stelliges prim.rek. Prädikat T_{n} ⊆ IN^{n+2}, so dass: Jede URM-berechenbare Funktion f : IN^{n} → IN lässt sich darstellen als

f(x̄) = U(μy T_{n}ex̄y) [:= \overline{sg}(χ_{T_{n}}(ex̄y)) = 0]

für geeignetes e, nämlich Code eines URM-Programms, das f berechnet. kurz: φ_{e}^{(n)}(x̄) = U(μy T_{n}ex̄y).

Beweis: Definition von T_{n}:

T_{n} ex̄y ⟺ e ist Code eines URM-Programms (P_{e}) und P stoppt auf Eingabe x̄ nach [y]_{1} Schritten mit Konfiguration, deren Code [y]_{2} ist. (y = [[y]_{1}, [y]_{2}]) Benutze Code < l, z_{1}, …, z_{m} > für Konfiguration K = (l, z_{1} = W ert(X_{1}), …, z_{m} = W ert(X_{m})) Genügt Betrachtung von X_{1}, …, X_{m} für m = m_{n}(e) = Max. von Stellenzahl n und grösstem in P_{e} auftretendem Variablenindex (m_{n} prim.rek.). U extrahiert aus y das Ergebnis (W ert(Y_{1})) der kodierten Konfiguration: U(y) =< [y]_{2} >_{1}, U prim.rek.

T_{n} prim.rek.:

1. Zeige, dass das Prädikat Ce ⟺ e ist Programmcode prim.rek.

2. S_{n} ”Schrittfunktion“ prim.rek. liefert Code von Konfiguration zu geg. Schrittzahl.

3. T_{n}

zu 1. Prüfe, ob e =< code(I_{1}), …, code(I_{k}) > im einzelnen: < e >_{len(e)−1}= 0

Für alle x < len(e) − 1 muss gelten < e >_{x}≠ 0, und:

wenn [< e >_{x}]_{1} ≠ 0, [< e >_{x}]_{2} ≠ 0 dann 1 ≤ [< e >_{x}]_{2} ≤ len(e) prim.rek. gemäss Schema der beschränkten Allquantifizierung.

Zuvor: Test, ob e Folge kodiert.[len(e) ≠ 0]

zu 2. Definiere:

S_{n}(e, x̄, z) = \{ \begin{matrix}0, & falls nicht Ce \\ 0, & Ce, P e auf x̄ stoppt vor Schritt z \\ Code der z-ten Konf. \\ von P e auf x̄, & sonst. \end{matrix}

S_{n} prim.rek.:

S_{n}(e, x̄, 0) = \{ \begin{matrix}0, & falls ¬Ce \\ p_{0}^{1+1} · p_{1}^{x_{2}+1} · · · · · p_{n}^{x_{n}+1} · p_{n+1}^{1} · · · · · p_{m_{n}(e)}^{1}, & falls Ce \end{matrix}
= c_{0}^{n+1} · \overline{sg}(χ_{c}(e)) + p_{0}^{1+1} · · · · · p_{m_{n}(e)}^{1} · χ_{c}(e)

< 1, x_{1}, …, x_{n}|0, …, \underbrace{0}_{m_{n}(e)} >

S_{n}(e, x̄, S(z)) = \{ \begin{matrix}h_{1}(e, x̄, z, S_{n}(e, x̄, z)), & Konfig. S_{n}(e, x̄, z) verlangt Incr \\ h_{2}, & analog für Dekrement \\ h_{3}, & analog für Sprunganweisung \\ 0, & S_{n}(e, x̄, z) kodiert Stopkonfig. \end{matrix}

Fallunterscheidung prim.rek. wie bei z=0.

Fall h_{1}:

\begin{matrix}< e >_{aktuelleAnweisung} & = & < e >_{<S_{n}(e,x̄,z)>_{0}−1} \\ & = & [0, y] \end{matrix} \} (∗)

h_{1}(e, x̄, S(z)) = S_{n}(e, x̄, z) · \underbrace{p_{0}}_{nächste Anw.} · \underbrace{p_{k}}_{W erterhöhung} mit k = μy ≤ e (∗)

zu 3. T_{n}ex̄y :

e ist Programmcode, S_{n}(e, x̄, [y]_{1}) = [y]_{2} mit: \underbrace{[y]_{2} kodiert Stopkonfiguration}_{<[y]_{2}>_{0}=len(e)}.

Bemerkungen zum T_{n}-Prädikat:

• ∃y T_{n}ex̄y ⟹ solches y eindeutig bestimmt.

• ∃y T_{n}ex̄y ⟺ e kodiert Programm, P_{e} stoppt auf x̄.

Folgerungen aus KNFT:

1. Jede μ-rekursive Fkt. ist definierbar mit nur einer Anwendung des μ-Operators. Dazu: Aus Definition von f gehe zu URM-Programm über (induktiv), dann Anwendung von KNFT.

2. Programmiersprachliche Deutung:

Jedes WHILE-Programm (mit LOOP- und WHILE-Schleifen) lässt sich umformen in ein WHILE-Programm mit nur einem WHILE-Statement. Beweis: WHILE-Programm ⇒ URM-Programm ⇒ KNFT-Form ⇒ WHILE-Programm.

KNFT besagt: Jede URM-berechenbare Funktion ist μ-rekursiv. Bemerkungen zu Äquivalenzbeweisen:

• A. Operationelle, nichtstrukturierte Modelle: URM-Programme, Flussdiagramme, TM’s

• B. Kompositionelle Modelle: WHILE-Programme, rek. Funktionen, λ-Kalkül

Simulationen:

A ⟶ A : schrittweise Simulation
B_{1} ⟶ B_{2} : induktiv über B_{1}
B ⟶ A : induktiv über B
A ⟶ B : Kodierung von A-Konfiguration durch Update-Schritte in B

B-Programm ≃ B-Interpreter für A-Programme.

2.10 Existenz nicht-rekursiver Mengen

K = {e|∃y T_{1}eey} = {e|φ_{e}(e) ↓} = {e|e ∈ W_{e}(= Def(φ_{e})}

Annahme: K rekursiv, λ_{K} rekursiv. Definition:

f(x) = \{ \begin{matrix}0, & x ∉ K \\ ⊥, & x ∈ K \end{matrix} (rekursiv)
f(x) = μy (χ_{K}(x)) + y = 0

wähle zu f ein e mit f(x) = φ_{e}(x)

φ_{e}(x) ↓⇔ φ_{e}(x) = 0 ⇔ φ_{x}(x) ↑

x = e Widerspruch!

T ot = {e|φ_{e} total} = {e|∀x∃y T_{1}exy}

Behauptung: T ot ist nicht rekursiv. Zu e stellen wir folgendes Programm her:

\begin{matrix}X1 := 0 \\ X1 := e \\ P_{e} \end{matrix} \} P_{f(e)}, f rekursiv

P_{e}(e) ↓ ⟺ P_{f(e)}(x) ↓, ∀x
e ∈ K ⟺ f(e) ∈ T ot
χ_{K}(x) = χ_{T} ot(f(x))

Da K nicht rekursiv ist folgt: T ot ist nicht rekursiv.

3 Universelle Funktionen und Selbstbezüglichkeit

Definiere φ^{n+1}(e, x̄) = U(μy T_{n}ex̄y)

Bemerkung: Nach Def. ist φ^{n+1} rek. Für jedes n-stellige rek. f ex. e, so dass f(x̄) = φ^{n+1}(e, x̄).

Definition: Sei K eine Klasse von n-stelligen Funktionen. F : IN^{n+1} → IN heisst universell für K, falls

• für jedes f ∈ K ex. e mit f(x̄) = F (e, x̄)

• für jedes e ∈ IN ist die Funktion λx̄ F (e, x̄) ∈ K

Satz: φ^{n+1} ist universell für Klasse RF_{n} der n-stelligen rekursiven Funktionen, und ist selbst rekursiv.

Definition:

• T RF_{n} sei Klasse der n-stelligen totalen rek. Funktionen

• P RF_{n} sei Klasse der n-stelligen prim.rek. Funktionen

Satz: Es gibt für T RF_{n} und P RF_{n} keine universelle Fkt., die selbst total und rekursiv, bzw. prim.rek. ist.

Beweis: T RF_{1} (P RF_{1} analog) Annahme: F : IN^{2} → IN universell für T RF_{1} total, rek. f(x) = F (x, x) + 1 total und rekursiv. Wähle e mit F (e, x) = f(x) x = e: F (e, e) = f(e) = F (e, e) + 1

Konsequenz: Die totalen berechenbaren Funktionen haben keinen effektiven Programmierformalismus durch nummerierbare Programme P_{i}, so dass:

• Jedes P_{i} berechnet totale Funktion • Jede totale berechenbare Funktion wird durch ein P_{i} berechnet

• Die Auswertungsfunktion F (i, x) = P_{i}(x) ist berechenbar

Bemerkung: Man kann für die rekursiven Funktionen (partiell!) so nicht schliessen: kein Widerspruch durch Existenz einer universellen Funktion f(x) = ϕ^{(2)}(x, x)+1 ∈ RF_{1} wähle e : f(x) = ϕ^{(2)}(e, x) dann: ϕ^{(2)}(e, e) = f(e) = ϕ^{(2)}(e, e) + 1 → kein Widerspruch, da ϕ^{(2)}(e, e) =⊥ sein kann.

Historische Bemerkung: Idee der Diagonalisierung geht auf Cantor zurück:

|IR| > |IN|

Hier: Die Menge der unendlichen 0-1-Folgen ist überabzählbar. Anmerkung: Abzählbarkeit diser Menge liefert Schema aller 0-1-Folgen:

β_{0} = β_{0}(0)β_{0}(1)β_{0}(2) …
β_{1} = β_{1}(0)β_{1}(1)β_{1}(2) …
…

Jede Folge kommt als ein β_{i} vor. Setze β(i) := \overline{β_{i}(i)} wähle e, so dass β = β_{e}

β_{e}(e) = β = β_{e}(e)

3.1 s-m-n-Theorem

Für m, n ≥ 1 gibt es totale rekursive Funktion s_{n}^{m} : IN^{m+1} → IN mit

φ_{e}^{(m+n)}(x̄, ȳ) = φ_{s_{n}^{m}(e,x̄)}(ȳ)

Beweis: Zu e, x̄ setze s_{n}^{m}(e, x̄) fest als Code für folgendes Programm P [e, x̄]. P [e, x̄]: Bringe Argumente ȳ von X_{1}, …, X_{n} in Variablen X_{m} + 1, …, X_{m} + n

X_{1} := x_{1}, …, X_{m} := x_{m}; P_{e}

Dann ist die Gleichung erfüllt. Nach Def. ist s_{n}^{m} rekursiv.

3.2 Der Satz von Rice

A ⊆ IN repräsentiere semantische Programmeigenschaft, wenn es eine Funktionenklasse F gibt mit

e ∈ A ⟺ φ_{e} ∈ F

Beispiel:

• ”P_{e} hat 17 Zeilen“ ist nicht semantisch

• ”P_{e} terminiert immer“ ist semantisch (mit F = T ot)

A heisse trivial, falls A = ∅ oder A = IN. Satz von Rice: Jede nichttriviale Menge, die semantische Programmeigenschaft repräsentiert, ist unentscheidbar. Beweis: Zu A betrachte F, wähle

a ∈ A φ_{a} ∈ F
b ∉ A φ_{b} ∉ F

Benutze K = {x|φ_{x}(x) ↓} unentscheidbar. Ziel: Finde tot. berechenbares f:

x ∈ K ⟺ f(x) ∈ A

Dann kann A nicht entscheidbar sein. Fertig. Betrachte c_{⊥}^{(1)} ∉ F (2.Fall analog) Definiere

g(x, y) = \{ \begin{matrix}φ_{a}(y), & x ∈ K \\ ⊥, & sonst \end{matrix}

Es gilt: x ∈ K ⟺ s_{1}^{1}(x) ∈ A Dann: x ∈ K ⇒ φ_{s_{1}^{1}(x)}(y) = φ_{a}(y) ⇒ s_{1}^{1}(x) ∈ A (da a ∈ A) (∗) Erinnerung: x ∈ K ⟺ ∃z T_{1}xxz g rek., g(x, y) = φ_{e}^{(2)}(x, y), smn : φ_{e}(x, y) = φ_{s_{1}^{1}(x)}(y), s_{1}^{1} tot.rek. (∗)x ∉ K: φ_{s_{1}^{1}(x)} = c_{⊥}^{(1)} (∉ F, 1.Fall), s_{1}^{1}(x) ∉ A

3.3 Rekursionssatz

Sei f : IN → IN total, rekursiv. Dann existiert e mit φ_{e} = φ_{f(e)}. Sabotage: e ↦ f(e), φ_{e} ≠ φ_{f(e)} Beweis: Betrachte

g(y, x) = \{ \begin{matrix}φ_{z}(x), & falls φ_{y}(y) ↓ und = z \\ ⊥, & sonst \end{matrix}

g rekursiv. smn : g(y, x) = φ_{s_{1}^{1}(y)}(x), s_{1}^{1} tot., rek. Also:

φ_{s_{1}^{1}(y)}(x) = \{ \begin{matrix}φ_{φ_{y}(y)}(x), & falls φ_{y}(y) ↓ \\ ⊥, & sonst \end{matrix}

Definiere zu f gemäss Vorraussetzung eine Fkt. h : IN → IN mit h(y) = f(s_{1}^{1}(y)). Da s_{1}^{1}, f tot., rek., ist auch h tot., rek. wähle i mit φ_{i}(y) = h(y), φ_{i} total, also φ_{i}(i) ↓.

φ_{s_{1}^{1}(i)}(x) = φ_{φ_{i}(i)}(x) = φ_{f(s_{1}^{1}(i))}(x)

wegen φ_{i}(y) = h(y) = f(s_{1}^{1}(y)) setze e = s_{1}^{1}(i).

1. Anwendung: Es gibt ein (URM-)Programm, das für jeden Input (∈ IN) seine eigene Codezahl e ausgibt.

Beweis: g(x, y) = x, smn : g(x, y) = φ_{s_{1}^{1}(x)}(y)

Nach Rekursionssatz existiert e mit φ_{e} = φ_{s_{1}^{1}(e)}

φ_{e}(y) = φ_{s_{1}^{1}(e)}(y) = g(e, y) = e

Also: P_{e} liefert für Eingabe y die Zahl e als Ausgabe.

2. Anwendung: Es existiert e, so dass: W_{e} = e(= Def(φ_{e})).

Betrachte

g(x, y) = \{ \begin{matrix}0, & falls x = y \\ ⊥, & sonst. \end{matrix}

smn : g(x, y) = φ_{s_{1}^{1}(x)}(y), Def(φ_{s_{1}^{1}(x)}) = x nach Definition von g.

Rekursionstheorem liefert e: φ_{e} = φ_{s_{1}^{1}(e)}

W_{e} = Def(φ_{e}) = Def(φ_{s_{1}^{1}(e)}) = e

3.4 Bemerkungen zur Selbstbezüglichkeit

1. Gödel’s Unvollständigkeitssatz (1931) zeigt:

Das Beweissystem der Peano-Arithmetik (Peano-Axiome für alle 1.Stufe Formeln, Beweiskalkül für Logik 1.Stufe) ist unvollständig: Es gibt einen in (IN, +, ·, 0, 1) wahren Satz, der nicht herleitbar ist.

Ansatz: Wähle Satz, der sagt ”Ich bin nicht beweisbar.“

Durchführung:

a) Kodiere Sätze, Formeln und Beweise durch Zahlen.

b) Konstruktion einer Formel

beweis(x, y) := ”y ist Code eines Beweises für Satz x“

Hieraus: bewbar(x) := ∃y beweis(x, y)

c) Betrachte m ↦ f(m) mit f(m) = Code von ¬bewbar(m) Rekursionssatz liefert e mit f(e) = e, e = Code von ¬bewbar(e)

d) Satz mit Nr. e sagt: ”Ich bin nicht beweisbar.“

2. Selbst(re-)produktion in physikalischen Systemen benutzt Realisierung von Codes, kodierten Objekten.

Operationen: Konstruktor Kon : e ↦ P_{e} Kopierer Kop : e ↦ neue Kopie von e Reproduzierer Repr : e ↦ P_{e}, e (Kombination von Kon und Kop)

Falls Reproduzierer einen Code besitzt (e_{R}) Repr : e_{R} ↦ Repr, e_{R}.

Realisierung in biolog. Systemen: Code eines Objekts(Lebewesen)=Genom(DNA)

Kon : Protheinsynthesemechanismus
Kop : RNA-Polymerase
Repr mit e_{R} : Zelle und ihr Genom

Vorraussetzung: Umgebung hält Substrate bereit (Proteinsuppe)

3. Von Neumann-Modell der zellularen Automaten.

Zell. Automat: (Z×Z)-Anordnung von Kopien eines einzigen endlichen Automaten. Konfiguration ist endliches Arrangement von Zuständen (sonst: Ruhezustand).

C, B ⟶ C, B, B ⟶ … (C, B Automaten, auch für B = C)

C wurde konstruiert durch v. Neumann mit 29 Zuständen, durch Conway mit 2 Zuständen.

4 Elementare Sachverhalte über aufzählbare Mengen

Signifikanz: A aufzählbar ⟺ die A-Elemente können durch systematischen Prozess sukzessiv erzeugt werden.

Musterbeispiel: Sätze einer axiomatisierten Theorie.

Intuitive Definition: A = {f(0), f(1), f(2), …} für ein totales, berechenbares f. Bisher: A = Def(g) für berechenbares g.

Satz: ∅ ≠ A ⊆ IN ist Bild(f(IN)) einer tot. rek. Funktion f ⟺ A = Def(g) für rekursive Funktion g.

Beweis:

• “⟸“:

Interessant |A| = ∞ g(x) = Uμy T exy

Idee: Gehe Paare (x, y) mit T exy durch und produziere jeweils x als Wert.

f(0) = [μt T e \underbrace{[t]_{1}}_{x} \underbrace{[t]_{2}}_{y}]_{1}
f(z + 1) = [μt t > f(z) ∧ T e[t]_{1}[t]_{2}]_{1}

• “⟹“:

Zu f wähle Index e

z ∈ A ⟺ ∃x f(x) = z
⟺ ∃x∃y (T exy ∧ U(y) = z)
⟺ μy (T exy ∧ U(y) = z)
⟺ ∃t (T e[t]_{1}[t]_{2} ∧ U([t]_{2}) = z)

g(z) = μt(…), Def(g) = A.

4.1 Reduktionsbeziehungen ≤_{1}, ≤_{m}

K = {x|φ_{e}(e) ↓} = {x|∃y T eey}

Hieraus: K ist rekursiv aufzählbar (recursively enumerable): Gehe alle Paare (e, y) durch und gebe e aus, wenn T eey gilt. A, B ⊆ IN:

A ≤_{m} B ⟺ es ex. rek. tot. f : IN → IN mit: x ∈ A ⟺ f(x) ∈ B

schreibe f : A ≤_{m} B, A ≤_{1} B : verlange zusätzlich, dass f injektiv. Bemerkungen:

1. ≤_{1}, ≤_{m} reflexiv, transitiv

2. A ≤_{1} B ⟹ A ≤_{m} B

3. A ≤_{1} B ⟹ \overline{A} ≤_{1} \overline{B}, A ≤_{m} B ⟹ \overline{A} ≤_{m} \overline{B}

4. A ≤_{m} B, B rek. ⟹ A rek.

χ_{A}(x) = χ_{B}(f(x)), für f : A ≤_{m} B

5. A ≤_{m} B, B rek. aufzählbar ⟹ A rek. aufzählbar, f : A ≤_{m} B, g rek. mit

Def(g) = B

g(f(x)) def. ⟺ f(x) ∈ B

Def(f ∘ g) = A, f ∘ g rek.

Definition: A heisst 1-vollständig/m-vollständig:⟺

1. A rek. aufzählbar

2. ∀B (B rek. aufzählbar ⟹ B ≤_{1} A/B ≤_{m} A)

Satz: K ist m-vollständig. Beweis: x ∈ K ⟺ ∃y T xxy Sei B rek. aufzählbar, zeige B ≤_{m} K: B = Def(h), h rek. Definiere

g(x, y) = \{ \begin{matrix}0, & h(x) ↓ \\ ⊥, & sonst \end{matrix}

smn : g (x, y) = φ_{s_{1}^{1}(x)}(y)

x ∈ B : φ_{s_{1}^{1}(x)} = c_{0}^{(1)}
x ∉ B : φ_{s_{1}^{1}(x)} = c_{⊥}^{(}1)

x ∈ B ⟺ φ_{s_{1}^{1}(x)}(\underbrace{s_{1}^{1}(x)}_{y}) ↓⟺ s_{1}^{1}(x) ∈ K

Also: s_{1}^{1} : B ≤_{m} K. Verschärfung: K sogar 1-vollständig. Aufgabe: Mache s injektiv (dann s^{∗}) h(s(x), y) = Code von (P_{s}(x) ergänzt um k Anweisungspaare incr(X_{1})decr(X_{1}) am Anfang)

s^{∗}(0) = s(0)
s^{∗}(s(x)) = h(s(x), y)
für kleinste y: h(s(x), y) ≠ s^{∗}(0), …, s^{∗}(x)

Übertragung des Beweises liefert:

A 1-vollständig ⟺ A m-vollständig.

5 Reduktionsbegriffe und Grade

A ≡_{1} B :⟺ A ≤_{1} B, B ≤_{1} A A ≡_{m} B :⟺ A ≤_{m} B, B ≤_{m} A

1-Grad ist ≡_{1}-Klasse m-Grad ist ≡_{m}-Klasse

Ziel 1: Vergleich von ≡_{1}, ≡_{m}

Ziel 2: Allgemeinere Reduktionsbegriffe

5.1 Satz von Myhill

A ≡_{1} B ⟺ A und B sind rekursiv isomorph, d.h es gibt eine rek. Bijektion f : IN → IN mit x ∈ A ⇔ f(x) ∈ B.

linke Seite liefert: inj. g : IN → IN mit x ∈ A ⟺ g(x) ∈ B inj. h : IN → IN mit y ∈ B ⟺ h(y) ∈ A

“⟸“ trivial: g = f, h = f^{−1}

5.2 Satz von Cantor-Schröder-Bernstein

Für beliebige Mengen A, B gilt: Falls injektive Funktionen g : A → B und h : B → A existieren, dann existiert Bijektion f : A → B.

Beweis verlangt Kombinationen der geg. Funktionen g : A ≤_{1} B, h : B ≤_{1} A zu Bij. f.

Ansatz: Erzeuge sukzessiv endliche A-B-Korrespondenzen: (x_{0}, y_{0}), (x_{1}, y_{1}), …, (x_{k}, y_{k}) mit

• i ≠ j ⟹ x_{i} ≠ x_{j}, y_{i} ≠ y_{j}

• x_{i} ∈ A ⟺ y_{i} ∈ B

so dass schliesslich jedes x ∈ IN ein x_{i} und jedes y ∈ IN ein y_{i}.

Sorge in Schritt 2n dafür, dass 0, …, n alle im Vorbereich, in Schritt 2n+1, dass 0, …, n im Nachbereich der A-B-Korrespondenzen auftreten.

Konstruktion: Setze x_{0} = 0, y_{0} = g(0). Seien (x_{0}, y_{0}), …, (x_{k}, y_{k}) konstruiert

• k + 1 gerade:

Wähle x_{k+1} kleinstes x ≠ x_{0}, …, x_{i}

(a) falls g(x_{k+1}) ≠ y_{0}, …, y_{k}, setze y_{k+1} = g(x_{k+1})

(b) sonst betrachte y_{i} = g(x_{k+1})

(a) falls g(x_{i}) ≠ y_{0}, …, y_{k} setze y_{k+1} = g(x_{i})

(b) sonst betrachte y_{i} = g(x_{i})

(a) falls g(x_{j}) ≠ y_{0}, …, y_{k} setze y_{k+1} = g(x_{j})

(b) etc.

Wegen |y_{0}, …, y_{k}| < |x_{0}, …, x_{k+1}| tritt schliesslich Fall (a) ein.

• k + 1 ungerade:

Analog mit h statt g. Klar: Es entsteht eine Bijektion von IN auf IN.

x_{k} ∈ A ⟺ y_{k} ∈ B: k = 0 wegen g : A ≤_{1} B k + 1, etwa k + 1 gerade und y_{k+1} = g(x_{j})

x_{k+1} ∈ A ⟺ g(x_{k} + 1) = y_{i} ∈ B
⟺ x_{i} ∈ A
⟺ g(x_{i}) = y_{j} ∈ B ⇔ x_{j} ∈ A
⟺ g(x_{j}) = y_{k+1} ∈ B

Beispiel:

x g(x) h(x) k x_{k} y_{k}
0 2  3  0 0 2
1 5  2  1 3 0
2 0  2 1 5
3 6  3 2 1
4 1  4 4 6
⋮  ⋮  ⋮ ⋮ ⋮

5.3 Produktive und kreative Mengen

A ⊆ IN heisst produktiv, falls eine rekursive Funktion f existiert mit:

W_{x} ⊆ A ⟹ f(x) ↓ und f(x) ∈ A\W_{x}

“f ist produktiv für A“

Bemerkung:

A produktiv ⟹ A nicht rekursiv aufzählbar

A heisst kreativ ⟺ A ist rek. aufz., Ā produktiv

Beispiel: K kreativ: rek. aufz., zeige K̄ produktiv: setze f(x) = x, betrachte W_{x} ⊆ K̄.

Beh.: x ∈ K̄\W_{x} Genügt x ∉ W_{x} (Dann x ∈ K̄, x ∉ W_{x}). Wäre x ∈ W_{x}, auch W_{x} ⊆ K̄ wegen Vorraussetzung. Widerspruch zu Definition von K.

Satz:

A produktiv, A ⊆_{m} B ⟹ B produktiv

Vorbereitung für Beweis: Wenn f total, rekursiv, dann f^{−1}(W_{x}) = W_{g(x)} für eine rek. tot. Fkt. g. Dann

f(y) ∈ W_{x} ⟺ y ∈ W_{g(x)} (∗)

Definiere rek. Fkt. h(x, y) = 0, falls φ_{x}(f(y)) ↓, sonst ⊥

smn: φ_{g(x)}(y) = h(x, y) für geeignetes g

Wegen (∗) gilt:

f(y) ∈ W_{x} ⟺ φ_{x}(f(y)) ↓
⟺ h(x, y) = 0
⟺ φ_{g(x)}(y) ↓
⟺ y ∈ W_{g(x)}

Beweis des Satzes: Sei h prod. für A: W_{x} ⊆ A ⟹ h(x) ↓ und h(x) ∈ A − W_{x} Sei f : A ≤_{m} B : x ∈ A ⟺ f(x) ∈ B, g zu f gewählt gemäss Vorbereitung.

Zeige g ∘ h ∘ f produktiv für B: Betrachte W_{x} ⊆ B: Wegen f : A ≤_{m} B gilt

\underbrace{f^{−1}(W_{x})}_{W_{g(x)}} ⊆ A

Da h produktiv für A: h(g(x)) ↓, h(g(x)) ∈ A − W_{g(x)} Dann f(h(g(x))) ↓, zeige f(h(g(x))) ∈ \underbrace{B}_{1} − \underbrace{W_{x}}_{2}

1. klar wegen h(g(x)) ∈ A

2. bekannt: h(g(x)) ∉ W_{g}(x). wegen (∗) folgt f(h(g(x))) ∉ W_{x}

5.4 Verbindungen zum Studium arithmetischer Theorien

Betrachte Sprache 1.Stufe mit +, ·, 0, 1. Identifiziere Sätze ϕ der Sprache mit Zahlen ⌈ϕ⌉.

T h = {⌈ϕ⌉|(IN, +, ·, 0, 1) ⊧ ϕ}

Gödel’s Kodierungstechnik liefert zu jedem e einen Satz ϕ_{e} mit

∃y T eey ⟺ ⌈ϕ_{e}⌉ ∈ T h
(e ∈ K̄ ⇔)¬∃y T eey ⟺ ⌈ϕ_{e}⌉ ∉ T h
⟺ ⌈¬ϕ_{e}⌉ ∈ T h

Somit K̄ ≤_{m} T h. Bekannt: K̄ produktiv, Somit: T h produktiv.

Proposition 1: Die Menge der wahren Sätze der Arithmetik 1.Stufe ist produktiv und somit nicht aufzählbar.

Betrachte P A (Peano-Arithmetik) als Menge der Zahlencodes der aus P A-Axiomen formal herleitbaren Sätze. Analyse der Gödel’schen Kodierung liefert: Falls T eem zutrifft, so T \underline{e}\underline{e}\underline{m} herleitbar. (\underline{e} ist Term \underbrace{1 + ⋯ + 1}_{e}), also auch \underbrace{∃y T \underline{e}\underline{e}y herleitbar}_{Code ∈P A}.

Daher K ≤_{m} P A, K̄ ≤_{m} \overline{P A}.

Proposition 2: Die Menge der in P A nicht herleitbaren Sätze ist produktiv, P A selbst also kreativ.

S = {⌈ϕ_{e}⌉|¬ϕ_{e} in P A beweisbar}

Unterstelle: P A ist widerspruchsfrei. Nach Def. ist S aufzählbar, ausserdem S ⊆ \overline{P A}. (¬ϕ_{e} in P A ⟹ ϕ_{e} nicht in P A beweisbar) Da nach Prop. 2 \overline{P A} produktiv, findet man aus (Index von) S ein e_{0} mit ⌈ϕ_{e_{0}}⌉ ∈ \overline{P A}\S. Proposition 3: ϕ_{e_{0}} nicht beweisbar in P A, ¬ϕ_{e_{0}} nicht beweisbar in P A (Unvollständigkeit von P A). Ziel: Vergleich von ≡_{1}, ≡_{m} Proposition:

1. Jede unendliche rek. aufz. Menge hat eine rek. unendliche Teilmenge

2. Jede produktive Menge hat eine unendl. rek. aufz. Teilmenge

Beweis:

1. Übung.

2. Sei A produktiv mit prod. Fkt. f:

∅ ⊆ A , etwa ∅ = W_{x_{0}} : f(x_{0}) ∈ A(\∅)
{x_{0}} ⊆ A , etwa {x_{0}} = W_{x_{1}} : f(x_{1}) ∈ A(\x_{0})
{x_{0}, x_{1}} ⊆ A , etwa {x_{0}, x_{1}} = W_{x_{2}} : f(x_{2}) ∈ A(\{x_{0}, x_{1}})
…

(⟹ {x_{0}, x_{1}, …} ⊆ A)

A immun :⟺ A unendlich, enthält keine ∞ rek. aufz. Teilmenge
A einfach :⟺ A rek. aufz., \overline{A} immun

Satz: Es gibt eine einfache Menge S. Beweis: Betrachte h(x) = [μt T x[t]_{1}[t]_{2} ∧ [t]_{1} > 2x]_{1} (erstes z, bei Durchsuchen aller Paare (z, y) mit T xzy ∧ z > 2x, wobei [t]_{1} = z, [t]_{2} = y) S := Bild(h) klar nach Definition: h rek., Bild(h) rek. aufz. Beachte: S enthält wenigstens ein Element jeder unendlichen rek. aufz. Menge W_{x}, klar nach Def. von h. (jedes ∞ W_{x} liefert z ∈ W_{x}, z > 2x)

Also: \overline{S} enthält kein ∞ W_{x} ganz.

Somit: \overline{S} enthält keine rek. aufz. Teilmenge.

Fehlt: \overline{S} unendlich. Nach Def. von S:

Für x = 0 wird verlangt z > 0. Für x = 1 wird verlangt z > 2. Für x = 2 wird verlangt z > 4.

Also in {0, 1, 2} ist höchstens ein z. Also in {0, 1, .., 4} sind höchstens zwei z. Also in {0, ..., 2k} sind höchstens k S-Elemente(z).

In \{0, .., 2k\} sind jeweils mindestens k + 1 \overline{S}-Elemente. Also ist \overline{S} unendlich.

Satz (Trennung von ≡_{1}, ≡_{m}-Klassen): Sei A einfach, k ∉ A, B = A ∪ k. Dann gilt:

1. B ist einfach

2. A ≤_{m} B

3. B ≤_{1} A

4. A ≰_{1} B

Beweis:

Index

1-Grad, 28 1-vollständig, 26 3x + 1-Funktion, 15 μ-rekursiv, 15 m-Grad, 28 m-vollständig, 26 s-m-n-Theorem, 21

aufzählbar, 5 Aufzählungsverfahren, 5

berechenbar, 5 Berechnungsverfahren, 5

einfach, 32 entscheidbar, 5 Entscheidungsverfahren, 5

immun, 32

Kleene’sches Normalformtheorem, 16 KNFT, 16 kreative Mengen, 30

produktive Mengen, 30

Rekursionssatz, 22 rekursiv, 6 rekursiv isomorph, 28

Sabotage, 22 Satz von Cantor-Schröder-Bernstein, 28 Satz von Myhill, 28 semantische Programmeigenschaft, 21 Signifikanz, 25

trivial, 22

universell, 20 Unvollständigkeitssatz, 23