It Began with Babbage Read Online Free Page B

was no guarantee that a system of mathematics was free from internal contradictions. He showed that there are true propositions in arithmetic (the truth of which could be established by appealing to concepts
outside
arithmetic) that could not be proved
within
the axiom system of arithmetic itself. He established what came to be called the
undecidability problem
in mathematics: that there are certain propositions in a mathematical system that can be neither proved nor disproved. 7
    All of this meant that a mathematical system (such as arithmetic) is both incomplete and inconsistent. These results came to be called
Gödel’s Incompleteness Theorem
. In proclaiming the limits of mathematical reasoning, it has the same status as Heisenberg’s celebrated Uncertainty Principle in physics.
II
    We seem to be far removed from the story of computing. The world shared by Hilbert, Russell and Whitehead, and Gödel belongs to the furthest reaches of abstraction, a veritable platonic universe seemingly having nothing to do with computing machines, even those that address the solution of algebraic problems. But let us consider another of Hilbert’s famous
fin de siècle
problems: his 10th problem concerning a family of equations of the form
    P (
x
1 ,
x
2 , …,
x n
) = 0
    where P is a polynomial with integer coefficients, known as “Diophantine equations.”
    Hilbert asked whether one could devise a procedure by which it can be decided in a finite number of steps whether a given Diophantine equation is solvable in rational integers (that is, zero, and positive and negative integers, ±1, ±2, and so forth). This is called a
decision problem
or, to use its impressive German term,
Entscheidungsproblem
. As for a “procedure” that can be performed in a “finite number of steps,” what Hilbert was asking was whether there is (using present-centered language) an
algorithm
to decide whether a given Diophantine equation has a solution.
    Now, the
Entscheidungsproblem
bears a connection with Gödel, for, although Gödel had shown that certain mathematical propositions are undecidable, the
Entscheidungsproblem
asks whether there is an algorithm that can decide whether any proposition is or is not decidable.
    This is where Alan Turing enters this story.
III
    As Lord Byron’s estranged daughter and Babbage’s interpreter, as a woman uncommonly gifted in mathematics, and as one who more than anyone else (save for Babbage) can claim to have understood something of what it is to program a computer a century before her time, it is not surprising that Augustus Ada, Countess of Lovelace, has drawn a measure of popular attention. However, among all the characters who people the history of computer science, no one has excited more attention of the nonmathematical, nonscientific world than Alan Mathison Turing (1912–1954).
    Apart from biographies, two plays about him were written, produced, and performed in London and New York (one even garnering three Tony Award nominations). A television film about his life was shown by the BBC. A novel has been written with Turing as its main character. A musical has been made. In Manchester, England, where he lived and taught in the university’s mathematics department in the final years of a short life, and where he died, a bridge and a road were named after him. Statues of the man have been installed in several places in England. Computer laboratories and auditoria and entire buildings have been named after him in universities in Europe, South America, and the United Kingdom. The world’s premier prize in computer science is called the Turing Award. And, in 2012, the centenary of his birth, commemorative events, both scientific and cultural, were held in many parts of the world. One wonders what he would have made of this posthumous adulation.
    No doubt, a significant part of the popular fascination with Turing stems from the tragic aspect of his