CHAPTER 37

Decidability and the

Entscheidungsproblem

robin whitty

I

n 1936 Turing invented a mathematical model of computation, known today as the

Turing machine. He intended it as a representation of human computation and in

particular as a vehicle for refuting a central part of David Hilbert’s early 20th-century

programme to mechanize mathematics. By a nice irony it came to define what is achiev-

able by non-human computers and has become deeply embedded in modern computer

science. A simple example is enough to convey the essentials of a Turing machine. We then

describe the background to Hilbert’s programme and Turing’s challenge—and explain

how Turing’s response to Hilbert resolves a host of related problems in mathematics and

logic.

Turing in 30 seconds

If I had to portray, in less than 30 seconds, what Alan Turing achieved in 1936 it seems to me

that drawing the picture shown in Fig. 37.1 would be a reasonable thing to do. That this might

be so is a testament to the quite extraordinary merging of the concrete and the abstract in

Turing’s 1936 paper on computability.^1 It is regarded by, I suppose, a large majority of mathem-

atical scientists as his greatest work.

0

(^0) A BC
0
1
1
1 figure 37.1 A machine that processes
binary numbers.