View source for Universal function

<!--
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.
-->

{{TEX|auto}}
{{TEX|done}}

''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. [[#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====
<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====

====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>