zurück zur Liste

Primitv rekursive Funktion

Jede berechenbare Funktion kann durch eine primitiv rekursive Funtkion mit Hilfe von einfachen Grundfunktionen dargestellt werden.

Basisfunktionen clr () = 0
suc (n) = n+1
p (1, x1, x2, ... , xn) = x1
p (i, x1, x2, ... , xn) = p (i-1, x2, x3, ... , xn)

Zu einer k-stelligen Funktion ψ und einer (k+2)-stelligen Funktion χ ist eine (k+1)-stellige Funktion φ definiert.
φ phi, ψ psi, χ chi ∈ PRF

φ (0, x1, x2, ... , xn) = ψ (x1, x2, ... , xn)
φ (y+1, x1, x2, ... , xn) = χ (φ (y, x1, x2, ... , xn), y, x1, x2, ... , xn)

Verdeutlichung am Beispiel: Addieren und multiplizieren von zwei Zahlen
Aufstellen der Gleichungen → Einfache Lösungen → Gleichungen mit ψ und χ
add (0, m)
add (n+1, m)
= m
= suc (add (n, m))
= p1 (m)
= suc (p1) (add (n, m), n, m))
mul (0, m)
mul (n+1, m)
= 0
= m + mul (n, m)
= clr (m)
= add (p1, p3) (mult (n, m), n, m)