Teorema MTU

Na Teoria da computabilidade, o Teorema MTU, ou o teorema da Máquina de Turing universal, é um resultado básico sobre os números de Gödel do conjunto de funções computáveis. Ele afirma a existência de uma função universal computável, a qual é capaz de calcular qualquer outra função computável. A função universal é uma versão abstrata da Máquina de Turing universal, advindo daí o nome do teorema.

Teorema da equivalência de Rogers proporciona uma caracterização da numeração de Gödel de funções computáveis em termos do teorema smn e do teorema MTU.

Sendo ${\displaystyle \varphi _{1},\varphi _{2},\varphi _{3},...}$ uma enumeração de números de Gödel de funções computáveis. Então, a função parcial

${\displaystyle u:\mathbb {N} ^{2}\to \mathbb {N} }$

definida como

${\displaystyle u(i,x):=\varphi _{i}(x)\qquad i,x\in \mathbb {N} }$

é computável.

${\displaystyle u}$ é chamado de função universal.

• Rogers, H. (1987) [1967]. The Theory of Recursive Functions and Effective Computability. [S.l.]: First MIT press paperback edition. ISBN 0-262-68052-1 
• Soare, R. (1987). Recursively enumerable sets and degrees. Col: Perspectives in Mathematical Logic. [S.l.]: Springer-Verlag. ISBN 3-540-15299-7