Content deleted Content added
bold titles |
mNo edit summary |
||
Line 1:
The '''recursive functions''' are a class of functions which provide a formal model of computability under the conditions set forth by [[computability theory]]. Any operation which can be described by a recursive function is called computable; in this respect, recursive functions are similar to [[Turing machine|Turing machines]], [[Lambda calculus]], and other models of [[computation|computability]]. Recursive functions are related to [[primitive recursive function|primitive recursive functions]], and their inductive definition (below) builds upon that of the primitive recursive functions.
Take as axioms the axioms of the [[primitive recursive function
::If ''f''(''x'',''z''<sub>0</sub>,''z''<sub>1</sub>,...) is a partial function on the [[natural numbers]], then the function μ''x'' ''f''(''x'',''z''<sub>0</sub>,''z''<sub>1</sub>,...), which returns the least ''x'' such that ''f''(0,''z''<sub>0</sub>,''z''<sub>1</sub>,...), ''f''(1,''z''<sub>0</sub>,''z''<sub>1</sub>,...), ''f''(''x'',''z''<sub>0</sub>,''z''<sub>1</sub>,...), ... are all defined and ''f''(''x'',''z''<sub>0</sub>,''z''<sub>1</sub>,...) = 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''<sub>0</sub>,''z''<sub>1</sub>,....)
Line 15:
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 the same -- in other words, the requirement for partial functions can be partially obviated. The set provided by this definition has historically been labelled the set of ''general recursive functions'', though it is one and the same as the set of recursive functions.
| |||