TEMPUS Magazine redefines time, giving you a glimpse into all things sophisticated, compelling, vibrant, with its pages reflecting the style, luxury and beauty of the world in which we live. A quarterly publication for private aviation enthusiasts.
Issue link: http://tempus-magazine.epubxp.com/i/447005
answer to the frst two questions was yes, making the third one moot. He put it simply, "Tere is no such thing as an unsolvable problem." Within three years, the Austrian-born logician Kurt Gödel, then twenty-fve and living with his mother in Vienna, polished off the frst two of these questions with unexpected answers: no and no. In his "incompleteness theorem," he showed that there existed statements that could be neither proved nor disproved. Among them, to oversimplify a bit, were those that were akin to self-ref- erential statements such as "Tis statement is unprov- able." If the statement is true, then it decrees that we can't prove it to be true; if it's false, that also leads to a logical contradiction. It is somewhat like the ancient Greek "liar's paradox," in which the truth of the state- ment "Tis statement is false" cannot be determined. (If the statement is true, then it's also false, and vice versa.) By coming up with statements that could not be proved or disproved, Gödel showed that any formal sys- tem powerful enough to express the usual mathematics was incomplete. He was also able to produce a compan- ion theorem that effectively answered no to Hilbert's second question. Tat left the third of Hilbert's questions, that of decid- ability or, as Hilbert called it, the Entscheidungs prob- lem or "decision problem." Even though Gödel had come up with statements that could be neither proved nor disproved, perhaps that odd class of statements could somehow be identifed and cordoned off, leaving the rest of the system complete and consistent. Tat would require that we fnd some method for deciding whether a statement was provable. When the great Cambridge math professor Max Newman taught Turing about Hil- bert's questions, the way he expressed the Entscheid- ungs problem was this: Is there a "mechanical process" that can be used to determine whether a particular logi- cal statement is provable? Turing liked the concept of a "mechanical process." One day in the summer of 1935, he was out for his usual solitary run along the Ely River, and after a couple of miles he stopped to lie down among the apple trees in Grantchester Meadows to ponder an idea. He would take the notion of a "mechanical process" literally, conjuring up a mechanical process—an imaginary machine—and applying it to the problem. Te "Logical Computing Machine" that he envisioned (as a thought experiment, not as a real machine to be built) was quite simple at frst glance, but it could handle, in theory, any mathematical computation. It consisted of an unlimited length of paper tape containing symbols within squares; in the simplest binary example, these symbols could be merely a 1 and a blank. Te machine would be able to read the symbols on the tape and per- form certain actions based on a "table of instructions" it had been given. Te table of instructions would tell the machine what to do based on whatever confguration it happened to be in and what symbol, if any, it found in the square. For example, the table of instructions for a particular task might decree that if the machine was in confguration 1 and saw a 1 in the square, then it should move one square to the right and shift into confguration 2. Somewhat surprisingly, to us if not to Turing, such a machine, given the proper table of instructions, could complete any mathematical task, no matter how complex. How might this imaginary machine answer Hil- bert's third question, the decision problem? Turing ap- proached the problem by refning the concept of "com- putable numbers." Any real number that was defned by a mathematical rule could be calculated by the Logical A T T W E N T Y - F O U R , T U R I N G ' S N A M E B E C A M E I N D E L I B L Y S T A M P E D O N O N E O F T H E M O S T I M P O R T A N T C O N C E P T S O F T H E D I G I T A L A G E . C O L O S S U S C O M P U T E R Colossus was the world's frst electronic programmable computer developed at Bletchley Park. The Germans considered their code unbreakable, but the code breakers at Bletchley cracked the code with the help of Colossus, which was instrumental in the Allies victory. CH . 2 T H E I N N O V A T O R S : HOW A GROUP OF HACKERS, GENIUSES AND GEEKS CREATED THE DIGITAL REVOLUTION