Wednesday, April 30, 2003

What do I have against Alan Turing?

It's not usual for me to have a set of Frequently Asked Questions before I even give a talk the first time, but this talk had them.

1. You know he's dead, right?

Yes, I know he's dead. He died in 1954, of a depression-induced suicide, apparantly caused by the hormone treatments that the United Kingdom government forced him to take to cure his homosexuality. God knows how much more brilliant work he might have produced. Pretty good argument against Senator Rick Santorum, if you ask me (oops, I said no politics in the blog).

2. What do you have against Alan Turing?

Nothing. He was a brilliant man, the father of the field of computer science, and probably more than any single person, was responsible for defeating the Nazis in World War II (due to his work breaking the Enigma code). The thing I'm against is refusing to move out of the shadow of his work. As I've written elsewhere, if Alan Turing is the father of computer science, it's time we moved out of the house.

More than the man, the problem is his construct, the Turing Machine (although he didn't call it that; the name came later). The Turing Machine is the abstract representation of a computing device on which all modern computers is based. It's composed of a single finite automaton, an infinite (or semi-infinite) tape that contains symbols, and a set of rules for determining how the automaton changes state and writes symbols onto the tape. A processor and memory.

Ironically, while Turing's great achievement in 1936 was showing the fundamental limits of the Turing machine, in modern imagination his achievement seems to be in proving the universality of the TM, that is, that it can compute any function that is computable. That's not really accurate; in a more limited sense, what he said first was that there existed a Universal Turing Machine that could compute any function that any other Turing Machine could compute. Secondly, he showed that the Turing Machine was an equivalent model to a number of other mechanical models of computation that had been proposed. But it's not really accurate to say that he showed the full universality of the Turing Machine; just that the Turing Machine was no less powerful than any other mechanical device.

In fact, it does appear that there are models of computation more powerful. Generally called hypercomputation, this is an active area of research. Quantum computers seem to be more powerful than Turing machines. The thing that Turing Machines don't model is interactivity, most likely a key ingredient in human intelligence. There's a good review article of some of this research in the April issue of Communications of the ACM.

The point is that the Turing Machine is not the only or the final model of computing, and moving to new models will require us to change many of our assumptions, as well as learning new ways to program and to think about programming.