a Turing machine

Posted on: Fri, 03/26/2010 - 15:59 By: Tom Swiss

If you've never studied computer science -- move on, nothing to see here.

But if you have, you'll appreciate Mike Davey's realization of a Turing machine.

A Turing machine, for those non-geeks who still with me, is a theoretical entity that models the process of computation. In 1936, Alan Turing -- one of most brilliant mathematicians ever, who helped break the Nazi's "Enigma" code and save Western civilization, and for his reward was prosecuted and sentenced to "chemical castration" via hormone injections for his homosexuality, but I digress -- proposed a mathematical model of computation that every CS student still studies today.

Imagine an infinitely long tape, divided into cells, where each cell can hold one symbol. This tape moves back and forth under a read/write head (or the head moves over the tape, it's equivalent), which can read the symbol under it and/or write a new one. The machine has just enough memory to hold one number, its "state", and a finite set of rules that tell it what to do when it seems a given symbol while in a given state: for example, "in state 17, if you see a 0, move the tape 23 places to the right and write a 1".

Anything that can be computed, can be computed by a Turing machine. You might think, for example, that a machine that used a two-dimensional grid of cells could do more than a Turing machine, but it can be proven that a "TM" can simulate such a 2-d machine, and so compute anything that it can. I wrote a lot of proofs involving TMs when I was in grad school.

Of course this is not a practical thing to build. Turing meant it only as a sort of thought-experiment. That's part of the beauty of Davey's construction: it's absolutely useless, completely a work of math art.