[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:

• 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₁(x) = x.
  • p₁(x, y) = x.
  • p₂(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₁ and p₂ because it uses functions of no more than two arguments.