410 | 37 DECIDABIlITy AND THE ENTSCHEIDUNGSPROBLEM
We shall certainly not attempt to describe how Turing’s universal machine works, although it
is just a couple of dense pages in his 1936 paper. But we will follow his deployment of it as closely
as we can, beginning with a glossary of Turing’s original terminology:
Description numbers: numerical encodings of machine definitions (enumerable as finite
0–1 strings)
Circle-free machines: those that write infinitely many 0–1 symbols onto the tape
Satisfactory numbers: description numbers that encode circle-free machines
Computable sequences: tape outputs produced by circle-free machines (infinite 0–1
sequences, enumerated by enumerating satisfactory numbers)
Uncomputable sequences: infinite 0–1 sequences that are not the output of any machine
(these must exist, by diagonalization).
The idea of a ‘description number’ is a natural application of enumerability: as we have seen,
the totality of a machine—the initial input digits on its tape, and the list of instructions in its
instruction table—can all be represented as long strings of zeros and ones, which together con-
stitute a single positive integer, represented in binary form. Once a machine has become a num-
ber, it is natural to suggest that it be placed on a Turing machine tape and to ask what instruction
table might reanimate this number—thus, Turing’s idea of a universal computing machine.
Note that finite tape outputs are regarded as ‘trivially’ computable and can be excluded
from our discussion. It was the infinite strings that brought Cantor’s theorem to bear on the
matter: some of these strings could not be computed, and Turing used them to dispatch the
Entscheidungsproblem. To recap: infinite outputs are produced by circle-free machines whose
description numbers are satisfactory. In what follows we shall simplify things a bit by using the
word ‘satisfactory’ for both numbers and machines and writing ‘satisfactory machine’ where
Turing would have written ‘circle-free machine’.
An application to the Entscheidungsproblem
The customized universal machine, which we shall call H, is specified in ‘pseudocode’. Turing,
in devising the machine, was readily able to give a native Turing machine specification:
for k from 1 to infinity do (* infinite loop *)
if k is description number of a satisfactory machine (i.e., is a satisfactory description
number) then- write corresponding machine, say Mk, on tape
- simulate Mk until kth output digit reached
- write binary negation of kth output digit on tape
end if
The job of the machine H is to generate a version of the diagonal sequence S featuring in
Cantor’s sleight-of-hand proof of his theorem. Note that H must be a satisfactory machine if it
is to work, since S is infinite. The machine works by enumerating all machines and throwing
away those that do not produce infinite 0–1 sequences (i.e., are unsatisfactory). The trouble is
that the machine cannot work—because if H is satisfactory it must eventually try to simulate H,