General recursive function: Difference between revisions

Revision as of 11:03, 13 December 2002

Revision as of 23:26, 15 December 2002

Line 1:

The '''recursive functions''' are a class of functions[[function]]s whichfrom provide[[natural anumber]]s formalto model[[natural ofnumber]]s computabilitywhich underare the"computable" conditionsin setsome forthintuitive bysense. In fact, in [[computability theory]]. Anyit operationis whichshown canthat be described by athe recursive functionfunctions isare calledprecisely computable;the infunctions thisthat respect,can recursivebe functionscomputed are similar toby [[Turing machine|Turing machines]], [[Lambda calculus]], and other models of [[computation|computability]]s. Recursive functions are related to [[primitive recursive function|primitive recursive functions]], and their inductive definition (below) builds upon that of the primitive recursive functions.

== Definition ==

Take as axioms the axioms of the [[primitive recursive function]]s, but extend the definitions so as to allow for [[partial function]]s. Add one further operator, the ''least search'' or ''unbounded search'' operator, defined byas the following axiomfollows:

::If ''f''(''x'',''z''₀₁,''z''₁,...,''z''_''n'') is a partial function on the [[natural numbers]], thenwith the function μ''xn''+1 arguments ''fx''(, ''xz''₁,...,''z''_0''n'', then the function μ''x'' ''f'' is the partial function with arguments ''z''₁,...),''z''_''n'' whichthat returns the least ''x'' such that ''f''(0,''z''₀₁,''z''₁,...,''z''_''n''), ''f''(1,''z''₀₁,''z''₁,...,''z''_''n''), ..., ''f''(''x'',''z''₀₁,''z''₁,...), ...''z''_''n'') are all defined and ''f''(''x'',''z''₀₁,''z''₁,...,''z''_''n'') = 0, if such an ''x'' exists,; isif ano such ''recursive functionx''. (Ifexists, such anthen μ''x'' does not exist, the operation''f'' is undefinednot ondefined for the inputparticular arguments ''z''₀₁,...,''z''_1''n'',....)

The set of ''partial recursive functions'' is defined as the smallest set of partial functions of any [[arity]] from natural numbers to natural numbers which contains the zero, successor, and projection functions, and which is closed under composition, primitive recursion, and unbounded search.

::If ''f''(''x'',''z''₀,''z''₁,...) is a partial function on the [[natural numbers]], then the function μ''x'' ''f''(''x'',''z''₀,''z''₁,...), which returns the least ''x'' such that ''f''(0,''z''₀,''z''₁,...), ''f''(1,''z''₀,''z''₁,...), ''f''(''x'',''z''₀,''z''₁,...), ... are all defined and ''f''(''x'',''z''₀,''z''₁,...) = 0, if such an ''x'' exists, is a ''recursive function''. (If such an ''x'' does not exist, the operation is undefined on the input ''z''₀,''z''₁,....)

The set of ''recursive functions'' is the subset of partial recursive functions which are [[total function|total]].

In the [[equivalence of models of computability]] the parallel is drawn between [[Turing machine|Turing machines]] which do not terminate for certain inputs and an undefined result for that input in the corresponding recursive function.

The unbounded search operator is not definable by the rules of primitive recursion as they do not provide a mechanism for these "infinite loops" (undefined values).

In the [[equivalence of models of computability]] the parallel is drawn between [[Turing machine|Turing machines]] which do not terminate for certain inputs and an undefined result for that input in the corresponding partial recursive function.

The set of ''partial recursive functions'' is the smallest set of partial functions of any [[arity]] from natural numbers to natural numbers which contains the zero, successor, and projection functions, and which is closed under composition, primitive recursion, and unbounded search.

The unbounded search operator is not definable by the rules of primitive recursion as theythose do not provide a mechanism for these "infinite loops" (undefined values).

The set of ''recursive functions'' is the subset of partial recursive functions which are [[total function|total]].

It is interesting to note that if the application of the unbounded search operator in the definition above is limited strictly to ''regular functions'' (functions which are guaranteed to be total when the unbounded search operator is applied to them), the resulting set is(historically the same -- in other words,called the requirement''general for partialrecursive functions'') canis bethe partiallysame obviated. The set provided by this definition has historically been labelledas the set of ''general recursive functions'', though-- itin isother one andwords, the samerequirement asfor thepartial setfunctions ofcan recursivebe functionspartially obviated.