computability theory Computability theory, also known as recursion theory, is a branch of mathematical logic, computer science, and the theory of computation that originated in the 1930s with the study of computable functions and Turing degrees. The field has since ex ...

, the theorem, or

universal Turing machine In computer science, a universal Turing machine (UTM) is a Turing machine capable of computing any computable sequence, as described by Alan Turing in his seminal paper "On Computable Numbers, with an Application to the Entscheidungsproblem". Co ...

theorem, is a basic result about Gödel numberings of the set of

computable function Computable functions are the basic objects of study in computability theory. Informally, a function is ''computable'' if there is an algorithm that computes the value of the function for every value of its argument. Because of the lack of a precis ...

s. It affirms the existence of a computable universal function, which is capable of calculating any other computable function. The universal function is an abstract version of the

, thus the name of the theorem. Roger's equivalence theorem provides a characterization of the Gödel numbering of the computable functions in terms of the ''s_mn'' theorem and the UTM theorem.

Theorem

The theorem states that a

partial Partial may refer to: Mathematics *Partial derivative, derivative with respect to one of several variables of a function, with the other variables held constant ** ∂, a symbol that can denote a partial derivative, sometimes pronounced "partial d ...

''u'' of two variables exists such that, for every computable function ''f'' of one variable, an ''e'' exists such that

f(x) \simeq u(e,x)

for all ''x''. This means that, for each ''x'', either ''f''(''x'') and ''u''(''e'',''x'') are both defined and are equal, or are both undefined. The theorem thus shows that, defining φ_''e''(''x'') as ''u''(''e'', ''x''), the sequence φ₁, φ₂, ... is an enumeration of the partial computable functions. The function

u

in the statement of the theorem is called a universal function.

References

* * Theorems in theory of computation Computability theory {{mathlogic-stub