Hilbert, Turing, & Pynchon

[Ghetta Life]

http://en.wikipedia.org/wiki/Thomas_Pynchon

It has been rumored that Pynchon's next book will be about the life and love 
stories of Sofia Kovalevskaya, whom he allegedly studied in Germany. The 
former German minister of culture Michael Naumann has stated that he 
assisted Pynchon in his research about "a Russian mathematician that studied 
for    *David Hilbert*    in Göttingen". No reliable information about the 
novel's date of publication has so far been forthcoming.


http://www.newyorker.com/critics/books/?060206crbo_books

In 1931, Turing entered Cambridge. [...]  With the backing of John Maynard 
Keynes, he was elected a Fellow of King’s College in 1935, at the age of 
twenty-two. [...] That spring, attending lectures in the foundations of 
mathematics, he was introduced to a deep and unresolved matter known as the 
“decision problem.” A few months later, during one of his habitual runs, he 
lay down in a meadow and conceived a sort of abstract machine that settled 
it in an unexpected way.

The decision problem asks, in essence, whether reasoning can be reduced to 
computation. That was the dream of the seventeenth-century philosopher 
Gottfried von Leibniz, who imagined a calculus of reason that would permit 
disagreements to be resolved by taking pen in hand and saying, 
Calculemus—“Let us calculate.” Suppose, that is, you have a set of premises 
and a putative conclusion. Is there some automatic procedure for deciding 
whether the former entails the latter? Can you determine, in principle, 
whether a conjecture can be proved true or false? The decision problem calls 
for a mechanical set of rules for deciding whether such an inference is 
valid, one that is guaranteed to yield a yes-or-no answer in a finite amount 
of time. Such a method would be particularly useful to mathematicians, since 
it would allow them to resolve many of the conundrums in their field—like 
Fermat’s last theorem, or Goldbach’s conjecture—by brute force. That is why 
David Hilbert, who in 1928 challenged the mathematical community to solve 
the decision problem, called it “the principal problem of mathematical 
logic.”

Turing began by thinking about what happens when a human carries out a 
computation by means of a pencil, a scratch pad, and a set of mindless 
instructions. By ruthlessly paring away inessential details, he arrived at 
an idealized machine that, he was convinced, captured the essence of the 
process. The machine was somewhat homely in conception: it consists of an 
unending tape divided into squares (rather like an infinite strip of toilet 
paper). Over this tape a little scanner travels back and forth, one square 
at a time, writing and erasing 0’s and 1’s. The scanner’s action at any 
moment depends on the symbol in the square it is over and the state it is 
in—its “state of mind,” so to speak. There are only a finite number of 
states, and the way they link up what the scanner sees to what it does 
constitutes the machine’s program. (A typical line in a program would be 
something like “When the machine is in state A scanning 0, it will replace 0 
by 1, move one square to the left, and then go into state B.”)

Turing was able to do some amazing things with his abstract devices, which 
soon became known as “Turing machines.” Despite their simple design, he 
showed, they could be made to perform all sorts of complicated mathematics. 
Each machine’s functioning, moreover, could be encapsulated in a single 
number (typically, a very long one), so that one machine could be made to 
operate on another by putting the number of the second machine on the tape 
of the first. If a machine were fed its own number, then it could operate on 
itself. Turing was thereby able to exploit something akin to the paradoxes 
of self-reference (“I am lying”) and show that certain sorts of Turing 
machines could not exist. For instance, there could be no Turing machine 
that, when fed with the program number of another machine, would decide 
whether that machine would eventually come to a halt in its computation or 
would grind on forever. (If there were such a machine, it could be tweaked 
into a Hamlet-like variant that would decide, in effect, “I will come to a 
halt if and only if I never come to a halt.”) But the halting problem, it 
turned out, was merely the decision problem in disguise. Turing was able to 
prove that no computing machine of the kind he envisaged could solve the 
decision problem. Reasoning could not be reduced to computation after all.

But the death of Leibniz’s dream turned out to be the birth of the computer 
age. The boldest idea to emerge from Turing’s analysis was that of a 
universal Turing machine: one that, when furnished with the number 
describing the mechanism of any particular Turing machine, would perfectly 
mimic its behavior. In effect, the “hardware” of a special-purpose computer 
could be translated into “software” and then entered like data into the 
universal machine, where it would be run as a program—the way, for example, 
the operating system on your laptop treats a word-processing program as 
data. What Turing had invented, as a by-product of his advance in logic, was 
the stored-program computer.

_________________________________________________________________
Don't just search. Find. Check out the new MSN Search! 
http://search.msn.com/