Friday, October 26, 2007

The simplest turing machine award

From Stephen Wolfram's Blog: I am thrilled to be able to announce that after only five months the prize is won...

Alex Smith--a 20-year-old undergraduate from Birmingham, UK--has produced a 40-page proof.

Just two states and three colors. And able to do any computation that can be done.

...And from searching the 2,985,984 possible 2,3 machines, I found a candidate. Which as of today we know actually is universal.

From our everyday experience with computers, this seems pretty surprising. After all, we're used to computers whose CPUs have been carefully engineered, with millions of gates....(but) That in the computational universe, phenomena like universality are actually quite common--even among systems with very simple rules.

From all my investigation of the computational universe, I came up with the very general principle that I call the Principle of Computational Equivalence.... What it says is essentially this: that when one sees behavior that isn't obviously simple, it'll essentially always correspond to a computation that's in a sense maximally sophisticated

(via KurzweilAI)
Post a Comment