VL-11: Primitive Rekursion

Question 1

Was ist die primitv rekursive Bijektion?

Answer 1

• Bijektive binomial Funktion β(x,y), welche eine eindeutige Zuordnung N² → N macht
• Primitv rekursive, da binom2 durch Addition dargestellt dar gestellt werden kann

Question 2

Wie funktionieren die Umkehrfunktionen der Bijektion?

Answer 2

• γ(n) = h (n,n,n)
• Sucht das größte x, für das ein y existiert mit β(x,y) = n
• δ(n) sucht analog das größte y
• primitiv rekursiv

Question 3

Wie lassen sich die bijektive (Umkehr-)funktion

Question 4

Wie funktioniert der Beweis: LOOP → Primitiv Rekursiv?

Answer 4

LOOP → Primitiv rekursiv:
- Ein LOOP Programm P beschreibt eine Funktion FP mit Eingabevariablen (a0, a1, …, ak) und den Ausgabevariablen (b0, b2, …, bk)
- Es wird induktiv über den Aufbau von P gezeigt, dass es eine primitv rekursive Funktion N→N gibt, welche g(<a0, …, ak>) = <b0, …, bk> berechnet

• Für Zuweisung: xi := xj + c
  gp(x) = <u0(x), … ui-1(x), uj(x)+c, ui+1(x), …, uk(x)>4
• Für Hintereinanderausführung: P = Q;R
  gp(x) = gr(gq(x))
• Für LOOP: LOOP xi DO Q ENDLOOP
  Hilfsfunktion h: N² → N:
• h(0,x) = x
• h(n+1, x) = gQ(h(n,x))
• gP = h( ui(x), x)
• Durchlaufe h genau ui mal und berechne gq

Start:
x = <0, x’1, …, x’m, 0, … 0>
- Setze x auf den Wert der m Eingabe Parameter. Setze die restlichen k-m Variablen auf 0

Ergebnis:
u0(gP(x))
- Ergebnis in variable x0

Question 5

Wie funktioniert der Beweis: Primitiv Rekursiv → LOOP?

Answer 5

Basisfunktionen

Wir zeigen, dass es ein Programm P gibt, welches das Verhalten der Funktion der Funktion f(x1, …, xk) simuliert und auf x0 Ausgibt:

• Konstante Funktionen: f(x1, …, xk) = c
  x0 := c
• Projektion: f(x1, …, xk) = xj
  x0 := xj
• Nachfolgerfunktion: succ(xj) = xj +1
  xj := xj+1

Komposition: f = f1, …, fs
Hintereinanderausführung der Programme zu f1, …, fs.
- Ergebnisse ggf. Zwischenspeichern in zusätzlichen variablen

Primitive Rekursion:
f (0, x1, …, xk) = g(x1, …, xk)
f (n+1, x1, …, xk) = h (n, f(n, x1, …, xk), x1, …, xk)
Pf:
x0 := g(x1, . . . , xk );
s := 0;
LOOP n DO
x0 := h(s, x0, x1, . . . , xk );
s := s + 1;
ENDLOOP;

Question 6

Was ist der Kleensche µ-Operator?

Answer 6

Sei g: N^k+1 → N ∪ {⊥} eine Funktion mit k+1 Argumenten. Dann entsteht dur das verwenden des µ Operators eine Funktion f: N^K → N ∪ {⊥}, wobei:
f(x1, …, xk) = min{ n| g(n, x1, …, xk) = 0 und für alle m<n gilt g(n, x1, …, xk) != ⊥ }

f = µg: N^k → N

Beispiel: g(x,a,b,c) = (x-a)²(x-b)²(x-c)²
- µg = kleinstes x für das g(x,a,b,c) = 0
- In dem Fall f = min{a,b,c}

Question 7

Was ist die Klasse der µ-rekursiven Funktionen?

Answer 7

Die Klasse der μ-rekursiven Funktionen ist die kleinste Klasse von
(partiellen und totalen) Funktionen, die die Basisfunktionen
- konstante Funktionen
- Projektionen
- Nachfolgerfunktion
enthält und die abgeschlossen ist unter
- Komposition
- primitiver Rekursion
-Anwendung des μ-Operators.

Question 8

Zu welchem Rechnermodell sind die µ-rekursiven Funktionen äquivalent?

Answer 8

• WHILE Programm und somit TM, RAM etc.