¿Cómo sabemos que cada Máquina Turing que se detiene puede expresarse como una función recursiva?

Question

He oído muchas veces que un resultado importante en la Teoría de la Recursividad es la equivalencia de Turing y la de Gödel modelos: las funciones realizables por una máquina de Turing son precisamente las funciones que pueden ser construidos a partir de las funciones recursivas primitivas a través de la composición y primitivo de la recursividad.

Estoy interesado en la prueba en la dirección de Turing $\to$ Gödel. ¿Cómo podemos tomar una máquina de Turing y llegar a una definición recursiva de una función que es equivalente a la lengua se decidió por la máquina de Turing?

Una explicación o un puntero a la ponencia(s) que demuestran que este resultado sería muy apreciada. Gracias!

Answer 1

Usted puede encontrar la prueba en cada matemáticos libro sobre la teoría de la recursividad. El argumento es más o menos la siguiente:

1. Si $f : \mathbb{N} \to \mathbb{N}$ y el gráfico de $\Gamma_f$ $f$ es recursivamente enumerable, a continuación, $f$ es recursiva.

2. Para cada Máquina de Turing no hay un único número de Gödel, que codifica la máquina.

3. Si $f$ es de Turing, a continuación, la gráfica es recursivamente enumerable. Esto se constata por decir \begin{equation} (x,y) \in \Gamma_f \Leftrightarrow \exists s \in B_n(e,x_1,\ldots,x_n,y,s) \end{equation} donde: $B_n$ es el conjunto de todos los $(e,x_1,\ldots,x_n,y,s) \in \mathbb{N}^{n+3}$ tal que

   • $e$ es el número de Gödel de la Máquina $M$, $s$ es el número de Gödel de la operación de cálculo de la máquina de $M$, la máquina de $M$, $x_1,\ldots,x_n \to y$

   que es una primitiva recursiva conjunto.

4. El reclamo de la siguiente manera a partir de la 1 y la 3.

Si desea más información sobre cualquiera de estos pasos, hágamelo saber.

EDIT: como Marc van Leeuwen señaló en el comentario anterior, esto demuestra que Turing funciones recursivas. El conjunto de funciones Turing no es el mismo que el conjunto de primitivas de funciones recursivas.

Answer 2

Como dice @mjb, este es un resultado de libro absolutamente estándar (al menos cuando se corrige al soltar "primitivo").

Pides punteros a la literatura. Para obtener un bosquejo de prueba ligeramente amplificador que da @mjb, puede probar mi Introducción a los Teoremas de Gödel , §32.3 en la primera edición, §42.3 en la nueva, turbo-cargada, pantalla retina, CPU mejorada, generalmente más extraña, segunda edición ...