Thursday, February 3, 2011

Alan Turing

The really interesting thing Alan Turing did was to turn the machine itself into a kind of input. What the machine deals with and the machine itself aren't different in kind. This is the idea that both program and input are held in the same memory space—an essential feature of the von Neumann architecture that describes nearly every computer in existence today.

But the engineering feat is less interesting than the logical one. A machine able to emulate any other machine, including itself, is a universal machine.1 Turing isolated the "machineness" of the machine, if you will, and was able to make true statements about the limits of computability generally on the basis of that.

1 This is called "Turing completeness". The first Turing complete computer was Konrad Zuse's Z3, completed in 1941.