- Utm theorem
In
computability theory the utm theorem or universal turing machine theorem is a basic result aboutGödel numbering s of the set ofcomputable function s. 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 theuniversal 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.utm theorem
Let varphi be a Gödel numbering of the set of computable functions, then the partial function:u_varphi: mathbb{N}^2 o 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
References
*cite book | author = Rogers, H. | title = The Theory of Recursive Functions and Effective Computability | publisher = First MIT press paperback edition | year = 1987 | origyear = 1967 | id = ISBN 0-262-68052-1
*cite book | author = Soare, R.| title = Recursively enumerable sets and degrees | series = Perspectives in Mathematical Logic | publisher = Springer-Verlag | year = 1987 | id = ISBN 3-540-15299-7
Wikimedia Foundation. 2010.