Namespaces
Variants
Actions

Difference between revisions of "Universal function"

From Encyclopedia of Mathematics
Jump to: navigation, search
(Importing text file)
 
m (tex encoded by computer)
Line 1: Line 1:
''for a given (countable) class <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/u/u095/u095680/u0956801.png" /> of functions of type <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/u/u095/u095680/u0956802.png" />''
+
<!--
 +
u0956801.png
 +
$#A+1 = 18 n = 0
 +
$#C+1 = 18 : ~/encyclopedia/old_files/data/U095/U.0905680 Universal function
 +
Automatically converted into TeX, above some diagnostics.
 +
Please remove this comment and the {{TEX|auto}} line below,
 +
if TeX found to be correct.
 +
-->
  
A function <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/u/u095/u095680/u0956803.png" /> of type <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/u/u095/u095680/u0956804.png" /> such that for any function <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/u/u095/u095680/u0956805.png" /> there exists an <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/u/u095/u095680/u0956806.png" /> for which
+
{{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/u/u095/u095680/u0956807.png" /></td> <td valign="top" style="width:5%;text-align:right;">(*)</td></tr></table>
+
''for a given (countable) class  $  K $
 +
of functions of type  $  \mathbf N  ^ {n} \rightarrow \mathbf N $''
  
Here, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/u/u095/u095680/u0956808.png" /> is the set of natural numbers and the equation (*) means that the functions <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/u/u095/u095680/u0956809.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/u/u095/u095680/u09568010.png" /> are defined for the same set of arguments, and their values on this set coincide. Sometimes it is required in the definition of a universal function that for each <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/u/u095/u095680/u09568011.png" /> the function <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/u/u095/u095680/u09568012.png" /> lies in <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/u/u095/u095680/u09568013.png" /> (cf. [[#References|[4]]]). There are a number of other variants of the definition of a universal function (cf. [[#References|[1]]], [[#References|[2]]]).
+
A function  $  F ( y , x _ {1} \dots x _ {n} ) $
 +
of type  $  \mathbf N  ^ {n+} 1 \rightarrow \mathbf N $
 +
such that for any function $  f ( x _ {1} \dots x _ {n} ) \in K $
 +
there exists an  $  i \in \mathbf N $
 +
for which
  
A universal function exists for every countable class of functions. The following universal functions play an important role in the theory of algorithms: 1) universal partial recursive functions for the class of all <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/u/u095/u095680/u09568014.png" />-place <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/u/u095/u095680/u09568015.png" /> partial recursive functions (cf. [[Partial recursive function|Partial recursive function]]); and 2) universal general recursive functions for the class of all <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/u/u095/u095680/u09568016.png" />-place primitive recursive functions (cf. [[Primitive recursive function|Primitive recursive function]]).
+
$$ \tag{* }
 +
f ( x _ {1} \dots x _ {n} ) = \
 +
F ( i , x _ {1} \dots x _ {n} ) .
 +
$$
  
If a function <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/u/u095/u095680/u09568017.png" /> is universal for the class of all one-place partial recursive functions, then it cannot be extended to a total recursive function, and the set <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/u/u095/u095680/u09568018.png" /> is an example of a recursively-enumerable, but not recursive, set of natural numbers (cf. also [[Enumerable set|Enumerable set]]).
+
Here,  $  \mathbf N $
 +
is the set of natural numbers and the equation (*) means that the functions  $  f ( x _ {1} \dots x _ {n} ) $
 +
and  $  F ( i , x _ {1} \dots x _ {n} ) $
 +
are defined for the same set of arguments, and their values on this set coincide. Sometimes it is required in the definition of a universal function that for each  $  i \in \mathbf N $
 +
the function  $  F ( i , x _ {1} \dots x _ {n} ) $
 +
lies in  $  K $(
 +
cf. [[#References|[4]]]). There are a number of other variants of the definition of a universal function (cf. [[#References|[1]]], [[#References|[2]]]).
 +
 
 +
A universal function exists for every countable class of functions. The following universal functions play an important role in the theory of algorithms: 1) universal partial recursive functions for the class of all  $  n $-
 +
place  $  ( n \geq  0 ) $
 +
partial recursive functions (cf. [[Partial recursive function|Partial recursive function]]); and 2) universal general recursive functions for the class of all  $  n $-
 +
place primitive recursive functions (cf. [[Primitive recursive function|Primitive recursive function]]).
 +
 
 +
If a function  $  \psi ( y , x ) $
 +
is universal for the class of all one-place partial recursive functions, then it cannot be extended to a total recursive function, and the set $  \{ {x } : {\psi ( x , x )  \textrm{ is  defined  } } \} $
 +
is an example of a recursively-enumerable, but not recursive, set of natural numbers (cf. also [[Enumerable set|Enumerable set]]).
  
 
====References====
 
====References====
 
<table><TR><TD valign="top">[1]</TD> <TD valign="top">  R. Peter,  "Recursive functions" , Acad. Press  (1967)  (Translated from German)</TD></TR><TR><TD valign="top">[2]</TD> <TD valign="top">  S.C. Kleene,  "Introduction to metamathematics" , North-Holland  (1951)</TD></TR><TR><TD valign="top">[3]</TD> <TD valign="top">  V.A. Uspenskii,  "Leçons sur les fonctions calculables" , Hermann  (1966)  (Translated from Russian)</TD></TR><TR><TD valign="top">[4]</TD> <TD valign="top">  A.I. Mal'tsev,  "Algorithms and recursive functions" , Wolters-Noordhoff  (1970)  (Translated from Russian)</TD></TR></table>
 
<table><TR><TD valign="top">[1]</TD> <TD valign="top">  R. Peter,  "Recursive functions" , Acad. Press  (1967)  (Translated from German)</TD></TR><TR><TD valign="top">[2]</TD> <TD valign="top">  S.C. Kleene,  "Introduction to metamathematics" , North-Holland  (1951)</TD></TR><TR><TD valign="top">[3]</TD> <TD valign="top">  V.A. Uspenskii,  "Leçons sur les fonctions calculables" , Hermann  (1966)  (Translated from Russian)</TD></TR><TR><TD valign="top">[4]</TD> <TD valign="top">  A.I. Mal'tsev,  "Algorithms and recursive functions" , Wolters-Noordhoff  (1970)  (Translated from Russian)</TD></TR></table>
 
 
  
 
====Comments====
 
====Comments====
 
  
 
====References====
 
====References====
 
<table><TR><TD valign="top">[a1]</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">  H. Rogers jr.,  "Theory of recursive functions and effective computability" , McGraw-Hill  (1967)  pp. 164–165</TD></TR></table>

Revision as of 08:27, 6 June 2020


for a given (countable) class $ K $ of functions of type $ \mathbf N ^ {n} \rightarrow \mathbf N $

A function $ F ( y , x _ {1} \dots x _ {n} ) $ of type $ \mathbf N ^ {n+} 1 \rightarrow \mathbf N $ such that for any function $ f ( x _ {1} \dots x _ {n} ) \in K $ there exists an $ i \in \mathbf N $ for which

$$ \tag{* } f ( x _ {1} \dots x _ {n} ) = \ F ( i , x _ {1} \dots x _ {n} ) . $$

Here, $ \mathbf N $ is the set of natural numbers and the equation (*) means that the functions $ f ( x _ {1} \dots x _ {n} ) $ and $ F ( i , x _ {1} \dots x _ {n} ) $ are defined for the same set of arguments, and their values on this set coincide. Sometimes it is required in the definition of a universal function that for each $ i \in \mathbf N $ the function $ F ( i , x _ {1} \dots x _ {n} ) $ lies in $ K $( cf. [4]). There are a number of other variants of the definition of a universal function (cf. [1], [2]).

A universal function exists for every countable class of functions. The following universal functions play an important role in the theory of algorithms: 1) universal partial recursive functions for the class of all $ n $- place $ ( n \geq 0 ) $ partial recursive functions (cf. Partial recursive function); and 2) universal general recursive functions for the class of all $ n $- place primitive recursive functions (cf. Primitive recursive function).

If a function $ \psi ( y , x ) $ is universal for the class of all one-place partial recursive functions, then it cannot be extended to a total recursive function, and the set $ \{ {x } : {\psi ( x , x ) \textrm{ is defined } } \} $ is an example of a recursively-enumerable, but not recursive, set of natural numbers (cf. also Enumerable set).

References

[1] R. Peter, "Recursive functions" , Acad. Press (1967) (Translated from German)
[2] S.C. Kleene, "Introduction to metamathematics" , North-Holland (1951)
[3] V.A. Uspenskii, "Leçons sur les fonctions calculables" , Hermann (1966) (Translated from Russian)
[4] A.I. Mal'tsev, "Algorithms and recursive functions" , Wolters-Noordhoff (1970) (Translated from Russian)

Comments

References

[a1] H. Rogers jr., "Theory of recursive functions and effective computability" , McGraw-Hill (1967) pp. 164–165
How to Cite This Entry:
Universal function. Encyclopedia of Mathematics. URL: http://encyclopediaofmath.org/index.php?title=Universal_function&oldid=49090
This article was adapted from an original article by S.N. Artemov (originator), which appeared in Encyclopedia of Mathematics - ISBN 1402006098. See original article