Primitive recursive function: Difference between revisions

Revision as of 08:30, 23 June 2024

Revision as of 08:40, 23 June 2024

Line 250:

Primitive recursive functions tend to correspond very closely with our intuition of what a computable function must be. Certainly the initial 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 total computable function—this can be seen with a variant of [[Cantor's diagonal argument]]. This argument provides a total computable function that is not primitive recursive. A sketch of the proof is as follows:

{{block indent|The primitive recursive functions of one argument (i.e., unary functions) can be [[Recursively enumerable set|computably enumerated]]. This enumeration uses the definitions of the primitive recursive functions (which are essentially just expressions with the composition and primitive recursion operations as operators and the basic primitive recursive functions as atoms), and can be assumed to contain every definition once, even though a same ''function'' will occur many times on the list (since many definitions define the same function; indeed simply composing by the [[identity function]] generates infinitely many definitions of any one primitive recursive function). This means that the {{mvar|''<math>n''}}</math>-th definition of a primitive recursive function in this enumeration can be effectively determined from {{mvar|''<math>n''}}</math>. Indeed if one uses some [[Gödel numbering]] to encode definitions as numbers, then this {{mvar|''<math>n''}}</math>-th definition in the list is computed by a primitive recursive function of {{mvar|''<math>n''}}</math>. Let {{math|''f''<submath>''n''f_n</submath>}} denote the unary primitive recursive function given by this definition.

Now define the "evaluator function" {{mvar|''<math>ev''}}</math> with two arguments, by {{<math|''>ev''(''i'',''j'') {{=}} ''f''_''i''f_i(''j'')}}</math>. Clearly {{<math|''>ev''}}</math> is total and computable, since one can effectively determine the definition of {{math|''f''<submath>''i''f_i</submath>}}, and being a primitive recursive function {{math|''f''<submath>''i''f_i</submath>}} is itself total and computable, so {{<math|''f''_''i''f_i(''j'')}}</math> is always defined and effectively computable. However a diagonal argument will show that the function {{mvar|''<math>ev''}}</math> of two arguments is not primitive recursive.

Suppose {{mvar|''<math>ev''}}</math> were primitive recursive, then the unary function {{mvar|''<math>g''}}</math> defined by {{<math|''>g''(''i'') {{=}} S(''ev''(''i'',''i''))}}</math> would also be primitive recursive, as it is defined by composition from the successor function and {{mvar|''<math>ev''}}</math>. But then {{mvar|''<math>g''}}</math> occurs in the enumeration, so there is some number {{mvar|''<math>n''}}</math> such that {{<math|''>g'' {{=}} ''f''<sub>''n''f_n</submath>}}. But now {{<math|''>g''(''n'') {{=}} S(''ev''(''n'',''n'')) {{=}} S(''f''_''n''f_n(''n'')) {{=}} S(''g''(''n''))}}</math> gives a contradiction.}}

This argument can be applied to any class of computable (total) functions that can be enumerated in this way, as explained in the article [[Machine that always halts]]. Note however that the ''partial'' computable functions (those that need not be defined for all arguments) can be explicitly enumerated, for instance by enumerating Turing machine encodings.