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 coefficients (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 ±
where r divides a0 and s divides an. One may manually
check each such fraction and determine whether any of them yields
In 1910, the first volume of Alfred North Whitehead and Bertrand
Russell’s Principia Mathematica was published [89]. This ultimately
Previous Page Next Page