Turing machines

Why it exists

Finite automata have a fixed amount of memory and pushdown automata a stack that can be read only at the top. A Turing machine (TM) has a finite control and an unbounded tape that it can read, write and move along in both directions. It is the standard model of "what can be computed": everything a computer program can do, a Turing machine can do, and the languages it recognises are exactly the recursively enumerable languages (top of the Chomsky hierarchy). GATE asks: trace a given machine, say which language it accepts, count moves or tape cells, and decide whether it halts.

Prerequisites

You need finite control, configurations and acceptance from the automata pages; the Turing machine generalises the PDA by replacing the stack with a tape (PDA).

Precise definitions

A (deterministic) Turing machine is $M = (Q, \Sigma, \Gamma, \delta, q_0, q_{\text{acc}}, q_{\text{rej}})$:

• $Q$ finite set of states; $q_0$ the start state; $q_{\text{acc}}$ the accepting state; $q_{\text{rej}}$ the rejecting state ($q_{\text{acc}} \ne q_{\text{rej}}$);
• $\Sigma$ the input alphabet (no blank); $\Gamma \supseteq \Sigma$ the tape alphabet; a blank symbol $\sqcup \in \Gamma \setminus \Sigma$ (written _ in the animations);
• $\delta : (Q \setminus \{q_{\text{acc}}, q_{\text{rej}}\}) \times \Gamma \to Q \times \Gamma \times \{L, R\}$.

The tape is infinite in both directions and holds blanks except for the input, which starts at one cell with the head on its first symbol. One move: in state $q$ reading $a$, if $\delta(q, a) = (q', b, D)$ the machine writes $b$ over $a$, moves the head one cell left ($D = L$) or right ($D = R$) and enters $q'$. A missing transition means the machine halts and rejects (the convention of this site; many books add that explicit $q_{\text{rej}}$ transition).

A configuration records the state, the tape contents and the head position, usually written $u\,q\,v$: the tape is $uv$ (with blanks outside), the head is on the first symbol of $v$ and the state is $q$. A configuration yields the next one by one move.

On input $w$ exactly one of three things happens:

• the machine accepts (reaches $q_{\text{acc}}$ and halts),
• it rejects (reaches $q_{\text{rej}}$ or has no applicable move and halts),
• it loops (never halts).

The language recognised by $M$ is $L(M) = \{w : M \text{ accepts } w\}$. $M$ decides $L$ if it recognises $L$ and halts on every input. The difference between recognising and deciding is the difference between recursively enumerable and recursive languages (decidable and recognisable languages).

A TM can also compute a function: the machine halts and the answer is what is left on the tape.

How it works

Example 1: a decider for $a^n b^n$

Idea: mark one $a$ with $X$, move right to the first unmarked $b$ and mark it $Y$, return to the left end, repeat. When no $a$ is left, check that only $Y$'s remain.

States and moves ($q_a$ accepts):

• $q_0$: on $a$: write $X$, move right, go to $q_1$; on $Y$: go to $q_3$ (all $a$'s used up); on blank: accept (empty string).
• $q_1$ (looking for a $b$): on $a$ or $Y$: skip right; on $b$: write $Y$, move left, go to $q_2$.
• $q_2$ (going back): on $a$ or $Y$: skip left; on $X$: move right, go to $q_0$.
• $q_3$ (checking): on $Y$: skip right; on blank: accept.

Any other pair has no transition: the machine rejects. Run on $aabb$ (the head is the arrow above the tape, the shaded cell was just written, the outlined transition was used):

On $aab$ there is an $a$ left over: the head reaches the blank at the right end while still looking for a $b$ and the machine rejects:

Correctness: each round marks exactly one $a$ and one $b$, so the string is accepted iff the number of $a$'s equals the number of $b$'s and all $a$'s come before all $b$'s. (Checked on all strings over $\{a, b\}$ up to length $10$.) The machine halts on every input: it is a decider.

Example 2: a decider for $a^n b^n c^n$

The same idea with three symbols: in each round mark one $a$ ($X$), one $b$ ($Y$) and one $c$ ($Z$), return to the left end by passing over the marks, and repeat; when no $a$ is left check that only $Y$'s and $Z$'s remain. A Turing machine can do what no PDA can: it compares three blocks because it can go back and re-read.

Example 3: a machine that computes a function

Binary increment: go right to the end of the number, then turn trailing $1$'s into $0$'s going left until a $0$ (or the blank before the number) becomes $1$. On $1011$ it halts with $1100$ on the tape:

For all binary strings up to length $12$ the result is the binary successor of the number (the same number of digits, or one more after $1\ldots1$).

Example 4: a machine that loops

The recogniser that moves right over $a$'s, accepts when it sees $b$, and treats a blank like an $a$ (keeps moving right) accepts exactly the strings that contain a $b$. On a string with no $b$ it never halts: the head runs off to the right over blank cells, and each step looks like the previous one except for the head position. After $14$ moves the animation stops without a verdict:

This machine recognises the language "contains $b$" without deciding it. (A decider for it is easy to build: reject on the blank; but the animation shows why recognising is a weaker property.)

How many moves

The number of moves is the running time of the machine. For the three machines above:

The machine for $a^n b^n$ makes $2n^2 + 2n + 1$ moves on $a^n b^n$, the one for $a^n b^n c^n$ makes $4n^2 + 3n + 1$ moves, and the increment machine makes $2n + 2$ moves on $1^n$ (formulas fitted to simulations and confirmed for $n$ up to $40$). The quadratic growth is typical of one-tape machines that go back and forth: each of the $n$ rounds walks over a string of length about $2n$. (Faster machines exist for this language; the formula describes THIS machine.)

Conventions that differ between books

• Tape: two-way infinite (this site, Hopcroft et al.) or infinite to the right only with the head unable to move left from the first cell (Sipser). They are equivalent in power.
• Halting: one accepting state and one rejecting state (Sipser, this site) or a set of final states with the machine halting when no move applies (Hopcroft et al.).
• Blank and marks: names of symbols differ; the work-alphabet marks $X, Y, Z$ are only a habit.
• Moves: some books allow the head to stay in place ($S$) as well as move left and right; they are equivalent (a stay is a right move followed by a left move through an extra state).

Worked examples

Cheat box

Traps and GATE patterns

Connections

The Turing machine is the top of the Chomsky hierarchy (hierarchy); its variants (several tapes, nondeterminism) and the Church–Turing thesis are next (TM variants); recognising versus deciding leads to undecidability (decidable and recognisable languages).

PYQs

Self-check

Revision card

References