Few figures embody the fusion of pure intellect and practical genius as powerfully as Alan Turing. A mathematician, logician, and wartime hero, Turing not only laid the theoretical foundations of computer science but also changed the course of history with his work at Bletchley Park. His design for the Automatic Computing Engine (ACE) was one of the earliest blueprints for the modern computer, while the “Bombe” decryption device he helped develop enabled Britain to crack Nazi Germany’s Enigma code, hastening the end of World War II. In Turing, abstract logic met urgent necessity, and the result was a revolution in both science and society.
But Turing’s legacy extends far beyond his wartime triumphs. His groundbreaking work on computation and artificial intelligence opened questions that remain at the heart of today’s technological debates. What does it mean for a machine to “think”? How can logical systems capture the nuances of human reasoning? And where do the limits of computability lie? These were the puzzles Turing posed with extraordinary clarity, and in many ways, we are still living in the wake of his unanswered questions.
One of the most perceptive guides to Turing’s world is Martin Davis, Professor Emeritus of Computer Science at New York University. A preeminent logician and theorist of computation, Davis has devoted his career to tracing the deep roots of computer science, from Leibniz’s dream of a universal calculus to Turing’s formalization of the algorithm. His book The Universal Computer offers a sweeping history of the ideas that made modern computing possible, showing how centuries of mathematical thought culminated in Turing’s vision.
In conversation, Davis highlights both the rigor and the audacity of Turing’s contributions. He reminds us that behind the technical achievements was a mind constantly probing the boundaries between the possible and the impossible, between what can be computed and what forever escapes calculation. To revisit Turing through Davis’s eyes is to see not only the birth of computer science but also the enduring philosophical questions about logic, intelligence, and the nature of thought itself.
Charles Carlini: 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, which 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.
CC: 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.
CC: 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.
CC: 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.
CC: "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 those of a person.
CC: 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 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.
CC: 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 in cracking the German naval “Enigma” cipher was crucial in dealing with U-boat depredations on the shipping on which Britain depended.
CC: 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.
CC: 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.
CC: 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.
Recommended Reading
