Utm theorem

From Wikipedia, the free encyclopedia

You have new messages (last change).
The correct title of this article is utm theorem. The initial letter is shown capitalized due to technical restrictions.

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 proves 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 universal turing machine thus the name of the theorem.

Rogers equivalence theorem provides a characterization of the Gödel numbering of the computable functions in terms of the smn theorem and the utm theorem.

[edit] utm theorem

Let \varphi be a Gödel numbering of the set of computable functions, then the partial function

u_\varphi: \mathbb{N}^2 \to \mathbb{N}

defined as

u_\varphi(i,x) := \varphi_i(x) \qquad i,x \in \mathbb{N}

is computable.

u_\varphi is called the universal function for \varphi

[edit] References

  • Rogers, H. [1967] (1987). 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. 
Retrieved from "http://en.wikipedia.org../../../u/t/m/Utm_theorem.html"