How do we know that every halting Turing Machine can be expressed as a recursive function?

Question

I've hear many times that a major result in Recursion Theory is the equivalence of Turing and Godel's models: the functions implementable on a Turing machine are precisely the functions that can be built from the primitive recursive functions via composition and primitive recursion.

I am interested in the proof in the direction Turing $\to$ Godel. How do we take a Turing machine and come up with a recursive definition of a function that is equivalent to the language decided by the Turing machine?

An explanation or a pointer to the paper(s) that prove this result would be much appreciated. Thanks!

Answer 1

You can find the proof in every mathematical book on recursion theory. The argument is roughly as follows:

1. If $f : \mathbb{N} \to \mathbb{N}$ and the graph $\Gamma_f$ of $f$ is recursively enumerable then $f$ is recursive.

2. For every Turing Machine there is a unique Gödel number, which encodes the machine.

3. If $f$ is Turing then the graph is recursively enumerable. This is proofed by saying \begin{equation} (x,y) \in \Gamma_f \Leftrightarrow \exists s \in B_n(e,x_1,\ldots,x_n,y,s) \end{equation} where $B_n$ is the set of all $(e,x_1,\ldots,x_n,y,s) \in \mathbb{N}^{n+3}$ such that

   • $e$ is the Gödel number of the Machine $M$, $s$ is the Gödel number of the calculation of the machine $M$, the machine $M$ does $x_1,\ldots,x_n \to y$

   which is a primitive recursive set.

4. The claim follows from 1 and 3.

If you want more information for any of these steps, let me know.

EDIT: as Marc van Leeuwen pointed out in the comment above, this proves that Turing functions are recursive. The set of Turing functions is not the same as the set of primitive recursive functions.

Answer 2

As @mjb says, this is an absolutely standard bookword result (at least when corrected by dropping "primitive").

You ask for pointers to the literature. For a proof-sketch slightly amplifying that @mjb gives, you could try my Introduction to Gödel's Theorems, §32.3 in the first edition, §42.3 in the new, turbo-charged, retina-screen, improved CPU, generally whizzier, second edition ...