If g_{1}, g_{2}, g_{3}, and h are previously defined functions,
we can combine them to form new functions. In a very careful, formal development, they can
be combined only in precisely defined ways. Here is an example of the kind of form
required.

*Composition:*f(x,y) = h(g_{1}(x,y), g_{2}(x,y)).

This lets us use functions as arguments to functions.

*Primitive recursion. This is a highly structured "recursive routine" with exactly this form: f(x,0) = g*_{1}(x)

f(x, s(y)) = h(g_{2}(x,y), g_{3}(f(x,y)))*Note: The form of primitive recursion given in the textbook is not consistent with the author's examples. If you want to step through his (or my) examples, use this form instead.*

A *primitive recursive function* is a function formed from the functions z, s, p_{1},
and p_{2} by using only composition and primitive recursion.

Copyright © 1996 by David Matuszek

Last modified Apr 17, 1996