Universal function

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)

References

[a1]	H. Rogers jr., "Theory of recursive functions and effective computability" , McGraw-Hill (1967) pp. 164–165