Aus ProgrammingWiki

Wiederholte Vorgängerfunktion Seite 16

$n = q$

$n1 = m$

$r = 1$

$S^2(0, m) = m = f(m) = U^1_1(m)$

$S^2(S(q), m) = g(q, S^2(q, m), m)$

$= S(U^3_2(q, S^2(q, m), m))$

AP ohne Computer Seite 32

Beispiel für Primitiv rekursive Funktionen Seite 41

Fakultät

$fak(0) = C^0_1() = 1$

$fak(n) = g(n, fak(n))$

$3! = 3 * 2 * 1$

$4! = 4 * 3!$

$mult(S(n), fak(n))$

Monus-Operation

$mo(0, y) = C^1_0(y) = 0$

$mo(S(x), y) = g(x, mo(x, y), y)$

$= P(U^3_2(x, mo(x, y), y))$

Polynome

Ein Polynom mit natürlichen Koeffizienten enthält Operationen, welche wir bereits in der Vorlesung als primitiv rekursive Funktion dargestellt haben: Addition, Multiplakation, Potenzierung (bei Polynomen nur natürliche Exponenten) und die jeweils die Substitution und die primitive Rekursion, mit denen man diese Operationen verknüpfen kann.