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:

- The
*zero function:*z(x)=z(y) for all x,yI. (This is our "zero"; it is written as a function so we don't have to introduce*constants*into the system.) - The
*successor function:*s(x). Informally, this means "x+1". Formally, it doesn't "return a value", it just sits there: the result of s(x)*is*s(x).

For convenience, we make the following "abbreviations":- 0 is shorthand for z(x).
- 1 is shorthand for s(z(x)).
- 2 is shorthand for s(s(z(x))).
- 3 is shorthand for s(s(s(z(x))).
- ...and so on.

- The
*projector functions:*- p
_{1}(x) = x. - p
_{1}(x, y) = x. - p
_{2}(x, y) = y.

The projector (or "pick") functions are just a way of extracting one of the parameters and discarding the rest. The book defines only p

_{1}and p_{2}because it uses functions of no more than two arguments. - p

Copyright © 1996 by David Matuszek

Last modified Apr 17, 1996