4
$\begingroup$

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!

$\endgroup$
  • $\begingroup$ There must be some confusion here, the set of primitive recursive functions is already closed under composition and (quite naturally) primitive recursion. Also not all total recursive functions are primitive recursive, so you need to drop the "primitive", or modify your statement in some other way. $\endgroup$ – Marc van Leeuwen Jun 19 '13 at 7:00
2
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ The definition of your set $B_n$ wasn't displaying correctly (for me, at least). As such I've made some formatting alterations (and hopefully zero content alterations). $\endgroup$ – user642796 Jun 20 '13 at 9:13
1
$\begingroup$

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 ...

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.