The Turing Guide

wHITTy | 411

which will in turn try to simulate H, and so on ad infinitum. The machine can never proceed to
the point where it writes an output for machine H. But then its output is finite, in which case it
is not satisfactory.
So Turing had to debug his programme, the first person in the world to do so! The simula-
tion step (H simulating H) appears tricky, but it is fine: his proof of universality ensures this.
Attention focuses on the ‘if’ condition: can it be a bug? It must be a bug, because everything else
is working. Turing concluded, exactly as he wanted to conclude, that he could not programme
a machine to check satisfactoriness. This is known as ‘Turing’s theorem’:

Satisfactory numbers are not computable: there can be no machine which, given any positive
integer k, and in a finite number of steps, outputs ‘yes’ if k is satisfactory and ‘no’ if it is not.

It was a small step for Turing to establish undecidability on the basis of his theorem. Even so,
it introduced the new idea of ‘machine reductions’. Rather than giving details, we illustrate the
ideas in Fig. 37.4. Note that there are two reductions. One shows that a hypothetical machine
solving a new task (Turing’s choice was an artificial ‘printing problem’) reduces to (or converts
into) a machine solving satisfactoriness: thus this new task cannot be computed. This is the
most influential kind of reduction, which has since been applied in hundreds of new cases and
adapted to related tasks such as assigning a level of computational complexity to a computing
task. Its influence in mathematics and mathematical logic is profound.

Satisfactoriness

Problem

Machine M

M

P(M)

provable if

and only if

M prints ‘0’

Reducer

Reducer

Printing Problem

Determine if a given

machine M ever

prints a given symbol

Yes/No

figure 37.4 Reductions between Turing machines.

The second reduction turns machine M into a theorem P(M). A machine that solves the
Entscheidungsproblem by checking provability can in turn solve the unsolvable printing problem,
which in turn checks the uncheckable satisfactoriness property. Thus, an Entscheidungsproblem
machine cannot exist; the last facet of the Hilbert programme shatters.

Turing and Hilbert: the final showdown

As a coda we return to Hilbert’s tenth millennium problem: Can a computer program be writ-
ten to decide solvability of any input Diophantine equation? Can we somehow reduce this to