Teorema MTU

Predefinição:Sem notas Predefinição:Minúscula 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 ${\phi }_1,{\phi }_2,{\phi }_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):={\phi }_i(x)i,x\in \mathbb{N}$

é computável.

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

Referências

• Predefinição:Citar livro
• Predefinição:Citar livro