Recursive function

partial recursive function

One of the mathematical precizations of the intuitive concept of a computable function, defined as follows. One examines functions given on the natural numbers and with natural values. The functions are assumed to be partial, i.e. they are not defined, generally speaking, for all values of the arguments. The following functions are called basic: $ S( x) = x+ 1 $, $ o( x) = 0 $, $ I _ {m} ^ {n} ( x _ {1} \dots x _ {n} ) = x _ {m} $ $ ( 1 \leq m \leq n) $. One says that an $ n $- place function $ \psi $ is obtained from an $ m $- place function $ \phi $ and $ n $- place functions $ f _ {1} \dots f _ {m} $ with the aid of composition if for all $ x _ {1} \dots x _ {n} $ the following equality holds:

$$ \psi ( x _ {1} \dots x _ {n} ) = $$

$$ = \ \phi ( f _ {1} ( x _ {1} \dots x _ {n} ) \dots f _ {m} ( x _ {1} \dots x _ {n} )). $$

One says that an $ ( n+ 1) $- place function $ f $ is obtained from an $ n $- place function $ \phi $ and the $ ( n+ 2) $- place function $ \psi $ by means of primitive recursion if for any values of $ x _ {1} \dots x _ {n} , y $, the following equalities hold:

$$ f( x _ {1} \dots x _ {n} , 0) = \phi ( x _ {1} \dots x _ {n} ), $$

$$ f( x _ {1} \dots x _ {n} , y+ 1) = $$

$$ = \ \psi ( x _ {1} \dots x _ {n} , y, f( x _ {1} \dots x _ {n} , y)). $$

One says that an $ n $- place function $ f $ is obtained from the $ ( n+ 1) $- place function $ \phi $ with the aid of a minimization operator, or least-number operator, if for any $ x _ {1} \dots x _ {n} , y $ the condition $ f( x _ {1} \dots x _ {n} ) = y $ holds if and only if the values $ \phi ( x _ {1} \dots x _ {n} , 0) \dots \phi ( x _ {1} \dots x _ {n} , y- 1) $ are defined and are not equal to 0, while $ \phi ( x _ {1} \dots x _ {n} , y) = 0 $. A partial function $ f $ is called recursive if it can be obtained from the basic functions by means of a finite number of applications of composition, primitive recursion and minimization operators.

In other words, $ f $ is a recursive function if there is a finite sequence of partial functions $ g _ {1} \dots g _ {k} $ such that $ g _ {k} = f $, and each function in this sequence is either basic or is obtained from the previous functions by means of composition, primitive recursion or minimization. With the method of arithmetization it is possible to obtain an enumeration of all such descriptions of a recursive function, and in fact an algorithm can be given which computes a one-to-one surjective encoding between descriptions of recursive functions and the natural numbers. The recursive function being defined by this description is usually denoted by $ \phi _ {x} $, and $ x $ is called its Gödel number.

An everywhere-defined recursive function is called general recursive. There are recursive functions that cannot be extended to general recursive functions.

For any recursive function one can give an algorithm for calculating its values, i.e. all recursive functions are in essence computable. A widespread hypothesis, known as Church's thesis, consists in the fact that every computable function is recursive. This thesis is confirmed by a number of facts. Thus, all concrete functions studied in mathematics and recognizable as computable in the intuitive sense of the word, proved to be recursive. The concept of a recursive function turns out to coincide in extent with other mathematical precizations of the concept of a computable function (e.g. with the concept of a function computable on a Turing machine, computable using a Markov normal algorithm, etc.).

There are several definitions of the class of all recursive functions by way of initial functions and generating operators. In particular, every recursive function can be obtained from the functions

$$ a( x, y) = x + y,\ \ m( x, y) = x \cdot y ,\ \ I _ {m} ^ {n} , $$

and

$$ k( x, y) = \left \{

using a finite number of composition and minimization operators.

References

[1]	A.I. Mal'tsev, "Algorithms and recursive functions" , Wolters-Noordhoff (1970) (Translated from Russian)
[2]	H. Rogers jr., "Theory of recursive functions and effective computability" , McGraw-Hill (1967) pp. 164–165