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 uma enumeração de números de Gödel de funções computáveis. Então, a função parcial
definida como
é computável.
é chamado de função universal.
Referências
Categoria:Teoria da computabilidade