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