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. 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.
utm theorem
Let be an enumeration of Gödel numbers of computable functions. Then the partial function
defined as
is computable.
is called the 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.
- Soare, R. (1987). Recursively enumerable sets and degrees. Perspectives in Mathematical Logic. Springer-Verlag. ISBN 3-540-15299-7.
This article is issued from Wikipedia - version of the Friday, April 03, 2015. The text is available under the Creative Commons Attribution/Share Alike but additional terms may apply for the media files.