# UTM theorem

This article includes a list of references, but its sources remain unclear because it has insufficient inline citations. (August 2019) (Learn how and when to remove this template message) |

In computability theory, the **UTM theorem**, or **universal Turing machine theorem**, is a basic result about Gödel numberings of the set of computable functions. It affirms the existence of a computable **universal function**, which is capable of calculating any other computable function.^{[1]} The universal function is an abstract version of the universal Turing machine, 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.

## TheoremEdit

The theorem states that a partial computable function *u* of two variables exists such that, for every computable function *f* of one variable, an *e* exists such that 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.^{[2]}

The theorem thus shows that, defining φ_{e}(*x*) as *u*(*e*, *x*), the sequence φ_{1}, φ_{2}, … is an enumeration of the partial computable functions. The function in the statement of the theorem is called a universal function.

## ReferencesEdit

- Rogers, H. (1987) [1967].
*The Theory of Recursive Functions and Effective Computability*. First MIT press paperback edition. ISBN 0-262-68052-1. - Soare, R. (1987).
*Recursively enumerable sets and degrees*. Perspectives in Mathematical Logic. Springer-Verlag. ISBN 3-540-15299-7.

This mathematical logic-related article is a stub. You can help Wikipedia by expanding it. |

**^**Rogers 1967, p. 22.**^**Soare 1987, p. 15.