En teoría de la computabilidad , la UTM teorema , o máquina universal de Turing teorema , es un resultado básico sobre numeraciones Gödel del conjunto de las 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 de Turing universal , 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.
Teorema
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 , tanto f ( x ) como u ( e , x ) están definidas y son iguales, o ambas no están definidas. [2]
Por tanto, el teorema muestra que, al definir φ e ( x ) como u ( e , x ), la secuencia φ 1 , φ 2 ,… es una enumeración de las funciones computables parciales. La función en el enunciado del teorema se llama función universal.
Referencias
- Rogers, H. (1987) [1967]. La teoría de las funciones recursivas y la computabilidad efectiva . Primera edición de bolsillo de prensa del MIT. ISBN 0-262-68052-1.
- Soare, R. (1987). Conjuntos y grados recursivamente enumerables . Perspectivas en lógica matemática. Springer-Verlag. ISBN 3-540-15299-7.
- ^ Rogers 1967 , p. 22.
- ^ Soare 1987 , p. 15.