Skip to content
Tape‑n‑Trace
PracticeSearch 26 tools

The diagonalization table

Hopcroft 2e §9.1. Two numberings make this table possible. §9.1.1 pairs every binary string with an integer — put a 1 in front of w and read it as a number — so there is an i-th string wi. §9.1.2 writes every Turing machine as a binary string, and §9.1.3 reads a string that is not a well-formed code as the machine with one state and no moves. So every string is a machine, there is an i-th machine Mi, and the grid below exists.

Complement the diagonal and you have a language that disagrees with every row in that row’s own column. It is therefore no row at all — and every Turing machine is a row. That is Theorem 9.2: Ld is not recursively enumerable, which is stronger than saying it is undecidable.

Every cell here is computed, not illustrated, and that changes what the table looks like. The book’s own footnote to Fig. 9.1 warns that “the top rows of the table are in fact solid 0’s”, because the low integers are all too short to be codes. They are, and you can see exactly where that stops.

Rows 1 onwards. Every one of these strings is too short to be a code, so every machine is the one with no moves and every cell is 0 — which is exactly what the footnote to Fig. 9.1 says the real table looks like here.

Rows 1–12 against columns 1–12. Cell (i, j) is 1 when Mi accepts wj, 0 when it does not, and ? when the run had not finished after 200 moves.
i \ j
1
ε
2
0
3
1
4
00
5
01
6
10
7
11
8
000
9
001
10
010
11
011
12
100
1 — no moves
2 — no moves
3 — no moves
4 — no moves
5 — no moves
6 — no moves
7 — no moves
8 — no moves
9 — no moves
10 — no moves
11 — no moves
12 — no moves

Choose a cell to see the machine its row codes (§9.1.2) and the string its column names (§9.1.1).