Math 2.0

Mathematical logic and foundations Theorem

Equivalence of Turing machines and partial recursive functions

Builds on Turing machineGeneral recursive function

Statement

Let k≥1k \ge 1 and let f ⁣:ℕk⇀ℕf \colon \N^k \rightharpoonup \N be a partial function. Code a tuple (x1,…,xk)(x_1, \dots, x_k) as the input string 1x101x20⋯01xk1^{x_1} 0 1^{x_2} 0 \cdots 0 1^{x_k}, and code an output yy as the string 1y1^y. Then the following are equivalent.

  1. The function ff is partial recursive.
  2. There is a Turing machine MM with the following property for every x∈ℕkx \in \N^k: MM halts on the code of xx exactly when f(x)f(x) is defined. In that case MM halts with the code of f(x)f(x) on its tape.

Remarks

From recursive functions to machines: one builds machines for the zero, successor and projection functions, and shows that Turing-computable functions are closed under composition, primitive recursion and minimisation. Minimisation is a loop that tests y=0,1,2,…y = 0, 1, 2, \dots in turn and stops at the first zero. From machines to recursive functions: configurations are coded as numbers, and the step function on codes is primitive recursive. Then f(x)f(x) is obtained by searching with μ\mu for the first halting time and decoding the output, as in Kleene's T predicate. In particular, every partial recursive function is obtained with at most one use of minimisation. The theorem is part of the evidence for the Church–Turing thesis, but it is a theorem about two formal models, while the thesis is not a formal statement. The choice of unary coding is not essential: any of the usual codings, such as binary numerals, gives the same class of functions.

Going deeper

For a student

The theorem lets one move freely between programs and recursive definitions. To show that a function is computable, it is often easier to write a recursive definition than to design a machine. To show that a set is undecidable, one argues with machines, for example with the halting problem, and then transfers the result to recursive functions. The same method of coding configurations by numbers shows that register machines and the lambda calculus define the same class.

Reading path

To understand this page from the ground up, read these 7 pages in order. The foundations come first.

Show the path as a graph
Function, concept, no evidence levelFunctionconceptNatural numbers, object, no evidence levelNatural numbersobjectPrimitive recursive function, concept, no evidence levelPrimitive recursive f…conceptSet, concept, no evidence levelSetconceptGeneral recursive function, definition, no evidence levelGeneral recursive fun…definitionTuring machine, definition, no evidence levelTuring machinedefinitionEquivalence of Turing machines and partial recursive functions, statement, no evidence levelEquivalence of Turing…statement
Each page uses the pages above it. The colour of the bar on a box shows how strong the evidence is, and the box also gives it as text. The list has the same pages.
  • no evidence level
  1. Function concept
  2. Natural numbers object
  3. Primitive recursive function concept
  4. Set concept
  5. General recursive function definition
  6. Turing machine definition
  7. Equivalence of Turing machines and partial recursive functions statement

Further reading

  1. Web https://en.wikipedia.org/wiki/Church–Turing_thesis
About this page
TagQ7CB3ET9P8
URIm2://Q7CB3ET9P8
Kindstatement, theorem
WritingW0 stub
MSC03D10, 03D20, 68Q04
StatusThis copy of the site has no build data. Run m2 status Q7CB3ET9P8.
AboutTuring machine, General recursive function
UsesTuring machine, General recursive function
Changed3 November 2026

Markdown · JSON · Edit on GitHub

What this page needs for W1

  • an inventory row: the row of the inventory that the node accounts for (0 of 1)
  • a source with a locator (0 of 1)

The writing levels say how complete the text of a page is. They do not measure its truth.

What links here

No page links to this page yet.