Turing Machines
A general model of algorithms and computability
The story so far
Each model studied so far recognizes a corresponding class of languages:
- finite automata recognize the regular languages;
- pushdown automata recognize the context-free languages; and
- every regular language is context-free.
These models deliberately restrict memory. A finite automaton has only fixed finite state, while a pushdown automaton has one last-in, first-out stack. Consequently, neither captures every algorithm we can describe.
The next question is broader:
Which languages can be recognized by any mechanical computing process?
This moves us from formal-language classification to computability theory.
Computability, decidability, and complexity
Three levels of questions should be kept separate.
Computability
Can a mechanical procedure perform the task at all?
Decidability
Can a mechanical procedure always terminate with a correct yes-or-no answer?
Complexity
Among decidable problems, which can be solved with a reasonable amount of time or memory?
The progression is therefore
\[ \text{computability}\longrightarrow\text{decidability}\longrightarrow\text{complexity}. \]
Complexity classes such as \(P\) and \(NP\) concern resource usage only after we know that the underlying problems are decidable.
Why another machine model?
Try sketching algorithms for these languages:
- palindromes;
- \(\{w\#w:w\in\{a,b\}^*\}\);
- \(\{ww:w\in\{a,b\}^*\}\); and
- \(\{a^nb^nc^n:n\ge0\}\).
A human can solve them on paper by marking symbols, revisiting earlier positions, and using the page as working memory. Alan Turing’s idea was to model these primitive actions directly.
The result is not intended to imitate modern computer hardware. It is a minimal mathematical model of an algorithmic process.
The Turing-machine model
A Turing machine consists of:
- a finite-state controller;
- an unbounded tape divided into cells;
- a read/write head positioned over one cell; and
- a transition function that determines each primitive step.
At each step, the machine:
- reads the symbol under the head;
- uses its current state and that symbol to choose a transition;
- writes a symbol in the current cell;
- moves the head one cell left or right; and
- enters a new state.
The tape is treated as unbounded. At every finite moment, however, the machine has visited only finitely many cells.
Formal definition
A deterministic Turing machine is a seven-tuple
\[ M=(Q,\Sigma,\Gamma,\delta,q_0,q_{\mathrm{accept}},q_{\mathrm{reject}}), \]
where:
- \(Q\) is a finite set of states;
- \(\Sigma\) is the input alphabet, not containing the blank symbol \(\sqcup\);
- \(\Gamma\) is the tape alphabet, where \(\Sigma\subseteq\Gamma\) and \(\sqcup\in\Gamma\);
- \(\delta\) is the transition function;
- \(q_0\in Q\) is the start state;
- \(q_{\mathrm{accept}}\in Q\) is the accepting state;
- \(q_{\mathrm{reject}}\in Q\) is the rejecting state; and
- \(q_{\mathrm{accept}}\ne q_{\mathrm{reject}}\).
The transition function is
\[ \delta: Q\times\Gamma \rightarrow Q\times\Gamma\times\{L,R\}. \]
If
\[ \delta(q,a)=(r,b,R), \]
the machine in state \(q\) reading \(a\) writes \(b\), moves right, and enters state \(r\).
The transition function is not applied after the machine enters either halting state.
Equivalent definitions may permit the head to stay in place, use a tape infinite in both directions, or handle the left boundary differently. These choices do not change which languages the model can recognize.
Configurations
A configuration is a complete snapshot of a Turing machine’s computation. It records:
- the relevant tape contents;
- the head position; and
- the current state.
Write a configuration as
\[ u q v, \]
where \(u,v\in\Gamma^*\):
- \(u\) is the tape content to the left of the head;
- \(q\) is the current state; and
- the first symbol of \(v\) is under the head.
If \(v=\varepsilon\), the head is understood to scan a blank.
For input \(w\in\Sigma^*\), the initial configuration is
\[ q_0w, \]
with blanks in the unshown cells.
The computation relation
Rather than treating an entire computation as one application of \(\delta\), it is usually clearer to distinguish:
- \(C\vdash C'\): configuration \(C\) yields \(C'\) in one step;
- \(C\vdash^*C'\): configuration \(C\) yields \(C'\) after zero or more steps.
Suppose
\[ \delta(q,b)=(r,c,R). \]
Then
\[ uaqbv\vdash uacrv. \]
The machine writes \(c\), moves right, and changes from \(q\) to \(r\).
If
\[ \delta(q,b)=(r,c,L), \]
then, away from the left boundary,
\[ uaqbv\vdash u r a c v. \]
The precise boundary convention depends on the chosen TM definition.
Accepting and rejecting
A Turing machine accepts input \(w\) if
\[ q_0w\vdash^*u q_{\mathrm{accept}}v \]
for some \(u,v\in\Gamma^*\).
It rejects \(w\) if
\[ q_0w\vdash^*u q_{\mathrm{reject}}v. \]
The strings \(u\) and \(v\) may be regarded as the final tape contents surrounding the head.
Unlike a DFA, a Turing machine is not guaranteed to halt. A computation has three possible outcomes:
- Accept: it eventually enters \(q_{\mathrm{accept}}\).
- Reject: it eventually enters \(q_{\mathrm{reject}}\).
- Loop: it runs forever without entering either halting state.
The third possibility will become crucial when we distinguish recognition from decision.
Drawing Turing machines
Turing-machine state diagrams resemble finite-automaton diagrams, but an edge label must specify what happens to the tape.
For example,
0 → 1, Rmeans “read 0, write 1, and move right.” Formally,
\[ \delta(q_0,0)=(q_1,1,R). \]
Similarly,
0 → 0, Lmeans
\[ \delta(q_0,0)=(q_1,0,L). \]
Tracing a machine
To determine what a machine does on an input:
- write the initial configuration;
- locate the transition matching the current state and scanned symbol;
- update the tape, state, and head position;
- write the resulting configuration; and
- continue until the machine accepts, rejects, or a nonterminating pattern is established.
Be careful: recognizing the purpose of a diagram by inspection can be misleading. Configuration-by-configuration tracing exposes overwrites, boundary behavior, and loops.
Turing-machine design strategies
Large Turing machines are rarely designed by drawing every state immediately. Begin with a high-level algorithm and refine it into tape operations.
Useful patterns include:
- marking: replace a processed symbol with a marked tape symbol;
- sweeping: move left or right until a delimiter, blank, or marked symbol is found;
- matching: mark a symbol in one region, find its required partner, and return;
- shifting: move a block of tape symbols to create or remove space;
- multiple passes: repeatedly scan the input while maintaining progress marks; and
- subroutines: describe reusable operations before translating them into states.
Example algorithms
Palindromes
Repeatedly:
- mark the leftmost unmarked symbol;
- sweep right to the last unmarked symbol;
- verify that it matches and mark it;
- return to the left; and
- accept when no unmarked symbols remain.
\(\{w\#w:w\in\{a,b\}^*\}\)
Repeatedly mark the leftmost unprocessed symbol before #, move across the separator, and match it with the leftmost unprocessed symbol after #. Reject on a mismatch or unequal lengths.
\(\{a^nb^nc^n:n\ge0\}\)
Repeatedly mark one a, then one corresponding b, then one corresponding c. Return to the left and repeat. Accept when all three blocks are exhausted together; reject if a required symbol is missing or the block order is invalid.
\(\{ww:w\in\{a,b\}^*\}\)
This is more difficult because there is no separator identifying the midpoint, and the second copy appears in the same order rather than in reverse. A one-tape TM can still decide it by determining whether the length is even, locating the midpoint through repeated marking, and comparing corresponding positions using additional tape symbols and sweeps.
The difficulty of designing the machine affects convenience and running time, not computability.
Computing functions
Turing machines can compute outputs, not only decide languages.
A TM \(T\) computes a partial function
\[ f:\Sigma^*\rightharpoonup\Gamma^* \]
if, whenever \(f(x)\) is defined, \(T\) started on \(x\) halts with \(f(x)\) encoded on its tape.
Examples include:
- addition;
- parity or \(n\bmod2\);
- integer division by two; and
- functions of several encoded arguments.
If the machine is required to halt on every valid input, it computes a total function.
Recognizing versus deciding
A language \(L\) is Turing-recognizable if some TM \(M\) satisfies:
- if \(w\in L\), then \(M\) eventually accepts \(w\);
- if \(w\notin L\), then \(M\) may reject or run forever.
A language \(L\) is Turing-decidable if some TM \(M\) satisfies:
- if \(w\in L\), then \(M\) eventually accepts \(w\);
- if \(w\notin L\), then \(M\) eventually rejects \(w\).
The essential distinction is termination:
A decider halts on every input. A recognizer is required to halt only on members of its language.
| Input | Recognizer for \(L\) | Decider for \(L\) |
|---|---|---|
| \(w\in L\) | Must accept eventually | Must accept eventually |
| \(w\notin L\) | May reject or loop | Must reject eventually |
Every decidable language is recognizable:
\[ \mathrm{DECIDABLE}\subseteq\mathrm{RECOGNIZABLE}. \]
We will later show that the inclusion is proper and that some languages are not even recognizable.
Why nontermination changes the question
Suppose a recognizer has been running for a long time without accepting. We cannot generally infer that the input is not in the language:
- perhaps the machine will reject later;
- perhaps it will accept later; or
- perhaps it will run forever.
For a decider, halting guarantees that waiting eventually produces an answer. This difference underlies undecidability: some problems can be recognized positively but cannot always be resolved negatively by any terminating algorithm.
The Church–Turing thesis
The Church–Turing thesis states:
Every effectively computable procedure can be carried out by a Turing machine.
Equivalent formulations include:
- every mechanical computation can be simulated by a TM;
- every algorithm corresponds to some TM; and
- if no TM decides a problem, no algorithm decides it.
This is called a thesis, not a theorem, because “effective procedure” or “algorithm” is an informal concept. A mathematical theorem cannot prove that a formal model equals an informal notion without first defining that notion formally.
Its force comes from converging evidence: many independently proposed models of computation have turned out to have the same computational power.
Robustness of the model
Many variations of Turing machines have exactly the same computational power:
- a tape infinite in both directions;
- several tapes and several heads;
- nondeterministic transition choices;
- a two-dimensional tape; and
- other finite changes to the machine architecture.
These variants may make algorithms easier to describe or improve their efficiency, but they do not change which languages are recognizable or decidable.
Other formalisms equivalent in computability include:
- Church’s lambda calculus;
- unrestricted grammars;
- register and RAM-machine models; and
- general-purpose programming languages, assuming unbounded memory.
Claims about physical or biological computation—DNA systems, quantum computers, or the human brain—require care. Quantum computation may change efficiency dramatically, but standard quantum models do not compute non-Turing-computable functions. Whether every process in nature is captured by the Church–Turing framework is a broader scientific and philosophical question.
Why such a simple machine is enough
A Turing machine has only primitive operations: read, write, move one cell, and change state. Yet complex algorithms are built by composing these operations, just as machine-language instructions implement high-level programs.
The model’s simplicity is a strength:
- it is precise enough for proofs;
- it exposes the minimum resources required for general computation;
- it is independent of any programming language or hardware architecture; and
- limits proved for Turing machines apply to every ordinary algorithmic system under the Church–Turing thesis.
Check your understanding
- What capability does a Turing machine add beyond a pushdown automaton?
- What information is contained in a configuration \(u q v\)?
- Why are \(q_{\mathrm{accept}}\) and \(q_{\mathrm{reject}}\) not ordinary states with outgoing transitions?
- What are the three possible outcomes of running a TM on an input?
- How does a marking algorithm compensate for the absence of variables and arrays?
- What is the exact difference between recognizing and deciding a language?
- Why is the Church–Turing thesis not a mathematical theorem?
- Why does adding a second tape change efficiency but not computability?