Alan Turing (1912–1954) was an English mathematician, logician, pioneer of computer science, and wartime code-breaker. He is credited with creating a design for the Automatic Computing Engine (ACE), the early electronic stored-program computer, as well as the Bomb—a decryption device that the British government used during WWII to crack the German “Enigma,” machine, which encrypted secret messages.
Professor Emeritus at New York University’s Computer Science Department, Martin Davis is one of the world’s most notable logicians and researchers in the theory of computation. He is the author of several books, including The Universal Computer, which follows a strand in the history of computing from Gottfried von Leibniz to Alan Turing.
Simply Charly: Alan Turing is often credited as being the “father of the computer.” But the English mathematician and inventor Charles Babbage had conceived and designed the first mechanical computer back in the 19th century that eventually led to more complex designs. What is your view regarding this?
Martin Davis: Babbage famously said that his “analytic engine” could do anything except compose country dances, clearly intending that this task was beyond what a mere calculating device could be expected to do. The machines Turing imagined and that we now possess can readily do that.
SC: The Austrian logician Kurt Gödel had proved that there would be some unsolvable problems in all strong enough systems of logic. Then Turing comes along, recasts Gödel’s incompleteness theorem in terms of computers, and makes matters much worse. Can you tell us just how Turing recast Gödel’s theorem and extended his proof?
MD: Turing did no such thing. He took a few ideas from Gödel (using numbers to code data and applying Cantor’s diagonal technique), but Turing’s theorems are in a quite different direction than Gödel’s. Gödel had proved that for any suitable logical system there would be unprovable truths. Turing proved the non-existence of algorithms for solving certain easily statable combinatorial problems.
SC: When Turing was about to publish his seminal paper “On Computable Numbers,” he was surprised to learn, much to his chagrin, that the American mathematician Alonzo Church had already published a paper that was similar in scope and subject matter to his own work. Can you describe the circumstances surrounding this?
MD: What was new in 1935-36 was the existence of precise characterizations of the notion of algorithmic process. Church and Turing had different proposals for this, which were readily proved equivalent.
SC: It would seem as if the ideas for which Turing garnered his reputation were already in the air, ready to be plucked, as it were, from the Platonic realm. In fact, Emil Post’s and Jacques Herbrand’s work in this area bore a striking similarity to that of Turing’s. What is your view?
MD: Post’s work was indeed very close to Turing’s. Herbrand’s contribution was more complicated. It was Gödel who suggested how Herbrand’s rather abstract idea could be made algorithmic. Kleene finally clarified the matter.
SC: “Computing Machinery and Intelligence” is perhaps Turing’s most famous paper. In it he tackles the question, ‘Can machines think?’ What is the main thrust of this paper?
MD: That this should be judged by the machine’s behavior, in particular by whether the machine can make people believe its responses are that of a person.
SC: At about the same time that Turing was working on his computer model, the Hungarian mathematician John von Neumann was also designing his own. Were they on aware of each other’s work and how different or similar were the computers they were building?
MD: Von Neumann did nothing comparable to the abstract model of computation in Turing’s 1936 paper. In the 1940s, Turing’s ACE made do with more limited hardware (using software instead) than von Neumann’s EDVAC or the IAS machine.
SC: During the Second World War, Turing was commissioned by the British government to help decipher the German Enigma code, which the German military used to encode strategic messages. His efforts were so important that former British Prime Minister Gordon Brown recently said that “without his outstanding contribution, the history of the Second World War could have been very different.” So just what was Turing’s contribution that turned the tide of the war?
MD: His work on cracking the German naval “Enigma” cipher was crucial in dealing with U-boat depredations on the shipping on which Britain depended.
SC: Turing made news headlines a few years ago when former British Prime Minister Gordon Brown issued an apology for the “appalling” way in which he was treated at the hands of authorities. To what exactly was the Prime Minister referring?
MD: Turing was prosecuted for “gross indecency” for a homosexual affair and sentenced to a year of estrogen treatments.
SC: You’ve written extensively on Computability Theory as it relates to Turing and others (Gödel, Church, Kleene, and Post). Can you briefly describe the theory behind it?
MD: The theory makes it possible to treat algorithms in generality by mathematical methods and to prove that certain problems are algorithmically unsolvable.
SC: Universities around the world celebrated Turing’s centenary last year. What do you feel is his lasting legacy? And how relevant is his work today?
MD: His work underlies the world we live in.
