Primitive und partielle Rekursion

Gliederung

6 (Un-)Entscheidbarkeit, Halteproblem
und Reduzierbarkeit
1 Einführung
7 Das Postsche Korrespondenzproblem
2 Berechenbarkeitsbegriff
8 Komplexität – Einführung
3 LOOP-, WHILE-, und
GOTO-Berechenbarkeit
9 NP-Vollständigkeit

4 Primitive und partielle Rekursion

10 PSPACE

5 Die Ackermannfunktion

Rolf Niedermeier (TU Berlin) Berechenbarkeit und Komplexität WiSe’19/20 57 / 162

 Primitive und partielle Rekursion

Primitive und partielle Rekursion

13
Quelle: [Link]/wiki/File:Barnsley_fern_mutated_-Leptosporangiate_fern.PNG
Rolf Niedermeier (TU Berlin) Berechenbarkeit und Komplexität WiSe’19/20 58 / 162
 Primitive und partielle Rekursion

Primitiv-rekursive Funktionen I
Definition
Die Klasse der primitiv-rekursiven Funktionen ist die kleinste Klasse
von Funktionen von N� → N, � ≥ 014 , die
a) folgende Grundfunktionen enthält:
i) die konstanten Funktionen f : Nk → N, f (n1 , . . . , nk ) = c;

14
Für � = 0 ist eine 0-stellige Funktion eine konstante Zahl.
Rolf Niedermeier (TU Berlin) Berechenbarkeit und Komplexität WiSe’19/20 59 / 162
 Primitive und partielle Rekursion

Primitiv-rekursive Funktionen I
Definition
Die Klasse der primitiv-rekursiven Funktionen ist die kleinste Klasse
von Funktionen von N� → N, � ≥ 014 , die
a) folgende Grundfunktionen enthält:
i) die konstanten Funktionen f : Nk → N, f (n1 , . . . , nk ) = c;
ii) die Projektionen πik : Nk → N, πik (n1 , . . . , nk ) = ni ;

14
Für � = 0 ist eine 0-stellige Funktion eine konstante Zahl.
Rolf Niedermeier (TU Berlin) Berechenbarkeit und Komplexität WiSe’19/20 59 / 162
 Primitive und partielle Rekursion

Primitiv-rekursive Funktionen I
Definition
Die Klasse der primitiv-rekursiven Funktionen ist die kleinste Klasse
von Funktionen von N� → N, � ≥ 014 , die
a) folgende Grundfunktionen enthält:
i) die konstanten Funktionen f : Nk → N, f (n1 , . . . , nk ) = c;
ii) die Projektionen πik : Nk → N, πik (n1 , . . . , nk ) = ni ;
iii) die Nachfolgerfunktion succ : N → N, succ(n) = n + 1;

14
Für � = 0 ist eine 0-stellige Funktion eine konstante Zahl.
Rolf Niedermeier (TU Berlin) Berechenbarkeit und Komplexität WiSe’19/20 59 / 162
 Primitive und partielle Rekursion

Primitiv-rekursive Funktionen I
Definition
Die Klasse der primitiv-rekursiven Funktionen ist die kleinste Klasse
von Funktionen von N� → N, � ≥ 014 , die
a) folgende Grundfunktionen enthält:
i) die konstanten Funktionen f : Nk → N, f (n1 , . . . , nk ) = c;
ii) die Projektionen πik : Nk → N, πik (n1 , . . . , nk ) = ni ;
iii) die Nachfolgerfunktion succ : N → N, succ(n) = n + 1;
b) und abgeschlossen ist unter folgenden Operationen:
i) der Komposition: falls f1 , . . . , fm : Nk → N, g : Nm → N
primitiv-rekursiv, dann auch g ◦ (f1 , . . . , fm ) : Nk → N,
(n1 , . . . , nk ) �→ g (f1 (n1 , . . . , nk ), . . . , fm (n1 , . . . , nk ));

14
Für � = 0 ist eine 0-stellige Funktion eine konstante Zahl.
Rolf Niedermeier (TU Berlin) Berechenbarkeit und Komplexität WiSe’19/20 59 / 162
 Primitive und partielle Rekursion

Primitiv-rekursive Funktionen I
Definition
Die Klasse der primitiv-rekursiven Funktionen ist die kleinste Klasse
von Funktionen von N� → N, � ≥ 014 , die
a) folgende Grundfunktionen enthält:
i) die konstanten Funktionen f : Nk → N, f (n1 , . . . , nk ) = c;
ii) die Projektionen πik : Nk → N, πik (n1 , . . . , nk ) = ni ;
iii) die Nachfolgerfunktion succ : N → N, succ(n) = n + 1;
b) und abgeschlossen ist unter folgenden Operationen:
i) der Komposition: falls f1 , . . . , fm : Nk → N, g : Nm → N
primitiv-rekursiv, dann auch g ◦ (f1 , . . . , fm ) : Nk → N,
(n1 , . . . , nk ) �→ g (f1 (n1 , . . . , nk ), . . . , fm (n1 , . . . , nk ));
ii) der primitiven Rekursion: falls g : Nk → N, h : Nk+2 → N
primitiv-rekursiv, dann auch f : Nk+1 → N mit
f (0, n1 , . . . , nk ) = g (n1 , . . . , nk ) und
f (n + 1, n1 , . . . , nk ) = h(n, f (n, n1 , . . . , nk ), n1 , . . . , nk ).

14
Für � = 0 ist eine 0-stellige Funktion eine konstante Zahl.
Rolf Niedermeier (TU Berlin) Berechenbarkeit und Komplexität WiSe’19/20 59 / 162
 Primitive und partielle Rekursion

Primitiv-rekursive Funktionen II

Bsp. 1: Die Summenfunktion add : N2 → N ist primitiv-rekursiv:

Rolf Niedermeier (TU Berlin) Berechenbarkeit und Komplexität WiSe’19/20 60 / 162

 Primitive und partielle Rekursion

Primitiv-rekursive Funktionen II

Bsp. 1: Die Summenfunktion add : N2 → N ist primitiv-rekursiv:

Bsp. 2: Die Produktfunktion mult : N2 → N ist dann auch

primitiv-rekursiv :

Rolf Niedermeier (TU Berlin) Berechenbarkeit und Komplexität WiSe’19/20 60 / 162

 Primitive und partielle Rekursion

Primitiv-rekursive Funktionen II

Bsp. 1: Die Summenfunktion add : N2 → N ist primitiv-rekursiv:

Bsp. 2: Die Produktfunktion mult : N2 → N ist dann auch

primitiv-rekursiv :

Alle primitiv-rekursiven Funktionen sind total.

Rolf Niedermeier (TU Berlin) Berechenbarkeit und Komplexität WiSe’19/20 60 / 162

 Primitive und partielle Rekursion

Primitiv-rekursive Funktionen III

Theorem
Die primitiv-rekursiven Funktionen sind genau die LOOP-berechenbaren.

Rolf Niedermeier (TU Berlin) Berechenbarkeit und Komplexität WiSe’19/20 61 / 162

 Primitive und partielle Rekursion

Primitiv-rekursive Funktionen III

Theorem
Die primitiv-rekursiven Funktionen sind genau die LOOP-berechenbaren.

Beweisidee:
Entsprechungen (zur wechselseitigen Simulation):
∧
• xi := c =

Rolf Niedermeier (TU Berlin) Berechenbarkeit und Komplexität WiSe’19/20 61 / 162

 Primitive und partielle Rekursion

Primitiv-rekursive Funktionen III

Theorem
Die primitiv-rekursiven Funktionen sind genau die LOOP-berechenbaren.

Beweisidee:
Entsprechungen (zur wechselseitigen Simulation):
∧
• xi := c =
∧
• xi := xj =

Rolf Niedermeier (TU Berlin) Berechenbarkeit und Komplexität WiSe’19/20 61 / 162

 Primitive und partielle Rekursion

Primitiv-rekursive Funktionen III

Theorem
Die primitiv-rekursiven Funktionen sind genau die LOOP-berechenbaren.

Beweisidee:
Entsprechungen (zur wechselseitigen Simulation):
∧
• xi := c =
∧
• xi := xj =
∧
• P; Q =

Rolf Niedermeier (TU Berlin) Berechenbarkeit und Komplexität WiSe’19/20 61 / 162

 Primitive und partielle Rekursion

Primitiv-rekursive Funktionen III

Theorem
Die primitiv-rekursiven Funktionen sind genau die LOOP-berechenbaren.

Beweisidee:
Entsprechungen (zur wechselseitigen Simulation):
∧
• xi := c =
∧
• xi := xj =
∧
• P; Q =
∧
• LOOP ... =
�

Rolf Niedermeier (TU Berlin) Berechenbarkeit und Komplexität WiSe’19/20 61 / 162

 Primitive und partielle Rekursion

µ-rekursive (bzw. partiell rekursive) Funktionen I

Definition
Die Klasse der µ-rekursiven Funktionen ist die kleinste Klasse von
Funktionen von N� → N, � ≥ 0,15 die
a) die Grundfunktionen enthält und

15
Für � = 0 ist eine 0-stellige Funktion eine konstante Zahl.
Rolf Niedermeier (TU Berlin) Berechenbarkeit und Komplexität WiSe’19/20 62 / 162
 Primitive und partielle Rekursion

µ-rekursive (bzw. partiell rekursive) Funktionen I

Definition
Die Klasse der µ-rekursiven Funktionen ist die kleinste Klasse von
Funktionen von N� → N, � ≥ 0,15 die
a) die Grundfunktionen enthält und
b) abgeschlossen ist unter folgenden Operationen:
i) der Komposition,
ii) der primitiven Rekursion und

15
Für � = 0 ist eine 0-stellige Funktion eine konstante Zahl.
Rolf Niedermeier (TU Berlin) Berechenbarkeit und Komplexität WiSe’19/20 62 / 162
 Primitive und partielle Rekursion

µ-rekursive (bzw. partiell rekursive) Funktionen I

Definition
Die Klasse der µ-rekursiven Funktionen ist die kleinste Klasse von
Funktionen von N� → N, � ≥ 0,15 die
a) die Grundfunktionen enthält und
b) abgeschlossen ist unter folgenden Operationen:
i) der Komposition,
ii) der primitiven Rekursion und
iii) dem µ-Operator: falls f : Nk+1 → N µ-rekursiv,
dann auch g : Nk → N mit

g (x1 , . . . , xk ) := µ(f )(x1 , . . . , xk )



n, falls f (n, x1 , . . . , xk ) = 0 und
= f (n� , x1 , . . . , xk ) �= 0 und def. für n� < n


⊥, sonst.

15
Für � = 0 ist eine 0-stellige Funktion eine konstante Zahl.
Rolf Niedermeier (TU Berlin) Berechenbarkeit und Komplexität WiSe’19/20 62 / 162
 Primitive und partielle Rekursion

µ-rekursive Funktionen II
Mitteilung: Die µ-rekursiven Funktionen sind genau die
Turing/WHILE/GOTO-berechenbaren.
Beweisidee: µ-Operator entspricht WHILE-Schleife. .. �

Rolf Niedermeier (TU Berlin) Berechenbarkeit und Komplexität WiSe’19/20 63 / 162

 Primitive und partielle Rekursion

µ-rekursive Funktionen II
Mitteilung: Die µ-rekursiven Funktionen sind genau die
Turing/WHILE/GOTO-berechenbaren.
Beweisidee: µ-Operator entspricht WHILE-Schleife. .. �

Mitteilung (Kleene’sche Normalform): Zu jeder µ-rekursiven Funktion

f : Nk → N existieren zwei primitiv-rekursive Funktionen
p, q : Nk+1 → N derart, dass für alle (x1 , . . . , xk ) ∈ Nk gilt

f (x1 , . . . , xk ) = p(x1 , . . . , xk , µ(q)(x1 , . . . , xk )).

Rolf Niedermeier (TU Berlin) Berechenbarkeit und Komplexität WiSe’19/20 63 / 162

 Primitive und partielle Rekursion

µ-rekursive Funktionen II
Mitteilung: Die µ-rekursiven Funktionen sind genau die
Turing/WHILE/GOTO-berechenbaren.
Beweisidee: µ-Operator entspricht WHILE-Schleife. .. �

Mitteilung (Kleene’sche Normalform): Zu jeder µ-rekursiven Funktion

f : Nk → N existieren zwei primitiv-rekursive Funktionen
p, q : Nk+1 → N derart, dass für alle (x1 , . . . , xk ) ∈ Nk gilt

f (x1 , . . . , xk ) = p(x1 , . . . , xk , µ(q)(x1 , . . . , xk )).

In anderen Worten: Es reicht immer ein µ-Operator.

Rolf Niedermeier (TU Berlin) Berechenbarkeit und Komplexität WiSe’19/20 63 / 162