I read on the Wired blog that a 20-year old engineering student from the University of Birmingham has formally proved that a certain Turing machine model invented by Stephen Wolfram* is the simplest possible model.
Turing machines, for those not up on their theoretical computer science, are simple computing machines that Alan Turing conjectured were capable of calculating any computable function (he didn't say anything about efficency).
The usual model is that of a machine with a ticker tape with a sequence of symbols and a number of states. The machine looks at the tape one symbol at a time, and, depending on the symbol and its current state, decides what to do: Go forward one character, go back one character, overwrite the current character, or change state.
What makes this minimal Turing machine special is that it only has two states and three different symbols (sometimes called colours). The student proved that if you take away a colour or a state, it wouldn't be a Turing machine anymore.
Meanwhile, what important result did I discover during my time as an undergraduate? Oh, that's right, I discovered that you can live on nothing but pizza for a week...
*Yes, the same one who created Mathematica.
No comments:
Post a Comment