Last Tech Tuesday as part of my series on the theory of computation I introduced the Turing Machine. Just to refresh your memory, the Turing Machine is essentially a Finite State Machine connected to an infinite tape for storage. And now, drum roll, here is Alan Turing’s amazing intellectual breakthrough: he showed that it is possible to construct a single Universal Turing Machine that will simulate any other Turing Machine!

Let me explain. What a particular Turing Machine does is defined by its transition function between its states. The function specifies for each state and symbol on the tape a new state, a potential output symbol (to replace the content of the current tape square) and a movement along the tape (left or right). Given an arbitrary transition function, Turing figured out a way to encode it on the tape itself and then have the Universal Turing Machine read that tape and emulate all the state transitions.

Or put differently, Turing mathematically proved that we can separate software from hardware and that a relatively trivial piece of hardware would be able to execute any piece of software that could ever be dreamed up (maybe not efficiently but that’s a different question). Subsequent work by Marvin Minsky and more recently by Stephen Wolfram showed just how small such a Universal Turing Machine could be by finding machines as small as a handful of states and symbols. In fact by relaxing some of the constraints on what can be on the tape when the machine starts to work it may be possible to have a Universal Turing Machine in only 2 states and 3 symbols. 

Relating this back to the very beginning of Tech Tuesdays, a CPU with just a few internal states combined with memory, is all that we need to have a general purpose computer. There is no fundamental additional computational power to be gained by making the CPU more complex. Again this doesn’t say anything about how fast we can compute something simply about what we can compute.

I find this result to be one of the truly amazing things about the world. As far as we know, anything that can be computed, can be computed by a nearly trivial machine (given enough time and space). What is also incredible is that Turing derived this result before the first digital computers were built. He published his paper in 1936, about a decade before ENIAC became operational.