COPElAND | 61
Turing showed, however, that digital super-optimism is false.^17 It is definitely not the case
that all well-defined mathematical tasks can be done by computer—not even in principle. Some
tasks simply cannot be performed by computing machines, no matter how good the program-
mers or how powerful the hardware.
Turing was the first to describe examples of tasks like this, and in discovering them he blazed
a trail through the new landscape glimpsed by Gödel—the unknown world of uncomputability.
Exploring the unknown world
Some of Turing’s examples are simpler than others, and the simplest one is surprisingly straight-
forward. The task is this: to work out, about any given computer program in some specific
programming language (C++, for instance), whether or not running the program will involve
outputting a given keyboard character, say ‘#’.
It might seem a relatively easy task for someone who understands the programming lan-
guage to scan through the lines of a program and figure out whether any instruction will result
in the computer’s outputting the character ‘#’, but Turing showed that no computer can perform
this task. The reason, essentially, is that the scope of the task covers all computer programs,
including the program of the very computer attempting the task.
Another example of an uncomputable task is provided by Turing’s result about the decision-
machine: no computer can decide whether or not arbitrarily selected formulae are provable
in Hilbert’s engere Functionenkalkül. Chapters 37 and 41 give more information on Turing’s
negative result about the decision-machine.
Between them, Gödel and Turing had delivered multiple blows to Hilbert’s account of the
nature and foundations of mathematics, from which it never recovered. Hilbert’s overarching
concern had been to ‘regain for mathematics the old reputation for incontestable truth’, as he
put it;^18 but caring less about incontestability and ancient reputation, Gödel and Turing looked
towards new mathematical realms that Hilbert had not even imagined.
Hilbert on axioms
Axioms are mathematical propositions so basic that they stand in no need of proof. Hilbert
described axioms as principles that are ‘as simple, intuitive, and comprehensible as possible’.^19
Examples are the so-called Peano axioms, named after the Italian mathematician Giuseppe
Peano. The Peano axioms are about the ‘natural’ numbers: 0, 1, 2, 3, 4, etc. Two examples of
Peano axioms are:
(1) if the immediate successor of natural number x = the immediate successor of natural
number y, then x = y; and
(2) 0 is not the immediate successor of any natural number.The immediate successor of a natural number is simply the number immediately following it in
the sequence 0, 1, 2, 3, . . . . For example, the immediate successor of 7 is 8, and the immediate
successor of 3 + 4 is also 8. Most people are able to see intuitively that both these axioms are true.
Axioms are the starting point of all mathematical proofs: by a process of rigorous logical
deduction, mathematicians prove theorems from axioms. From the total of five Peano axioms,