hypios

Turing would have been 97 years old today. If he were alive, we’d give him a brand new silver Macbook pro. Not only is it a lovely exemplar of Turing’s most famous brainchild, the Turing Machine, but it’s got a partly-eaten apple emblazoned across its back—a reference, some insist, to Turing’s 1954 death by cyanide-laced apple (which was itself a suicidal wink, others claim, to his favorite fairy tale, Snow White, which was in turn…).

Who was Alan Turing? According to his biographer, Andrew Hodges, who maintains a fantastic site of Turing-iana, he was the “founder of computer science, mathematician, philosopher, codebreaker, strange visionary and a gay man before his time.” (He was convicted of gross indecency under the same British law that had sent Oscar Wilde to prison 50 years earlier.)

Why do we at hypios love Turing (so much so that his birthday appears on our internal calendar)? Simply, his work provides the conceptual foundation for modern computing—the dominant technology of our time—and his insights remain far from exhausted. He also made astounding parallel contributions to math, logic, cognitive science and the philosophy of mind.

What were these contributions? In many ways they’ve become so ubiquitious that they’re hard to see. The first conceptual hump to get over is making the distinction between the computer as you know it (the one that you’re using to read this) and the idea of a machine. The latter remains purely formal or theoretical, a bit like a thought experiment, and is indifferent to its material incarnation. A Turing machine might, for example, be electronic, neuronal or mechanic. In principle it should be constructible, but what Turing was after with his idea of the Turing machine (and a universal Turing machine, as we’ll see below) was closer to offering the most general model of a caculable process or method than to building a MAC (or VAIO or…) prototype.

In Turing’s day, we should recall, “computers” still referred to people—people who calculated. On the other hand, the idea of a calculating machine had been around for a while, and was usually thought about in terms of Leibniz’s calculus ratiocinator, whose basic idea was an inference engine. Turing’s contribution, from a computer science viewpoint, was the idea that one machine could necessarily perform all computable tasks; one didn’t need different machines for different tasks. This was in no way an obvious thought. In 1956, the chief of the electromagnetic relay calculator at Harvard, Howard Aiken, wrote:

If it should turn out that the basic logics of a machine designed for the numerical solution of differential equations coincide with the logics of a machine intended to make bills for a department store, I would regard this as the most amazing coincidence that I have ever encountered.

In fact, it’s turned out just that way.

But what makes such a machine—a machine that can be equally applied to biology and billing—possible? To understand Turing’s answer, we need to get a grip on one further distinction: that between the universal and the general Turing machine. While a general Turing machine is able to complete a certain computing task by following a table of instructions, a universal Turing machine would be able to simulate all such computing machines. Turing’s major contribution was to prove that anything that is computable can in fact be computed by one machine: a universal Turing machine.

And what, for Turing, is computable? Computability, is of course, a concept that has fundamentally to do with numbers and the operations to which they are susceptible (addition, subtraction and the like). What numbers are computable and how do we know that they are computable? Turing’s innovation here is related to the famous Entscheidungsproblem (decision problem), a question posed by mathematician and logician Hilbert. Hilbert asked whether there could be a general method or process by which one could decide whether a mathematical proposition could be proved. Turing responded to this question with his 1936 paper “On Computable Numbers, with an application to the Entscheidungsproblem.” Briefly, he saw that it was necessary to grasp exactly what was meant by a ‘method’ or ‘process,’ and had an idea which made this quite precise: computability. What it was to be computable, precisely and exactly, was to be a real number whose expression as a decimal is calculable by finite means. He wrote that “a number is computable if its decimal can be written down by a machine.” (You can read the paper here.) Offering the definition of computability—and thus the limits of computability—was itself one of Turing’s greatest achievements.

What it means to be computable is also what can be done by a universal Turing machine acting alone. The activity of any Turing machine is determined by a mechanical process: anything that can be formalized into a set of instructions or an instruction table. This determination is what distinguishes the calculable from the uncalculable. Any process that is not computable in this way is undecideable in the sense of Hilbert’s question. In 1947, Turing said:

It can be shown that a single special machine of that type can be made to do the work of all. It could in fact be made to work as a model of any other machine. The special machine may be called the universal machine.

So Turing’s universal machine is able to simulate the work of any specific machine. In sum, Turing showed that while there are many things that can’t be computed (or decided), all computable things can be computed by a universal Turing machine. This leads us to the Church-Turing thesis: everything that is computable, is Turing computable.

And we haven’t even begun to address the question of simulating physical reality or even our brains be simulated on a Turing machine. For this and so much more, we wish Turing a happy birthday!

Simone De Liberato

Photo by jessie_st.amand / CC BY 2.0

Share this post!