Vorlesung 11 Grüning

Aus ProgrammingWiki
< BuK < IIm20

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

Ap.png

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.