En teoría de la computabilidad , el teorema UTM , o teorema de la máquina universal de Turing , es un resultado básico sobre las numeraciones de Gödel del conjunto de funciones computables . Afirma la existencia de una función universal computable , que es capaz de calcular cualquier otra función computable. [1] La función universal es una versión abstracta de la máquina universal de Turing , de ahí el nombre del teorema.
El teorema de equivalencia de Roger proporciona una caracterización de la numeración de Gödel de las funciones computables en términos del teorema s mn y el teorema UTM.
El teorema establece que existe una función computable parcial u de dos variables tal que, para cada función computable f de una variable, existe una e tal que para todo x . Esto significa que, para cada x , f ( x ) y u ( e , x ) están definidas y son iguales, o ambas son indefinidas. [2]
El teorema muestra que, definiendo φ e ( x ) como u ( e , x ), la sucesión φ 1 , φ 2 , ... es una enumeración de las funciones parciales computables. La función en el enunciado del teorema se denomina función universal.
