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.

Teorema MTU

Sendo $\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

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

definida como

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

é computável.

$u$ é chamado de função universal.

Referências

• 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