Computability Theory and Turing Machines

⚡ Key Takeaways

Computability theory studies which problems can in principle be solved by mechanical procedures. The central model is the Turing machine, an idealized computer with unlimited memory; the Church–Turing thesis asserts it captures every notion of "effective computation." Key result in words: there exist precisely defined problems (like the halting problem) that NO algorithm can solve. Applies across logic, computer science, and the foundations of mathematics. Pioneered by Alan Turing, Alonzo Church, Kurt Gödel, and Emil Post in 1936.

💡 The Core Insight

A computation is a finite, mechanical, rule-following process. Once you fix any reasonable formalization of this idea, you get the same class of computable functions. This robustness is what gives the concept its weight: "computable" is not an artifact of one machine design but a fundamental mathematical category. And because programs are finite strings, they can be counted and encoded as numbers — which lets a machine take other machines as input, and lets us run diagonalization to manufacture problems no machine can decide.

DefinitionTuring Machine

A (deterministic, one-tape) Turing machine is a 7-tuple

1

\quad M = (Q,\ \Sigma,\ \Gamma,\ \delta,\ q_0,\ q_{\text{accept}},\ q_{\text{reject}})

Derivation hint: this is a definition, not derived — each component names one physical part of the abstract device. where the symbols mean:

$Q$ — a finite set of states (the controller's internal configurations).
$\Sigma$ — the input alphabet, not containing the blank symbol.
$\Gamma$ — the tape alphabet, with $\Sigma \subseteq \Gamma$ and blank $\sqcup \in \Gamma$ .
$\delta : Q \times \Gamma \to Q \times \Gamma \times \{L, R\}$ — the transition function.
$q_0 \in Q$ — the start state.
$q_{\text{accept}}, q_{\text{reject}} \in Q$ — the halting states ( $q_{\text{accept}} \neq q_{\text{reject}}$ ).

The transition function reads

2

\quad \delta(q, a) = (q',\ b,\ D),\qquad D \in \{L, R\}

Derivation hint: from current state $q$ reading symbol $a$ , the machine moves to state $q'$ , overwrites $a$ with $b$ , and shifts the head one cell in direction $D$ . A configuration is a snapshot $(q, w, i)$ giving the current state, full tape contents, and head position. The machine halts if it ever enters $q_{\text{accept}}$ or $q_{\text{reject}}$ ; otherwise it runs forever.

DefinitionDecidable and Recognizable Languages

Let $L \subseteq \Sigma^*$ be a language (set of strings).

$L$ is Turing-recognizable (recursively enumerable, r.e.) if some TM $M$ accepts exactly the strings in $L$ , and on strings not in $L$ either rejects or loops.
$L$ is decidable (recursive) if some TM accepts every string in $L$ and rejects every string not in $L$ — i.e. it always halts.

A function $f : \mathbb{N} \to \mathbb{N}$ is computable if some TM, started with $n$ encoded on its tape, halts with $f(n)$ encoded on its tape.

TheoremChurch–Turing Thesis

Every function that is "effectively calculable" by any mechanical procedure is computable by a Turing machine. Formally, the following classes coincide:

3

\quad \text{TM-computable} = \lambda\text{-definable} = \mu\text{-recursive} = \text{register-machine-computable}

Derivation hint: each equality is a separate constructive theorem (e.g. Kleene's proof that $\lambda$ -definable $=$ $\mu$ -recursive); the thesis itself is the empirical claim that this common class equals the informal notion of "algorithm." The thesis is not a theorem — "effectively calculable" is informal — but it is supported by the convergence of every independent formalization onto the same class.

TheoremUndecidability of the Halting Problem

Let

4

\quad \mathrm{HALT} = \{\,\langle M, w\rangle : M \text{ is a TM that halts on input } w\,\}.

Derivation hint: $\langle M, w\rangle$ is a single string encoding both the machine's description and its input via a fixed Gödel encoding. Then $\mathrm{HALT}$ is Turing-recognizable but not decidable: no Turing machine decides, for all $\langle M, w\rangle$ , whether $M$ halts on $w$ .

ProofHalting Problem is Undecidable — Diagonalization

1. Assume for contradiction a decider $H$ exists with

5

\quad H(\langle M, w\rangle) = \begin{cases} \text{accept} & \text{if } M \text{ halts on } w,\\ \text{reject} & \text{if } M \text{ loops on } w.\end{cases}

Derivation hint: this is exactly the negation of " $\mathrm{HALT}$ is undecidable"; $H$ always halts by assumption. 2. Build a new machine $D$ that takes a single machine description $\langle M\rangle$ as input and runs $H$ on $\langle M, \langle M\rangle\rangle$ — i.e. asks "does $M$ halt when fed its own description?" 3. Invert the answer: $D$ is defined so that

6

\quad D(\langle M\rangle) = \begin{cases} \text{loop forever} & \text{if } H(\langle M,\langle M\rangle\rangle)=\text{accept},\\ \text{halt} & \text{if } H(\langle M,\langle M\rangle\rangle)=\text{reject}.\end{cases}

Derivation hint: $D$ does the opposite of what $M$ does on its own code — this is the diagonal flip. 4. Feed $D$ its own description. Consider $D(\langle D\rangle)$ . By the definition of $D$ :

If $D$ halts on $\langle D\rangle$ , then $H$ said "halt," so by step 3 $D$ loops — contradiction.
If $D$ loops on $\langle D\rangle$ , then $H$ said "loop," so by step 3 $D$ halts — contradiction.

5. Conclusion: both cases are impossible, so $H$ cannot exist. Hence $\mathrm{HALT}$ is undecidable. $\blacksquare$ (That $\mathrm{HALT}$ is recognizable: simply simulate $M$ on $w$ ; accept if it halts. This may loop, but it never wrongly rejects.)

∎

ProofMost Functions Are Uncomputable — Counting

1. Every Turing machine has a finite description, encodable as a finite binary string. So the set of TMs is at most countable:

7

\quad |\{\text{Turing machines}\}| \le |\Sigma^*| = \aleph_0.

Derivation hint: finite strings over a finite alphabet form a countable union of finite sets. 2. The set of all functions $\mathbb{N} \to \{0,1\}$ has cardinality

8

\quad |\{0,1\}^{\mathbb{N}}| = 2^{\aleph_0} = \mathfrak{c}.

Derivation hint: Cantor's theorem — the power set of $\mathbb{N}$ is strictly larger than $\mathbb{N}$ . 3. Since there are only countably many machines but uncountably many functions, almost all functions are uncomputable. $\blacksquare$

∎

mathematician · Alan Turing | 1912–1954

British mathematician who, at age 23, defined the abstract machine now bearing his name in the 1936 paper "On Computable Numbers, with an Application to the Entscheidungsproblem." He introduced the universal machine, the halting argument, and the very idea of a stored-program computer years before electronic hardware existed. During WWII he led codebreaking at Bletchley Park against the German Enigma, work credited with shortening the war. His later interests included morphogenesis and machine intelligence (the "Turing test"). Persecuted for his homosexuality, he died in 1954; he received a posthumous royal pardon in 2013.

🧠 Intuition

Picture a clerk with an infinitely long roll of squared paper, a pencil, and an eraser. The clerk follows a small fixed rulebook (the transition function): "in mood $q$ seeing symbol $a$ , write $b$ , change to mood $q'$ , step left/right." That's all a computer ever does — there is no hidden magic. The astonishing claim of computability theory is that this clerk can do anything any computer can do, just more slowly. The limits then become visceral. A program is itself just symbols on paper, so the clerk can read another clerk's rulebook and simulate it — this is the universal Turing machine, the mathematical ancestor of the general-purpose computer. But self-reference creates a trap: ask the clerk to predict whether an arbitrary clerk (possibly itself) will ever stop, and you can always construct a contrarian clerk that does the opposite of the prediction. The prediction task is therefore impossible in general, not merely hard.

Figure

A Turing machine: finite controller scanning an infinite tape

ExampleTracing a TM that increments a unary number

Given: A TM $M$ over $\Gamma=\{1,\sqcup\}$ that appends a single `1` to a block of `1`s (computes $n \mapsto n+1$ in unary). Rule: in $q_0$ , move right over `1`s; on hitting $\sqcup$ , write `1`, then accept. Start tape: `111` (so $n=3$ ), head on the leftmost `1`.

Steps (configuration = state · tape with head position underlined): 1. $q_0:$ `111⊔` → read `1`, move R → $q_0:$ `111⊔` 2. $q_0:$ `111⊔` → read `1`, move R → $q_0:$ `111⊔` 3. $q_0:$ `111⊔` → read `1`, move R → $q_0:$ `111⊔` 4. $q_0:$ `111⊔` → read `⊔`, write `1`, enter $q_{\text{accept}}$ → tape `1111`

Boxed answer: $\boxed{f(3) = 4}$ — the tape now holds four `1`s, the unary encoding of $4$ . Total steps: $4$ transitions for input length $3$ , i.e. $n+1$ steps.

ExampleCounting machines vs. functions concretely

Given: Restrict to TMs whose total description fits in $k = 1000$ bits, and ask how many distinct boolean functions on a single byte ( $8$ -bit inputs) exist.

Steps: 1. Number of TM descriptions $\le 2^{1000} \approx 1.07 \times 10^{301}$ machines (an upper bound on how many functions this finite family can compute). 2. Number of functions $\{0,1\}^8 \to \{0,1\}$ : domain has $2^8 = 256$ inputs, so the count is

9

\quad 2^{2^8} = 2^{256} \approx 1.16 \times 10^{77}.

Derivation hint: each of the $256$ inputs is independently mapped to $0$ or $1$ , giving $2^{256}$ truth tables. 3. Here $2^{1000} \gg 2^{256}$ , so all $2^{256}$ functions are describable within 1000 bits. But let the input width grow: functions on $w$ -bit inputs number $2^{2^w}$ , which for $w = 10$ already gives $2^{1024} > 2^{1000}$ .

Boxed answer: $\boxed{2^{2^w} > 2^{1000} \text{ for } w \ge 10}$ — already at 10-bit inputs there are more functions than 1000-bit programs, so some are not computable by any such program. Taking $w \to \infty$ gives the uncountability gap of $[8]$ .

⚠️ Common mistake

"Undecidable" ≠ "hard" ≠ "unknown." The halting problem is not merely intractable like NP-complete problems; it is provably impossible for any algorithm, regardless of time or memory. Also, undecidability is about deciding all instances uniformly — for any specific program you may well be able to determine whether it halts. The theorem only forbids a single general method that works for every input.

⚠️ Common mistake

The Church–Turing thesis is not provable. Because "effectively calculable" is an informal notion, the thesis cannot be a theorem; it could in principle be refuted by exhibiting a physically realizable procedure computing a non-Turing-computable function. No such device is known, and quantum computers do not violate it (they compute the same class of functions, only — for some problems — faster).

CounterexampleRecognizable but not decidable, and the gap between them

The complement of the halting problem, $\overline{\mathrm{HALT}}$ (machines that loop), is not even recognizable. If both $\mathrm{HALT}$ and $\overline{\mathrm{HALT}}$ were recognizable, run both recognizers in parallel; one must accept, giving a decider — contradicting undecidability. This shows recognizability is not closed under complement, unlike decidability. Concretely:

10

\quad \mathrm{HALT} \in \mathrm{RE},\qquad \overline{\mathrm{HALT}} \notin \mathrm{RE},\qquad \mathrm{HALT} \notin \mathrm{R}.

Derivation hint: $L \in \mathrm{R}$ iff both $L$ and $\overline{L}$ are in $\mathrm{RE}$ (Post's theorem); $\mathrm{HALT}$ fails this.

connection

Computability theory underpins much of theoretical computer science and logic. It feeds directly into Complexity Theory, which refines "computable" into "computable within bounded resources" (P, NP, PSPACE). Its diagonalization technique is the same engine behind Gödel's Incompleteness Theorems — Turing's halting argument can be rephrased to prove that any consistent, sufficiently strong formal system has true-but-unprovable statements. The encoding of machines as numbers connects to Recursive Function Theory and to Formal Languages and Automata, where Turing machines sit atop the Chomsky hierarchy above pushdown and finite automata. The notion of one problem reducing to another links to Many-One Reducibility and the structure of Turing Degrees.

🔬 Where this appears

⏳ History

- 1900 — David Hilbert poses, among 23 problems, the Entscheidungsproblem: find an algorithm deciding the truth of any first-order statement.

- 1931 — Kurt Gödel proves his incompleteness theorems, showing arithmetic cannot be both complete and consistent — foreshadowing computational limits.

- 1933–34 — Gödel and Jacques Herbrand define general recursive functions.

- 1936 — Alonzo Church introduces the λ-calculus and proves the Entscheidungsproblem unsolvable; states "Church's thesis."

- 1936 — Alan Turing independently defines the Turing machine, the universal machine, and proves the halting problem undecidable, settling the Entscheidungsproblem.

- 1936 — Emil Post publishes a closely related "worker on a tape" model.

- 1937 — Turing proves λ-definability, μ-recursion, and TM-computability all coincide, unifying the field.

- 1943–53 — Stephen Kleene systematizes recursion theory; states the Church–Turing thesis in its standard form and proves the recursion (fixed-point) theorem.

- 1953 — Henry Gordon Rice proves Rice's theorem: every non-trivial semantic property of programs is undecidable.

- 1970 — Yuri Matiyasevich completes the proof (with Davis, Putnam, Robinson) that Hilbert's Tenth Problem is undecidable.

open-problem

Computability theory has a rich landscape of unresolved and subtle questions. The Busy Beaver function $\Sigma(n)$ — the maximum number of `1`s a halting $n$ -state TM can print — grows faster than any computable function and is itself uncomputable; the exact value of $\Sigma(5)$ was only confirmed (47,176,870) in 2024, and $\Sigma(6)$ is astronomically beyond reach, recently shown to exceed $10\uparrow\uparrow15$ . Post's problem — whether there exist r.e. sets strictly between decidable and $\mathrm{HALT}$ in Turing degree — was solved (yes) by Friedberg and Muchnik in 1956 via the priority method, but the fine structure of the Turing degrees $\mathcal{D}$ remains an active research area with many open questions about its order-theoretic and automorphism properties. At the philosophical frontier, hypercomputation asks whether any physical process could compute beyond Turing limits — currently no, but the question intertwines with open problems in physics about the computability of physical law.

Computability Theory and Turing Machines

Formal Statement

Why It Holds / Derivation

Building Intuition

Worked Examples

Common Misconceptions

Connections

Real-World Applications

Historical Development

Subtleties & Limits

See Also