Namespaces
Variants
Actions

Difference between revisions of "Primitive recursive function"

From Encyclopedia of Mathematics
Jump to: navigation, search
(Importing text file)
 
m (tex encoded by computer)
Line 1: Line 1:
 +
<!--
 +
p0746101.png
 +
$#A+1 = 47 n = 0
 +
$#C+1 = 47 : ~/encyclopedia/old_files/data/P074/P.0704610 Primitive 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.
 +
-->
 +
 +
{{TEX|auto}}
 +
{{TEX|done}}
 +
 
A function from natural numbers to natural numbers which can be obtained from the initial functions
 
A function from natural numbers to natural numbers which can be obtained from the initial 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/p/p074/p074610/p0746101.png" /></td> </tr></table>
+
$$
 +
s ( x)  = x + 1,\ \
 +
o ( x)  = 0,\ \
 +
I _ {m}  ^ {n} ( x _ {1} \dots x _ {n} )  = x _ {m}  $$
  
 
by a finite number of the operations of composition and [[Primitive recursion|primitive recursion]].
 
by a finite number of the operations of composition and [[Primitive recursion|primitive recursion]].
  
Since the initial functions are computable and the operators of superposition and primitive recursion preserve computability, the set of all primitive recursive functions is a subclass of the class of all computable functions (cf. [[Computable function|Computable function]]). Every primitive recursive function is specified by a description of its construction from the initial functions (a primitive recursive description); hence the class of primitive recursive functions is countable. Practically all arithmetic functions used in mathematics for some concrete reason are primitive recursive functions; e.g. <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p074/p074610/p0746102.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p074/p074610/p0746103.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p074/p074610/p0746104.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p074/p074610/p0746105.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p074/p074610/p0746106.png" /> (the remainder from division of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p074/p074610/p0746107.png" /> by <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p074/p074610/p0746108.png" />), <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p074/p074610/p0746109.png" /> (the prime number with index <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p074/p074610/p07461010.png" />), etc.
+
Since the initial functions are computable and the operators of superposition and primitive recursion preserve computability, the set of all primitive recursive functions is a subclass of the class of all computable functions (cf. [[Computable function|Computable function]]). Every primitive recursive function is specified by a description of its construction from the initial functions (a primitive recursive description); hence the class of primitive recursive functions is countable. Practically all arithmetic functions used in mathematics for some concrete reason are primitive recursive functions; e.g. $  x + y $,  
 +
$  x \cdot y $,  
 +
$  x  ^ {y} $,  
 +
$  \mathop{\rm sign} ( x) $,  
 +
$  [ x/y] $(
 +
the remainder from division of $  x $
 +
by $  y $),  
 +
$  \pi ( x) $(
 +
the prime number with index $  x $),  
 +
etc.
  
A relation <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p074/p074610/p07461011.png" /> on natural numbers is called a primitive recursive relation if the function <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p074/p074610/p07461012.png" />, equal to 1 if <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p074/p074610/p07461013.png" /> is true and 0 if <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p074/p074610/p07461014.png" /> is false, is primitive recursive. One says that the relation <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p074/p074610/p07461015.png" /> has been obtained from a relation <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p074/p074610/p07461016.png" /> by means of a bounded quantifier if
+
A relation $  P ( x _ {1} \dots x _ {n} ) $
 +
on natural numbers is called a primitive recursive relation if the function $  g ( x _ {1} \dots x _ {n} ) $,  
 +
equal to 1 if $  P ( x _ {1} \dots x _ {n} ) $
 +
is true and 0 if $  P ( x _ {1} \dots x _ {n} ) $
 +
is false, is primitive recursive. One says that the relation $  P ( x _ {1} \dots x _ {n} , z) $
 +
has been obtained from a relation $  Q ( x _ {1} \dots x _ {n} , y, z) $
 +
by means of a bounded quantifier if
  
<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/p/p074/p074610/p07461017.png" /></td> </tr></table>
+
$$
 +
P ( x _ {1} \dots x _ {n} , z)  \iff \
 +
\forall y  ( y \leq  z \Rightarrow Q
 +
( x _ {1} \dots x _ {n} , y, z))
 +
$$
  
 
or
 
or
  
<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/p/p074/p074610/p07461018.png" /></td> </tr></table>
+
$$
 +
P ( x _ {1} \dots x _ {n} , z)  \iff \
 +
\exists y  ( y \leq  z \& Q
 +
( x _ {1} \dots x _ {n} , y, z)).
 +
$$
  
 
The class of primitive recursive relations is closed under the application of logical connectives (including negation) and bounded quantifiers.
 
The class of primitive recursive relations is closed under the application of logical connectives (including negation) and bounded quantifiers.
  
Suppose that <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p074/p074610/p07461019.png" /> are <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p074/p074610/p07461020.png" />-place primitive recursive functions, and let <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p074/p074610/p07461021.png" /> be primitive recursive relations such that for any set of argument values at most one of them is true. Then the function
+
Suppose that $  f _ {1} \dots f _ {s + 1 }  $
 +
are $  n $-
 +
place primitive recursive functions, and let $  P _ {1} \dots P _ {s} $
 +
be primitive recursive relations such that for any set of argument values at most one of them is true. Then the 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/p/p074/p074610/p07461022.png" /></td> <td valign="top" style="width:5%;text-align:right;">(*)</td></tr></table>
+
$$ \tag{* }
 +
f ( x _ {1} \dots x _ {n} ) = \
 +
\left \{
  
 
is primitive recursive.
 
is primitive recursive.
  
One says that the function <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p074/p074610/p07461023.png" /> has been obtained from an everywhere-defined function <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p074/p074610/p07461024.png" /> by means of the bounded minimization operator if <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p074/p074610/p07461025.png" /> is equal to the minimal <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p074/p074610/p07461026.png" /> such that <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p074/p074610/p07461027.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p074/p074610/p07461028.png" />, and is equal to <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p074/p074610/p07461029.png" /> otherwise. The class of primitive recursive functions is closed under bounded minimization operators.
+
One says that the function $  f ( x _ {1} \dots x _ {n} , z) $
 +
has been obtained from an everywhere-defined function $  g ( x _ {1} \dots x _ {n} , y, z) $
 +
by means of the bounded minimization operator if $  f ( x _ {1} \dots x _ {n} , z) $
 +
is equal to the minimal $  y $
 +
such that $  y \leq  z $
 +
and $  g ( x _ {1} \dots x _ {n} , y, z) = 0 $,  
 +
and is equal to $  z + 1 $
 +
otherwise. The class of primitive recursive functions is closed under bounded minimization operators.
  
A function <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p074/p074610/p07461030.png" /> is called universal for the class of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p074/p074610/p07461031.png" />-place primitive recursive functions if for each such function <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p074/p074610/p07461032.png" /> there is a natural number <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p074/p074610/p07461033.png" /> such that
+
A function $  \Phi ( y, x _ {1} \dots x _ {n} ) $
 +
is called universal for the class of $  n $-
 +
place primitive recursive functions if for each such function $  f ( x _ {1} \dots x _ {n} ) $
 +
there is a natural number $  k $
 +
such that
  
<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/p/p074/p074610/p07461034.png" /></td> </tr></table>
+
$$
 +
f ( x _ {1} \dots x _ {n} )  = \
 +
\Phi ( k, x _ {1} \dots x _ {n} ).
 +
$$
  
There exists a universal function for every <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p074/p074610/p07461035.png" />, but it need not be primitive recursive.
+
There exists a universal function for every $  n \geq  1 $,  
 +
but it need not be primitive recursive.
  
Every recursively enumerable set is the range of values of a primitive recursive function; every recursively enumerable relation <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p074/p074610/p07461036.png" /> can be represented as <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p074/p074610/p07461037.png" />, where <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p074/p074610/p07461038.png" /> is a primitive recursive relation. Every primitive recursive function can be represented in formal arithmetic (cf. [[Arithmetic, formal|Arithmetic, formal]]); i.e. for each primitive recursive function <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p074/p074610/p07461039.png" /> there is an arithmetical formula <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p074/p074610/p07461040.png" /> such that for all natural numbers <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p074/p074610/p07461041.png" />, the formula <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p074/p074610/p07461042.png" /> is derivable in formal arithmetic if <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p074/p074610/p07461043.png" />, while <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p074/p074610/p07461044.png" /> is derivable if <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p074/p074610/p07461045.png" />. (Here <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p074/p074610/p07461046.png" /> are arithmetical terms reflecting the natural numbers <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p074/p074610/p07461047.png" /> in formal arithmetic.) This fact takes a central position in the proof of the incompleteness of formal arithmetic (cf. [[#References|[4]]]).
+
Every recursively enumerable set is the range of values of a primitive recursive function; every recursively enumerable relation $  R ( x _ {1} \dots x _ {n} ) $
 +
can be represented as $  \exists y  A ( y, x _ {1} \dots x _ {n} ) $,  
 +
where $  A $
 +
is a primitive recursive relation. Every primitive recursive function can be represented in formal arithmetic (cf. [[Arithmetic, formal|Arithmetic, formal]]); i.e. for each primitive recursive function $  f ( x _ {1} \dots x _ {n} ) $
 +
there is an arithmetical formula $  F ( y, x _ {1} \dots x _ {n} ) $
 +
such that for all natural numbers $  k _ {1} \dots k _ {n} , m $,  
 +
the formula $  F ( \overline{m}\; , \overline{k}\; _ {1} \dots \overline{k}\; _ {n} ) $
 +
is derivable in formal arithmetic if $  f ( k _ {1} \dots k _ {n} ) = m $,  
 +
while $  \neg F ( \overline{m}\; , \overline{k}\; _ {1} \dots \overline{k}\; _ {n} ) $
 +
is derivable if $  f ( k _ {1} \dots k _ {n} ) \neq m $.  
 +
(Here $  \overline{k}\; _ {1} \dots \overline{k}\; _ {n} , \overline{m}\; $
 +
are arithmetical terms reflecting the natural numbers $  k _ {1} \dots k _ {n} , m $
 +
in formal arithmetic.) This fact takes a central position in the proof of the incompleteness of formal arithmetic (cf. [[#References|[4]]]).
  
 
====References====
 
====References====
 
<table><TR><TD valign="top">[1]</TD> <TD valign="top">  V.A. Uspenskii,  "Leçons sur les fonctions calculables" , Hermann  (1966)  (Translated from Russian)</TD></TR><TR><TD valign="top">[2]</TD> <TD valign="top">  A.I. Mal'tsev,  "Algorithms and recursive functions" , Wolters-Noordhoff  (1970)  (Translated from Russian)</TD></TR><TR><TD valign="top">[3]</TD> <TD valign="top">  H. Rogers jr.,  "Theory of recursive functions and effective computability" , McGraw-Hill  (1967)  pp. 164–165</TD></TR><TR><TD valign="top">[4]</TD> <TD valign="top">  E. Mendelson,  "Introduction to mathematical logic" , v. Nostrand  (1964)</TD></TR></table>
 
<table><TR><TD valign="top">[1]</TD> <TD valign="top">  V.A. Uspenskii,  "Leçons sur les fonctions calculables" , Hermann  (1966)  (Translated from Russian)</TD></TR><TR><TD valign="top">[2]</TD> <TD valign="top">  A.I. Mal'tsev,  "Algorithms and recursive functions" , Wolters-Noordhoff  (1970)  (Translated from Russian)</TD></TR><TR><TD valign="top">[3]</TD> <TD valign="top">  H. Rogers jr.,  "Theory of recursive functions and effective computability" , McGraw-Hill  (1967)  pp. 164–165</TD></TR><TR><TD valign="top">[4]</TD> <TD valign="top">  E. Mendelson,  "Introduction to mathematical logic" , v. Nostrand  (1964)</TD></TR></table>
 
 
  
 
====Comments====
 
====Comments====

Revision as of 08:07, 6 June 2020


A function from natural numbers to natural numbers which can be obtained from the initial functions

$$ s ( x) = x + 1,\ \ o ( x) = 0,\ \ I _ {m} ^ {n} ( x _ {1} \dots x _ {n} ) = x _ {m} $$

by a finite number of the operations of composition and primitive recursion.

Since the initial functions are computable and the operators of superposition and primitive recursion preserve computability, the set of all primitive recursive functions is a subclass of the class of all computable functions (cf. Computable function). Every primitive recursive function is specified by a description of its construction from the initial functions (a primitive recursive description); hence the class of primitive recursive functions is countable. Practically all arithmetic functions used in mathematics for some concrete reason are primitive recursive functions; e.g. $ x + y $, $ x \cdot y $, $ x ^ {y} $, $ \mathop{\rm sign} ( x) $, $ [ x/y] $( the remainder from division of $ x $ by $ y $), $ \pi ( x) $( the prime number with index $ x $), etc.

A relation $ P ( x _ {1} \dots x _ {n} ) $ on natural numbers is called a primitive recursive relation if the function $ g ( x _ {1} \dots x _ {n} ) $, equal to 1 if $ P ( x _ {1} \dots x _ {n} ) $ is true and 0 if $ P ( x _ {1} \dots x _ {n} ) $ is false, is primitive recursive. One says that the relation $ P ( x _ {1} \dots x _ {n} , z) $ has been obtained from a relation $ Q ( x _ {1} \dots x _ {n} , y, z) $ by means of a bounded quantifier if

$$ P ( x _ {1} \dots x _ {n} , z) \iff \ \forall y ( y \leq z \Rightarrow Q ( x _ {1} \dots x _ {n} , y, z)) $$

or

$$ P ( x _ {1} \dots x _ {n} , z) \iff \ \exists y ( y \leq z \& Q ( x _ {1} \dots x _ {n} , y, z)). $$

The class of primitive recursive relations is closed under the application of logical connectives (including negation) and bounded quantifiers.

Suppose that $ f _ {1} \dots f _ {s + 1 } $ are $ n $- place primitive recursive functions, and let $ P _ {1} \dots P _ {s} $ be primitive recursive relations such that for any set of argument values at most one of them is true. Then the function

$$ \tag{* } f ( x _ {1} \dots x _ {n} ) = \ \left \{ is primitive recursive. One says that the function $ f ( x _ {1} \dots x _ {n} , z) $ has been obtained from an everywhere-defined function $ g ( x _ {1} \dots x _ {n} , y, z) $ by means of the bounded minimization operator if $ f ( x _ {1} \dots x _ {n} , z) $ is equal to the minimal $ y $ such that $ y \leq z $ and $ g ( x _ {1} \dots x _ {n} , y, z) = 0 $, and is equal to $ z + 1 $ otherwise. The class of primitive recursive functions is closed under bounded minimization operators. A function $ \Phi ( y, x _ {1} \dots x _ {n} ) $ is called universal for the class of $ n $- place primitive recursive functions if for each such function $ f ( x _ {1} \dots x _ {n} ) $ there is a natural number $ k $ such that $$ f ( x _ {1} \dots x _ {n} ) = \ \Phi ( k, x _ {1} \dots x _ {n} ). $$

There exists a universal function for every $ n \geq 1 $, but it need not be primitive recursive.

Every recursively enumerable set is the range of values of a primitive recursive function; every recursively enumerable relation $ R ( x _ {1} \dots x _ {n} ) $ can be represented as $ \exists y A ( y, x _ {1} \dots x _ {n} ) $, where $ A $ is a primitive recursive relation. Every primitive recursive function can be represented in formal arithmetic (cf. Arithmetic, formal); i.e. for each primitive recursive function $ f ( x _ {1} \dots x _ {n} ) $ there is an arithmetical formula $ F ( y, x _ {1} \dots x _ {n} ) $ such that for all natural numbers $ k _ {1} \dots k _ {n} , m $, the formula $ F ( \overline{m}\; , \overline{k}\; _ {1} \dots \overline{k}\; _ {n} ) $ is derivable in formal arithmetic if $ f ( k _ {1} \dots k _ {n} ) = m $, while $ \neg F ( \overline{m}\; , \overline{k}\; _ {1} \dots \overline{k}\; _ {n} ) $ is derivable if $ f ( k _ {1} \dots k _ {n} ) \neq m $. (Here $ \overline{k}\; _ {1} \dots \overline{k}\; _ {n} , \overline{m}\; $ are arithmetical terms reflecting the natural numbers $ k _ {1} \dots k _ {n} , m $ in formal arithmetic.) This fact takes a central position in the proof of the incompleteness of formal arithmetic (cf. [4]).

References

[1] V.A. Uspenskii, "Leçons sur les fonctions calculables" , Hermann (1966) (Translated from Russian)
[2] A.I. Mal'tsev, "Algorithms and recursive functions" , Wolters-Noordhoff (1970) (Translated from Russian)
[3] H. Rogers jr., "Theory of recursive functions and effective computability" , McGraw-Hill (1967) pp. 164–165
[4] E. Mendelson, "Introduction to mathematical logic" , v. Nostrand (1964)

Comments

The fact that the function (*) is primitive recursive under the given assumptions is often rephrased as: the class of primitive recursive functions is closed under "definition by cases" .

References

[a1] C. Calude, "Theories of computational complexity" , North-Holland (1988)
How to Cite This Entry:
Primitive recursive function. Encyclopedia of Mathematics. URL: http://encyclopediaofmath.org/index.php?title=Primitive_recursive_function&oldid=11732
This article was adapted from an original article by S.N. Artemov (originator), which appeared in Encyclopedia of Mathematics - ISBN 1402006098. See original article