The simplest way to do the Turing boogie
A math experiment was carried out recently when Alex Smith —an Electronic and Computer Engineering undergraduate with “a background in mathematics and esoteric programming languages”— proved that the Turing machine below is in fact universal, making it the simplest universal Turing machine possible. In other words, the cute graph below are the instructions for an abstract symbol-manipulating machine that can in principle do anything your computer (or any other computer for that matter) can do.
Stephen Wolfram, who made the conjecture and offered a $25k reward for proving it, reports:
We’ve come a long way since Alan Turing’s original 1936 universal Turing machine — taking four pages of dense notation to describe.
We did an experiment; and PCE [the Principle of Computational Equivalence] was validated.
But unlike some science experiments, it didn’t take a multibillion-dollar particle accelerator. It just took a 20-year-old undergraduate with a PC.
[It’s] a wonderful monument in the computational universe — a marker at the edge of universality for Turing machines.
It’s a very satisfying way to spend $25,000.
Stephen Wolfram, The Prize Is Won; The Simplest Universal Turing Machine Is Proved
Now, ain’t this just breathtaking?