# UTM theorem

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 smn theorem and the UTM theorem.

## Theorem

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 ${\displaystyle 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.[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 ${\displaystyle u}$  in the statement of the theorem is called a universal function.

## References

• Rogers, H. (1987) [1967]. The Theory of Recursive Functions and Effective Computability. First MIT press paperback edition. ISBN 0-262-68052-1.CS1 maint: ref=harv (link)
• Soare, R. (1987). Recursively enumerable sets and degrees. Perspectives in Mathematical Logic. Springer-Verlag. ISBN 3-540-15299-7.CS1 maint: ref=harv (link)
1. ^ Rogers 1967, p. 22.
2. ^ Soare 1987, p. 15.