# 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. ). There are a number of other variants of the definition of a universal function (cf. , ).

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

How to Cite This Entry:
Universal function. Encyclopedia of Mathematics. URL: http://encyclopediaofmath.org/index.php?title=Universal_function&oldid=51016
This article was adapted from an original article by S.N. Artemov (originator), which appeared in Encyclopedia of Mathematics - ISBN 1402006098. See original article