[Overview] [Previous] [Next]

Primitive Recursive Functions

The purpose of this section is to give you some idea of the flavor of recursive function theory.

The textbook describes these functions as being over the natural numbers I={0,1,2,3,...}. A better way to look at recursive functions, though, is as pure symbol systems. Numbers are not used in the system; rather, we use the system to construct both numbers and arithmetical functions on numbers. In other words, it's a different numbering system, in the same way that Roman numerals are different. The correspondence goes like this:

z(x)=0, s(z(x))=1, s(s(z(x)))=2, s(s(s(z(x))))=3, ...

To "translate" to decimal, just count the number of s's surrounding the central z(x).

Now let's get formal. In this system there are only a few basic functions:

Copyright 1996 by David Matuszek
Last modified Apr 17, 1996