Teorema UTM

En la teoría de la computabilidad , el teorema de la máquina de Turing universal ( MTU ) es un resultado fundamental sobre las numeraciones de Gödel del conjunto de funciones computables . Afirma la existencia de una función universal computable , 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.

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 un número e tal que${\displaystyle f(x)\simeq u(e,x)}$para todo x . Esto significa que, para cada x , o bien f ( x ) y u ( e , x ) están ambas definidas y son iguales, o bien ambas no están definidas. ^{[ 2 ]}

El teorema muestra, por lo tanto, que al definir φ _e ( x ) como u ( e , x ), la secuencia φ ₁ , φ ₂ , ... es una enumeración ( numeración ) de las funciones computables parciales. De hecho, u puede elegirse de manera que esta sea la numeración estándar . La función${\displaystyle u}$En el enunciado del teorema se la denomina función universal.

• Rogers, H. (1987) [1967]. La teoría de las funciones recursivas y la computabilidad efectiva . Primera edición en rústica de MIT Press. 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.