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[edit]

Comments[edit]

References[edit]