Structure of a Turing Machine
In 1936, Alan Turing introduced a deceptively simple abstract machine that would become the foundation of all theoretical computer science. Unlike finite automata or pushdown automata, a Turing machine (TM) has unlimited memory in the form of an infinite tape, and a read/write head that can move in either direction. This gives it the full power needed to simulate any algorithmic process.
A Turing machine is a 7-tuple M = (Q, Σ, Γ, δ, q₀, q_accept, q_reject) where Q is the set of states; Σ is the input alphabet (not containing the blank symbol ⊔); Γ ⊇ Σ is the tape alphabet (includes ⊔); δ: Q × Γ → Q × Γ × {L, R} is the transition function; q₀ is the start state; q_accept is the unique accepting state; and q_reject is the unique rejecting state (q_accept ≠ q_reject).
At each step, the TM reads the symbol under the head, writes a (possibly different) symbol, moves the head left or right, and transitions to a new state. Computation halts when the machine enters q_accept or q_reject. Crucially, the machine may also loop — running forever without halting.
Image: Source
How a Turing Machine Operates
The tape is divided into cells, each holding one symbol from Γ. Initially the input string occupies the leftmost cells; all other cells contain the blank symbol ⊔. The head starts at the leftmost input symbol. The transition function δ(q, a) = (q', b, D) means: in state q reading symbol a, write b, move in direction D ∈ {L, R}, and transition to q'. A configuration of the TM records its current state, tape contents, and head position — the "snapshot" of the computation at any moment.
- Strategy: Repeatedly cross off one 'a' and one 'b' by replacing them with a marker symbol 'X'.
- Scan right past X's; replace the first 'a' with X; scan right past a's and X's; replace the first 'b' with X.
- Return to the left end and repeat.
- Accept if all a's and b's are crossed off simultaneously; reject if the counts differ.
- This language is not regular and not deterministic context-free, but a TM decides it easily.
The Church-Turing Thesis
The Church-Turing thesis is not a theorem that can be formally proved, but a fundamental claim about the nature of computation. It states that the intuitive notion of "effective computation" or "algorithm" is precisely captured by Turing machines.
Every function that can be computed by any physically realisable computational device — or by any algorithm that a human could in principle carry out — can also be computed by a Turing machine. Equivalently, Turing-computable functions are exactly the effectively computable functions.
The thesis is supported by the convergence of many independent formalisms proposed in the 1930s: Turing's machines, Alonzo Church's lambda calculus, Emil Post's production systems, and Stephen Kleene's recursive functions all turned out to define exactly the same class of computable functions. No model of computation proposed since has exceeded this boundary.
Image: Source
Implications for Computation
The Church-Turing thesis has profound consequences. It means that questions about what computers can do — in principle, ignoring time and memory constraints — can be answered by studying Turing machines. If a problem cannot be solved by any Turing machine, it cannot be solved by any computer, any program, or any algorithm, no matter how clever.
Decidable Languages and Turing-Recognisable Languages
A language L is Turing-decidable (or just decidable) if there is a TM that always halts — accepting strings in L and rejecting strings not in L. A language is Turing-recognisable if some TM accepts every string in L, but may loop on strings outside L.
- Decidable: All regular and context-free languages; the language of valid arithmetic expressions; primality testing.
- Recognisable but not decidable: The Halting Problem — a TM can recognise when another TM halts, but cannot always detect an infinite loop.
- Not even recognisable: The complement of the Halting Problem — no TM can systematically recognise all inputs on which a given TM fails to halt.
The distinction between decidable and merely recognisable languages is one of the deepest in the theory — it marks the boundary between what computers can fully solve and what they can only partially explore. Turing machines give us the precise language to reason about this boundary.