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

Purchased from American Mathematical Society for the exclusive use of nofirst nolast (email unknown) Copyright 2012 American Mathematical Society. Duplication prohibited. Please report unauthorized use to cust-serv@ams.org. Thank You! Your purchase supports the AMS' mission, programs, and services for the mathematical community.