Namespaces
Variants
Actions

Difference between revisions of "General recursive function"

From Encyclopedia of Mathematics
Jump to: navigation, search
(Importing text file)
 
m (fixing dots)
 
(One intermediate revision by one other user not shown)
Line 1: Line 1:
A [[Partial recursive function|partial recursive function]] that is defined for all values of its arguments. The concept of a general recursive function can also be defined independently of the concept of a partial recursive function as follows. The class of all general recursive functions is the smallest class of functions containing all primitive recursive functions (cf. [[Primitive recursive function|Primitive recursive function]]) and closed under composition of functions and the [[Least-number operator|least-number operator]], under the condition that the latter is only applied to a function <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g043/g043700/g0437001.png" /> when
+
A [[Partial recursive function|partial recursive function]] that is defined for all values of its arguments. The concept of a general recursive function can also be defined independently of the concept of a partial recursive function as follows. The class of all general recursive functions is the smallest class of functions containing all [[primitive recursive function]]s and closed under composition of functions and the [[least-number operator]] $\mu$, under the condition that $\mu$ is only applied to a function $g(x_1,\dots,x_n,y)$ when
 +
$$
 +
\forall x_1,\dots,x_n \exists y\, g(x_1,\dots,x_n,y) = 0 \ .
 +
$$
  
<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/g/g043/g043700/g0437002.png" /></td> </tr></table>
+
However, the study of general recursive functions is usually carried out within the class of all partial recursive functions. This is related, in particular, to the fact that there is no number $n>0$ for which there exists a general recursive function that is universal for the class of all $n$-place general recursive functions.
  
However, the study of general recursive functions is usually carried out within the class of all partial recursive functions. This is related, in particular, to the fact that there is no number <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g043/g043700/g0437003.png" /> for which there exists a general recursive function that is universal for the class of all <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g043/g043700/g0437004.png" />-place general recursive functions.
+
All general recursive functions are explicitly definable in [[Arithmetic, formal|formal arithmetic]] in the sense that for any such function $f(x_1,\dots,x_n)$ an arithmetical formula $F(x_1,\dots,x_n,y)$ can be constructed with the following property: For any natural numbers $k_1,\dots,k_n,k$, if $f(k_1,\dots,k_n) = k$, then $\vdash F(\bar k_1,\dots,\bar k_n,\bar k)$ ; but if $f(k_1,\dots,k_n) \ne k$, then $\vdash \neg F(\bar k_1,\dots,\bar k_n,\bar k)$, where $\bar k_1,\dots,\bar k_n,\bar k$ are the terms representing the numbers $k_1,\dots,k_n,k$, and the symbol $\vdash$ denotes derivability in the arithmetic calculus.
 
 
All general recursive functions are explicitly definable in formal arithmetic (cf. [[Arithmetic, formal|Arithmetic, formal]]) in the sense that for any such function <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g043/g043700/g0437005.png" /> an arithmetical formula <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g043/g043700/g0437006.png" /> can be constructed with the following property: For any natural numbers <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g043/g043700/g0437007.png" />, if <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g043/g043700/g0437008.png" />, then <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g043/g043700/g0437009.png" />; but if <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g043/g043700/g04370010.png" />, then <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g043/g043700/g04370011.png" />, where <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g043/g043700/g04370012.png" /> are the terms representing the numbers <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g043/g043700/g04370013.png" />, and the symbol <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g043/g043700/g04370014.png" /> denotes derivability in the arithmetic calculus.
 
  
 
====References====
 
====References====
<table><TR><TD valign="top">[1]</TD> <TD valign="top">  P.S. Novikov,  "Elements of mathematical logic" , Oliver &amp; Boyd and Addison-Wesley  (1964)  (Translated from Russian)</TD></TR><TR><TD valign="top">[2]</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">  P.S. Novikov,  "Elements of mathematical logic" , Oliver &amp; Boyd and Addison-Wesley  (1964)  (Translated from Russian)</TD></TR>
 +
<TR><TD valign="top">[2]</TD> <TD valign="top">  E. Mendelson,  "Introduction to mathematical logic" , v. Nostrand  (1964)</TD></TR>
 +
</table>
  
  
Line 16: Line 20:
  
 
====References====
 
====References====
<table><TR><TD valign="top">[a1]</TD> <TD valign="top">  S.C. Kleene,  "Introduction to metamathematics" , North-Holland  (1951)</TD></TR><TR><TD valign="top">[a2]</TD> <TD valign="top">  H. Rogers jr.,  "Theory of recursive functions and effective computability" , McGraw-Hill  (1967)  pp. 164–165</TD></TR></table>
+
<table>
 +
<TR><TD valign="top">[a1]</TD> <TD valign="top">  S.C. Kleene,  "Introduction to metamathematics" , North-Holland  (1951)</TD></TR>
 +
<TR><TD valign="top">[a2]</TD> <TD valign="top">  H. Rogers jr.,  "Theory of recursive functions and effective computability" , McGraw-Hill  (1967)  pp. 164–165</TD></TR>
 +
</table>
 +
 
 +
{{TEX|done}}

Latest revision as of 11:52, 31 January 2022

A partial recursive function that is defined for all values of its arguments. The concept of a general recursive function can also be defined independently of the concept of a partial recursive function as follows. The class of all general recursive functions is the smallest class of functions containing all primitive recursive functions and closed under composition of functions and the least-number operator $\mu$, under the condition that $\mu$ is only applied to a function $g(x_1,\dots,x_n,y)$ when $$ \forall x_1,\dots,x_n \exists y\, g(x_1,\dots,x_n,y) = 0 \ . $$

However, the study of general recursive functions is usually carried out within the class of all partial recursive functions. This is related, in particular, to the fact that there is no number $n>0$ for which there exists a general recursive function that is universal for the class of all $n$-place general recursive functions.

All general recursive functions are explicitly definable in formal arithmetic in the sense that for any such function $f(x_1,\dots,x_n)$ an arithmetical formula $F(x_1,\dots,x_n,y)$ can be constructed with the following property: For any natural numbers $k_1,\dots,k_n,k$, if $f(k_1,\dots,k_n) = k$, then $\vdash F(\bar k_1,\dots,\bar k_n,\bar k)$ ; but if $f(k_1,\dots,k_n) \ne k$, then $\vdash \neg F(\bar k_1,\dots,\bar k_n,\bar k)$, where $\bar k_1,\dots,\bar k_n,\bar k$ are the terms representing the numbers $k_1,\dots,k_n,k$, and the symbol $\vdash$ denotes derivability in the arithmetic calculus.

References

[1] P.S. Novikov, "Elements of mathematical logic" , Oliver & Boyd and Addison-Wesley (1964) (Translated from Russian)
[2] E. Mendelson, "Introduction to mathematical logic" , v. Nostrand (1964)


Comments

References

[a1] S.C. Kleene, "Introduction to metamathematics" , North-Holland (1951)
[a2] H. Rogers jr., "Theory of recursive functions and effective computability" , McGraw-Hill (1967) pp. 164–165
How to Cite This Entry:
General recursive function. Encyclopedia of Mathematics. URL: http://encyclopediaofmath.org/index.php?title=General_recursive_function&oldid=18346
This article was adapted from an original article by V.E. Plisko (originator), which appeared in Encyclopedia of Mathematics - ISBN 1402006098. See original article