teorema MTU
Aspeto
Este artigo ou secção contém uma lista de referências no fim do texto, mas as suas fontes não são claras porque não são citadas no corpo do artigo, o que compromete a confiabilidade das informações. (Agosto de 2021) |
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
[editar | editar código-fonte]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
[editar | editar código-fonte]- 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