TM variants and the Church-Turing thesis

Why it exists

The Turing machine of the previous page is one specific model. Many natural changes (more tapes, a head that may stay, guessing) look as if they should make it stronger. The theorems on this page say they do not change what can be computed, only how fast. That robustness is the reason the Turing machine is accepted as the definition of "computable", which is the content of the Church–Turing thesis. GATE asks which variants are equivalent in power, what the cost of a simulation is, and what the thesis states.

Prerequisites

You need the definition of a Turing machine, its configurations and the difference between recognising and deciding (Turing machines).

Precise definitions

Two models are equivalent if they accept (or decide, or compute) exactly the same languages (functions). The equivalences below are proved by simulation: a machine of the first kind is turned into one of the second kind that does the same job.

How it works

Several tapes

A $k$-tape machine has $k$ tapes with a head on each; one move reads the $k$ symbols under the heads, writes $k$ symbols, moves each head ($L$, $R$ or $S$) and changes state. The input is on tape 1. Example: a two-tape machine for $\{a^n b^n\}$ copies the $a$'s onto tape 2, then, for every $b$ on tape 1, erases one copied symbol on tape 2; it accepts when both tapes reach their blanks together. It makes $2n + 2$ moves on $a^n b^n$, whereas the one-tape machine of the previous page, which walks back and forth, makes $2n^2 + 2n + 1$:

Both machines decide the same language (checked on all strings up to length $10$). Simulation of $k$ tapes by one tape: write the contents of the tapes one after another separated by a marker $\#$, and mark the cell under each head with a dotted symbol (the alphabet is extended). One move of the $k$-tape machine becomes a sweep over the whole tape to read the marked symbols and a second sweep to update them; each sweep takes $O(t)$ steps if $t$ moves have been made, so $t$ moves cost $O(t^2)$ (quoted).

Nondeterminism

A nondeterministic Turing machine (NTM) has $\delta(q, a) \subseteq Q \times \Gamma \times \{L, R\}$: several moves may apply, and the machine accepts $w$ if some sequence of choices reaches the accepting state. Its computations form a tree. Example: the NTM that accepts the strings over $\{a, b\}$ whose third symbol from the end is $a$: on each $a$ it may guess "this is the symbol", then read two more symbols and look for the blank. The table follows all computations at once on an accepted and a rejected input:

Simulation by a deterministic machine: search the computation tree breadth first, keeping the list of all configurations after $0, 1, 2, \ldots$ moves, exactly as in the table; accept as soon as one of them is accepting. (Depth-first search would be wrong: an infinite branch could make it miss an accepting one.) If every configuration has at most $b$ successors, after $t$ moves there are at most $b^t$ configurations, which is the exponential cost; whether this exponential cost can be avoided is the P versus NP question. The two machines accept the same language: the simulation was checked against an explicit enumeration of all computation paths. A nondeterministic machine decides a language if all its computations halt; the simulation then halts on every input too.

Enumerators and dovetailing

An enumerator is a machine with a printer that, started on a blank tape, prints strings (possibly for ever); its language is the set of strings it prints. Enumerators and recognisers are equivalent. Given a recogniser $M$, build the enumerator by dovetailing: in stage $s$ run $M$ for $s - i$ moves on the $i$-th string (counting from $0$) of the list $\varepsilon, a, b, aa, ab, \ldots$ for every $i < s$, and print a string the first time $M$ accepts it. A string on which $M$ loops never blocks the others, and every string accepted after $m$ moves is printed in stage $i + \max(1, m)$:

Conversely, from an enumerator $E$ build a recogniser: run $E$ and accept $w$ if $E$ prints $w$.

Encoding machines and the universal machine

A machine can be written as a string $\langle M \rangle$ over a fixed alphabet: list the start and accepting states and all transitions. For the machine of the previous page that decides $a^n b^n$ the description begins start=q0;accept=qa;q0,Y>q3,Y,R;q0,_>qa,_,R;q0,a>q1,X,R;.... Decoding this string recovers the machine exactly (checked for six machines). A universal Turing machine $U$ takes $\langle M \rangle$ and $w$, and simulates $M$ on $w$: it accepts iff $M$ accepts $w$, loops iff $M$ loops. A program that decodes and simulates agrees with direct simulation on all strings up to length $8$ for four machines. $U$ is the model of a general-purpose computer; it is also the machine that recognises $A_{TM}$, the language of pairs $(\langle M \rangle, w)$ with $M$ accepting $w$, a language that is recognisable but not decidable (next pages).

The Church–Turing thesis

Everything that can be computed by an algorithm, in the intuitive sense, can be computed by a Turing machine.

It is a thesis, not a theorem, because "algorithm in the intuitive sense" is not a mathematical notion: it cannot be proved, only supported. The evidence: every proposed formal model of computation (the $\lambda$-calculus of Church, Turing machines, $\mu$-recursive functions of Gödel and Kleene, random-access machines, programming languages, two-stack machines) has turned out to compute the same functions, and no one has found an algorithm that a Turing machine cannot carry out. The strong (or extended) version claims that a Turing machine simulates every reasonable model with only a polynomial slowdown; it is more debatable (it is where quantum computers raise questions). Practical consequences: to show that a language is decidable one may describe an algorithm in plain language; to show it is undecidable one must show that no Turing machine, and by the thesis no algorithm, decides it.

Worked examples

Cheat box

Traps and GATE patterns

Connections

Recognising versus deciding becomes the central distinction of the next page (decidable and recognisable languages); the universal machine is the engine of the halting problem (undecidability); the strict gap between the first and second stack leads back to the Chomsky hierarchy (hierarchy).

PYQs

Which of the following pairs have DIFFERENT
expressive power?

Let A and B be finite alphabets and let # be a symbol
outside both A and B. Let f be a total function from A*
to B*. We say f is computable if there exists a Turing
machine M which given an input x  ∈  A*, always halts
with f(x) on its tape. Let Lf denote the language {x #
f(x)│x ∈ A* }. Which of the following statements is
true:

Self-check

Revision card

References