$25000 Prize Awarded for Simplest Turing Machine Ever

28 Oct 2007

Math, as related to Computer Science is highly intriguing to me. This article especially caught my eye, since I saw the challenge posted some five months ago. Well, in an untypically fast timeframe for math solutions, Alex Smith from Birmingham, UK has proved that this machine is indeed universal -- the simplest (first?) 2,3 Turing Machine ever proven to be so.


Just two states and three colors. It is almost a puzzle in and of itself that such a simple machine can be universal. This is a nice rebuttal to the academics that state most innovative solutions in mathematics have already been done by our predecessors. Alex Smith has quite negated that statement through his proof.