4 1. Introduction

to be repaired. The standard means of dealing with this situation is a

priority argument (§6.2), which breaks the goals of the construction

into small pieces and orders them. A piece (requirement) that is ear-

lier in the ordering has higher priority and gets to do what appears at

the moment to satisfy its goal even if that is harmful to later require-

ments. When done correctly, each requirement can be met at a finite

stage and cease harming the lower-priority requirements, and each

requirement can recover from the damage it sustains from the finitely

many higher-priority requirements. Satisfaction of requirements cas-

cades irregularly from the beginning of the order down.

1.2. Some History

The more early work in computability theory you read, the more it

seems its founding was an inevitability. There was a push to make

mathematics formal and rigorous, and find mechanical methods to

solve problems and determine truth or falsehood of statements; hence

there was a lot of thought on the nature of mechanical methods and

formality. For more on this early work, I recommend John Hopcroft’s

article “Turing Machines” [41] and two survey papers by Martin Davis

[20,21]. If you wish to go deeper philosophically (and broader math-

ematically), try van Heijenoort [86] and Webb [88].

David Hilbert gave an address in 1900 in which he listed problems

he thought should direct mathematical effort as the new century be-

gan [37]. His tenth problem, paraphrased, was to find a procedure to

determine whether any given multivariable polynomial equation with

integer coeﬃcients (a Diophantine equation) has an integer solution.

Hilbert asked for “a process according to which it can be determined

by a finite number of operations” whether such a solution exists. For

the specific case of single-variable Diophantine equations, mathemati-

cians already had the rational root test; for an equation of the form

anxn + an−1xn−1 + · · · + a0 = 0, any rational solution must be of the

form ±

r

s

where r divides a0 and s divides an. One may manually

check each such fraction and determine whether any of them yields

equality.

In 1910, the first volume of Alfred North Whitehead and Bertrand

Russell’s Principia Mathematica was published [89]. This ultimately