ISEGORIA / MATH ENCYCLOPEDIA
Logic and computability: what can be computed
Turing machines, the diagonal argument behind the halting problem, and Gödel numbering.
Before you begin: Set theory and discrete mathematics
Predict, manipulate, then check your reasoning against the example and question. Graphs illustrate the mathematics; they do not replace a proof.
1. Stepping through a Turing machine
A head reads one cell, consults a finite table, writes, moves one cell and changes state. That is all. Choose a machine and scrub through its run; the space-time diagram below stacks every tape, so the whole computation is visible at once.
Worked example. The four-state busy beaver starts on a blank tape, halts after 107 steps and leaves 13 ones, the most any halting four-state, two-symbol machine can leave.
Watch out. Each table here is fixed and finite. What makes the model universal is that one fixed machine can read another machine’s table from its tape and simulate it.
Why can nobody compute the busy beaver function in general?
A program that computed it would bound every halting run and so would decide the halting problem.
2. The diagonal argument
Suppose some program H could tell, for every program i and input j, whether i halts on j. Then build D: on input i, D does the opposite of what the table says program i does on i. D differs from every row on the diagonal, so D is not in the table, although the table was meant to list every program. Click cells to change the table: the contradiction survives every choice.
Worked example. If \(D\) were program number \(d\), the entry \(H(d,d)\) would have to equal its own opposite.
Watch out. The table shown is hypothetical: its entries are chosen by you or by a seed, not computed. The argument is about any table, which is the point.
Which assumption does the contradiction refute?
That H exists as a program that always halts with the right answer.
3. Gödel numbering
Give each symbol a code and turn a formula into one number: the k-th prime raised to the code of the k-th symbol. Unique factorisation means the number can be decoded, so statements about formulas become statements about numbers. Build your own formula from the palette.
Worked example. With the codes shown, \(\ulcorner 0=0\urcorner=2^{6}\cdot3^{5}\cdot5^{6}=243{,}000{,}000\).
Watch out. The particular codes are a convention. What matters is that coding and decoding are mechanical, so provability becomes an arithmetical property.
Why use primes rather than just writing the codes side by side?
The product is a single natural number that arithmetic can talk about, and unique factorisation guarantees it decodes to exactly one sequence.