Primitive recursive function: Difference between revisions

Revision as of 13:56, 28 February 2002

Revision as of 16:06, 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 computable (total) functions that can be enumerated in this way. (One might think this implies thatTherfore, any such explicit list of the computable (total) functions cannotcan never be complete,. butNote however that the ''partial''s falsecomputable becausefunctions of(those thewhich [[Computabilityneed theory|uncomputability]]not ofbe thedefined for all arguments) can be explicitly enumerated, for instance by enumerating [[HaltingTuring Problemmachine]] encodings.)

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]].