Primitive recursive function: Difference between revisions

Revision as of 15:51, 25 February 2002

Revision as of 13:42, 28 February 2002

Line 64:

Now consider the function ''g''(''x'')=S(''f''_''x''(''x'')). ''g'' lies on the diagonal of this matrix and simply adds one to the value it finds. This function is computable (by the above), but clearly no primitive recursive function exists which computes it as it differs from each possible primitive recursive function by at least one value. Thus there must be computable functions which are not primitive recursive.

Note that this argument can be applied to any class of functions that can be enumerated in this way. In(One othermight words,think this implies that any explicit list of the computable functions cannot be complete, but that's false because of the [[undecidability]] of the [[Halting Problem]].)

One can also explicitly exhibit a simple 1-ary computable function which is recursively defined for any natural number, but which is not primitive recursive, see [[Ackermann function]].