[Overview] [Previous] [Next]

Composition and Recursion, Revisited

Just as you can have lots of minor variations on a Turing machine that all turn out to be equivalent, so too you can have lots of minor variations on the definition of primitive recursive functions. Here I'm going to try to highlight the important aspects of the definitions.


The important thing here is that each function be defined only in terms of previously defined functions. This restriction prevents unwanted kinds of recursion from creeping in, such as indirect recursion (A calls B, B calls C, C calls A).

Many programming languages have a restriction that you cannot reference a variable until after it is defined. This is the same kind of restriction.

Primitive recursion

Primitive recursive functions may only use a simple form of recursion. In particular,

General recursive functions, which don't have these restrictions, are more powerful than primitive recursive functions.

Copyright 1996 by David Matuszek
Last modified Apr 18, 1996