[Overview] [Previous] [Next]

Composition and Recursion

If g1, g2, g3, 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.

A primitive recursive function is a function formed from the functions z, s, p1, and p2 by using only composition and primitive recursion.

Copyright 1996 by David Matuszek
Last modified Apr 17, 1996