Skip to content
Tutorials Center
My learning

Topics

Lesson 33 of 59 · Turing Machines

Variants of Turing Machines and the Church-Turing Thesis

Multi-tape, nondeterministic and other Turing machine variants all have the same power. Simulate them in Python, then meet the Church-Turing thesis and universal TMs.

The Turing machine of the previous lesson is a bare-bones model. It is natural to ask whether adding features makes it stronger: more tapes, several heads, a tape infinite in both directions, nondeterministic choices. The remarkable answer is no. Every reasonable variant recognizes exactly the same languages. What changes between variants is only the speed. This robustness is the first piece of evidence that the Turing machine captures a natural notion of computation, which leads to the Church–Turing thesis.

Variants that add no power

Stay move Head may stay put as well as move.
Two-way tape Infinite in both directions.
Multi-tape k tapes, each with its own head.
Nondeterministic Several choices; accept if one works.

All of them recognize exactly the recursively enumerable languages.

1 / 2

Multi-tape Turing machines

A k-tape machine has k tapes, each with its own head. The input starts on tape 1; the other tapes are blank. A transition looks at the k symbols under the heads and writes k symbols and moves all heads (each independently):

δ(q, a1, …, ak) = (p, b1, …, bk, D1, …, Dk)

Extra tapes are convenient scratch paper. For 0^n 1^n a second tape lets the machine copy the zeros and then walk back along the copy while reading the ones, with no marking and no sweeping back and forth.

Theorem. Every multi-tape TM can be simulated by a single-tape TM. A computation of t steps on the multi-tape machine takes O(t²) steps on the single-tape machine.

The simulation writes the contents of all k tapes one after another on one tape, separated by #, with a marker ^ for each head position. Each simulated step is one sweep over the whole tape, costing O(t) time. The quadratic slowdown is real: single-tape machines need Ω(n²) steps for palindromes, while two tapes do it in O(n).

The simulator below works for any number of tapes. Rules are written with Python tuples. The machine accepts 0^n 1^n in a linear number of steps, versus the quadratic count seen on one tape.

Python A two-tape machine for 0^n 1^n

Press Run (or Ctrl + Enter) to see the result here.

Program input · what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The step counts are about 2n + 2, so doubling n doubles the time. The one-tape version needed 4n²-ish steps.

Other tape variants

  • Two-way infinite tape. Fold the tape in the middle into two tracks; the head switches tracks when it crosses the fold. Same power.
  • Multi-track tape. Each cell holds a tuple of symbols; this is just a larger tape alphabet.
  • Several heads on one tape. Equivalent to multi-tape.
  • Two-dimensional tape. A grid can be linearized row by row. Same power, polynomially slower.
  • Stay-in-place move. Replace S by two moves (R then L). Same power.

Nondeterministic Turing machines

In a nondeterministic TM (NTM), δ(q, a) is a set of possible moves. The machine accepts if some sequence of choices reaches q_accept. This is not about randomness or about being lucky: it asks whether a successful branch exists.

An NTM is easy to design for "guess and check" languages. Take L = { w ∈ {0,1}* : the third symbol from the right is 1 }. The machine scans right; at each 1 it may guess that this is the third-from-last symbol and then verify by counting two more symbols and the end of the input.

Theorem. Every NTM can be simulated by a deterministic TM.

The deterministic machine explores the computation tree breadth-first: it keeps the set of all configurations reachable after 0, 1, 2, … steps. If an accepting configuration ever appears, accept. Breadth-first search matters: a depth-first search could follow an infinite branch and never find the accepting one. The price is time: a tree of depth t with branching b has up to b^t configurations, so the deterministic simulation takes exponential time. Whether this exponential cost is unavoidable is the P vs NP question.

Python Breadth-first simulation of an NTM

Press Run (or Ctrl + Enter) to see the result here.

Program input · what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The list widths shows how many configurations the breadth-first search keeps alive at each step. Here the guesses die quickly, so the width stays small; for harder languages it can grow exponentially.

Deciders and nondeterminism

An NTM is a decider if every branch halts on every input. A deterministic simulation of an NTM decider also halts. Nondeterminism changes the efficiency of recognition but never which languages are recognizable or decidable.

The Church–Turing thesis

In the 1930s several people independently proposed formal definitions of "effectively computable":

  • Alan Turing: Turing machines;
  • Alonzo Church: the lambda calculus;
  • Kurt Gödel and Stephen Kleene: general recursive functions;
  • Emil Post: production systems.

All of these were proved to define exactly the same class of functions. Later models (register machines, counter machines, modern programming languages, quantum computers when only computability is considered) joined the list without enlarging it.

Church–Turing thesis. Every function that can be computed by any effective, step-by-step procedure can be computed by a Turing machine.

The thesis is not a theorem: "effective procedure" is an informal notion, so it cannot be proved mathematically. It is an empirical claim that has survived ninety years of attempts to refute it. Its practical value is huge: to show that a problem is solvable, you may describe an algorithm in plain English or pseudocode, confident that a Turing machine could do it. To show that a problem is unsolvable by any algorithm, it is enough to show that no Turing machine solves it.

The extended Church–Turing thesis adds that any reasonable model can be simulated by a Turing machine with only polynomial overhead. Quantum computers are believed to challenge this extended version (they may solve some problems exponentially faster) but not the original thesis about what is computable.

Universal Turing machines

A Turing machine as defined has a fixed program. Turing's other great idea was the universal Turing machine (UTM): one machine U that takes as input the description ⟨M⟩ of any machine M plus an input w, and simulates M on w. It accepts if M accepts, rejects if M rejects, and loops if M loops.

You have already used one. The Python function tm(rules, tape) takes a machine described as data (the rule text) and runs it. A UTM is the same program written as a Turing machine. It is the theoretical ancestor of the stored-program computer, the interpreter and the virtual machine. It also powers the diagonal argument in the halting problem.

Check your understanding

Quick check · 4 questions

of 4 answered You scored / 4 · perfect!

  1. 1. How does the power of a multi-tape Turing machine compare with a single-tape machine?

    A single-tape machine simulates a multi-tape one with a quadratic slowdown; the class of languages is unchanged.
  2. 2. Why does the deterministic simulation of an NTM use breadth-first search?

    Breadth-first search explores all branches level by level, so any accepting configuration at finite depth is found.
  3. 3. What is the Church-Turing thesis?

    It is a thesis, not a theorem, because 'effectively computable' is an informal notion.
  4. 4. What does a universal Turing machine do?

    A UTM interprets a machine description, the idea behind stored-program computers.

Summary

  • Multi-track, multi-tape, two-way-tape and multi-head variants all recognize exactly the same languages as the basic Turing machine.
  • Multi-tape machines can be simulated by a single tape with a quadratic slowdown.
  • Nondeterministic TMs are simulated by breadth-first search over configurations, with exponential slowdown.
  • The Church–Turing thesis states that Turing machines capture everything effectively computable.
  • A universal Turing machine runs any machine given as data.

Next: Turing machines for arithmetic