Primitive recursive function: Difference between revisions

Revision as of 12:42, 30 May 2004

Revision as of 08:19, 20 July 2004

Line 59:

Primitive recursive functions tend to correspond very closely with our intuition of what a computable function must be. Certainly the initial set of functions are intuitively computable (in their very simplicity), and the two operations by which one can create new primitive recursive functions are also very straightforward. However the set of primitive recursive functions does not include every possible computable function --- this can be seen with a variant of [[Cantor's diagonal argument|Cantor's diagonalization argument]]. This argument provides a computable function which is not primitive recursive. A sketch of the proof is as follows:

The primitive recursive functions can be computably numbered. This numbering is unique on the definitions of functions, though not unique on the actual functions themselves (as every function can have an infinite number of definitions --- consider simply composing by the [[identity function|identity operator]]). The numbering is computable in the sense that it can be defined under formatformal models of computability such as [[Recursive function|recursive functions]] or [[Turing machine|Turing machines]]; but an appeal to the [[Church-Turing thesis]] is likely sufficient.

Now consider a matrix where the rows are the primitive recursive functions of one argument under this numbering, and the columns are the natural numbers. Then each element (''i'', ''j'') correponds to the ''i''th unary primitive recursive function being calculated on the number ''j''. We can write this as ''f''_''i''(''j'').