Namespaces
Variants
Actions

Difference between revisions of "Recursive function"

From Encyclopedia of Mathematics
Jump to: navigation, search
(Importing text file)
 
m (fixing =)
 
(4 intermediate revisions by 2 users not shown)
Line 1: Line 1:
''partial recursive function''
+
<!--
 +
r0802601.png
 +
$#A+1 = 39 n = 0
 +
$#C+1 = 39 : ~/encyclopedia/old_files/data/R080/R.0800260 Recursive function,
 +
Automatically converted into TeX, above some diagnostics.
 +
Please remove this comment and the {{TEX|auto}} line below,
 +
if TeX found to be correct.
 +
-->
  
One of the mathematical precizations of the intuitive concept of a [[Computable function|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: <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r080/r080260/r0802601.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r080/r080260/r0802602.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r080/r080260/r0802603.png" /> <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r080/r080260/r0802604.png" />. One says that an <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r080/r080260/r0802605.png" />-place function <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r080/r080260/r0802606.png" /> is obtained from an <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r080/r080260/r0802607.png" />-place function <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r080/r080260/r0802608.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r080/r080260/r0802609.png" />-place functions <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r080/r080260/r08026010.png" /> with the aid of composition if for all <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r080/r080260/r08026011.png" /> the following equality holds:
+
{{TEX|auto}}
 +
{{TEX|done}}
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r080/r080260/r08026012.png" /></td> </tr></table>
+
''partial recursive function''
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r080/r080260/r08026013.png" /></td> </tr></table>
+
One of the mathematical precizations of the intuitive concept of a [[Computable function|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:
  
One says that an <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r080/r080260/r08026014.png" />-place function <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r080/r080260/r08026015.png" /> is obtained from an <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r080/r080260/r08026016.png" />-place function <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r080/r080260/r08026017.png" /> and the <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r080/r080260/r08026018.png" />-place function <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r080/r080260/r08026019.png" /> by means of primitive recursion if for any values of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r080/r080260/r08026020.png" />, the following equalities hold:
+
$$
 +
\psi ( x _ {1}, \dots, x _ {n} ) =
 +
\phi ( f _ {1} ( x _ {1}, \dots, x _ {n} ), \dots, f _ {m} ( x _ {1} \dots x _ {n} )).
 +
$$
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r080/r080260/r08026021.png" /></td> </tr></table>
+
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:
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r080/r080260/r08026022.png" /></td> </tr></table>
+
$$
 +
f( x _ {1}, \dots, x _ {n} , 0= \phi ( x _ {1}, \dots, x _ {n} ),
 +
$$
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r080/r080260/r08026023.png" /></td> </tr></table>
+
$$
 +
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 <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r080/r080260/r08026024.png" />-place function <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r080/r080260/r08026025.png" /> is obtained from the <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r080/r080260/r08026026.png" />-place function <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r080/r080260/r08026027.png" /> with the aid of a minimization operator, or [[Least-number operator|least-number operator]], if for any <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r080/r080260/r08026028.png" /> the condition <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r080/r080260/r08026029.png" /> holds if and only if the values <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r080/r080260/r08026030.png" /> are defined and are not equal to 0, while <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r080/r080260/r08026031.png" />. A partial function <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r080/r080260/r08026032.png" /> 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.
+
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|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, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r080/r080260/r08026033.png" /> is a recursive function if there is a finite sequence of partial functions <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r080/r080260/r08026034.png" /> such that <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r080/r080260/r08026035.png" />, 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|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 <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r080/r080260/r08026036.png" />, and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r080/r080260/r08026037.png" /> is called its Gödel number.
+
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|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.
 
An everywhere-defined recursive function is called general recursive. There are recursive functions that cannot be extended to general recursive functions.
Line 25: Line 65:
 
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
 
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
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r080/r080260/r08026038.png" /></td> </tr></table>
+
$$
 +
a( x, y)  = x + y,\ \
 +
m( x, y)  = x \cdot y ,\ \
 +
I _ {m}  ^ {n} ,
 +
$$
  
 
and
 
and
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r080/r080260/r08026039.png" /></td> </tr></table>
+
$$
 +
k( x, y)  = \left \{
 +
 
 +
\begin{array}{ll}
 +
0  & \textrm{ if }  x < y,  \\
 +
1  & \textrm{ if }  x \geq  y,  \\
 +
\end{array}
 +
 
 +
\right .$$
  
 
using a finite number of composition and minimization operators.
 
using a finite number of composition and minimization operators.

Latest revision as of 15:34, 4 March 2022


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 \{ \begin{array}{ll} 0 & \textrm{ if } x < y, \\ 1 & \textrm{ if } x \geq y, \\ \end{array} \right .$$

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
How to Cite This Entry:
Recursive function. Encyclopedia of Mathematics. URL: http://encyclopediaofmath.org/index.php?title=Recursive_function&oldid=13434
This article was adapted from an original article by V.E. Plisko (originator), which appeared in Encyclopedia of Mathematics - ISBN 1402006098. See original article