VL-10: LOOP und WHILE Programme II

Question 1

Was ist ein Beispiel für eine Funktion, welche nicht LOOP berechenbar ist?

Answer 1

Ackermann Funktion:
Gemäß Wachstumslemma gibt es für jedes Programm P ein m, so das gilt A(m,n) > F(P)

Question 2

Was ist ein primitiv rekursive Funktion?

Answer 2

• Unterfamilie der Funktionen N^k -> N mit k>=1
• Induktive Definition über zwei Operationen aus den Basisfunktionen
• Totale und berechenbare Funktionen

Question 3

Was sind die Basisfunktionen der primitv rekursiven Funktionen?

Answer 3

• Konstante Funktionen: f(x) = 1
• Abbildungen auf eine der Komponenten: f(x,y) = y
• Nachfolgerfunktion: succ(x) = x+1

Question 4

Wie ist die Kompositions-Operation definiert?

Answer 4

• Jede Komposition von primitiv rekursiven Funktionen ist primitiv rekursiv:
  Wenn f: N² -> N und g1, g2 N->N alle primitv rekursiv sind, dann ist h = f(g1(x), g2(y)) auch primitiv rekursiv
• Beispiel: f(x,y) = y+1, da = succ(π2,2(x,y))

Question 5

Wie ist die primitive Rekursions-Operation definiert?

Answer 5

• Seien g: N^k+1 → N und h: N^k-q → N primitiv rekursive Funktionen.
• Dann ist f: N^k → N eine primitv rekursive Funktion, wenn sie wiefolgt definiert ist:
  f(0, x1, … , xk) = g(x1, …, xk)
  f(n+1, x1, …, xk) = h(n, f(n, x1, …, xk), x1, …, xk)
• f wird rekursiv über h mit x1-=1 aufgerufen bis x1 = 0, dann g(x2, …)

Beispiel Addition:
g(y) = y,
h(x,y,z) = succ(x)
f(x,y) = h(f(x-1, y), y, z)