UTM theorem

{{short description|Affirms the existence of a computable universal function}}

In computability theory, the {{Abbr|UTM|universal Turing Machine}} 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.{{Sfn|Rogers|1987|p=22}} 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.

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 $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.{{Sfn|Soare|1987|p=15}}

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

{{cite book|last=Rogers |first=H. |title=The Theory of Recursive Functions and Effective Computability|publisher=First MIT press paperback edition|year=1987|orig-year=1967|isbn=0-262-68052-1}}
{{cite book|last=Soare |first=R. |title=Recursively enumerable sets and degrees|series=Perspectives in Mathematical Logic|publisher=Springer-Verlag|year=1987|isbn=3-540-15299-7}}

Category:Theorems in theory of computation

Category:Computability theory