Science education tends to be a strange mixture of technical concepts and history. Ideally this gives us the best of both worlds: we learn how to get things done, but we also learn how our methods and formulations developed so that we do not develop tunnel vision. In practice, this often gives us the worst of both worlds: technical concepts are confused by irrelevant historical details, and we learn a bunch of names with no real idea of their significance. Think about how limiting the conception of an atom as planets orbiting around a sun becomes once you start studying more advanced chemistry.
To remedy this a little bit, I’d like to present “Time’s arrow”, a recurring column in which we’ll take a look at a moment or topic in the history of science. Looking at things from outside the classroom, we should hopefully be able to get a better perspective on both history and science. In today’s issue, we’re going to take a look at the grandfather of all modern computer science: Alan Turing.
Turing studied mathematics at King’s College at the University of Cambridge. He was elected a fellow of the college in 1935, at the age of 23, and shortly thereafter he published one of his most famous papers, “On Computable Numbers.” In this paper he explained computation using the metaphor of a tape-fed device that would come to be known as a Turing machine.
The infinite tape running through Turing’s theoretical machine is divided into squares, not unlike a roll of film. Each square can carry a symbol. The machine can read only one square at a time, and it can erase or overwrite the symbol on the scanned square. It can also shift the tape in either direction one square at a time. The machine has a finite number of “states” it can be in, and a finite table of instructions it must follow.
This is an extremely simple device, but according to Turing, these conditions are all that is required for computation. Turing’s paper gets increasingly abstract after this point, but it is mostly comprehensible to the layman as long as you keep the tape-fed machine in mind. Believe it or not, it actually helps to carry out the operations of a Turing machine with pen and paper.
In an extremely elegant move, Turing goes on to specify a way to uniquely number Turing machines. Once we have the ability to encode a machine as a number, we open up the possibility of one machine simulating another. This brings about the concept of the universal Turing machine, which can simulate any Turing machine, including itself.
The Turing machine is a very simple computer. The upshot of all this abstract stuff is that any function that can be performed by any computer can be performed by a Turing machine – in theory, a Turing machine could perform all the necessary calculations to run Battlefield 2, although it would be agonizingly slow and not much fun. Moreover, any function that cannot be performed by a Turing machine cannot be performed by any computer – not even the most powerful supercomputer can determine whether a given program will halt on a given input. Turing’s work outlined the limits of computation – and this was all the way back in 1936, long before the personal computer was even thought of. He would go on to influence the fields of cryptography and artificial intelligence in important ways. He distinguished himself as a codebreaker for the British during World War II.
Unfortunately, his story has an unhappy ending: as a gay man, Turing was chemically castrated under the “gross indecency” laws that were still in effect in Britain in the 1950s. His security clearance was revoked, and he committed suicide at the age of 41. The British government did not apologize for their treatment of Turing until 2009, 55 years after his death.
