• Source: 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.
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



f
(
x
)
≃
u
(
e
,
x
)


{\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.
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



u


{\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.
Soare, R. (1987). Recursively enumerable sets and degrees. Perspectives in Mathematical Logic. Springer-Verlag. ISBN 3-540-15299-7.

Kata Kunci Pencarian:

• Bilangan prima
• UTM theorem
• Universal Transverse Mercator coordinate system
• Universal Turing machine
• Universal function
• Prime number
• Twin prime
• Chaitin's constant
• Cullen number
• Universality probability
• Illegal number