UTM theorem

In computability theory the utm theorem or universal turing machine theorem is a basic result about effective numberings of the the of computable functions.

Rogers equivalence theorem provides a characterization of the effective numberings of the computable functions in terms of the smn theorem and the utm theorem.

utm theorem

Let $\varphi$ be an effective numbering of the set of computable functions, then the function

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

defined as

$u_{\varphi }(i,x):=\varphi _{i}(x)$

is computable.

$u_{\varphi }$ is called the universal function for $\varphi$