The Wolfram Prize and Universal Computation: It's Your Problem Now

It's not often I put you on the spot, but I did yesterday. Here's the deal....

So Ben Wilson, a guy who works for Wolfram Research sent me a note about the establishment of a $25,000 prize for the first person or group to prove (or disprove) that a particular very simple Turing machine can act as a universal computer.

Very cool, no question about it.

The prize is being announced on the fifth anniversary of the publication of Stephen Wolfram's A New Kind of Science and is intended to help stimulate one of the lines of research opened up by the book. (For more on the book, see Michael Swaine's column The Blind Men and The Elephant.)

According to Ben, today's computers have CPUs with millions of components. But it is known in theory that much simpler systems are also capable of "universal computation," which means that with appropriate programming, they can perform arbitrary computational tasks. The aim of the Wolfram 2,3 Turing Machine Research Prize is to determine the edge of where universal computation is possible.

Invented by British mathematician Alan Turing in 1936, Turing machines were the first abstract models of today's computers. Turing's primary achievement was to construct -- on paper -- a single "universal Turing machine" that could be made to emulate any other Turing machine, or in effect to perform any computation.

Ben goes on to say that Turing's insight, which in effect showed that software is possible, is what eventually launched the computer revolution, and led to much of the dramatic growth of technology in the late 20th century.

In his book, Wolfram found many examples of programs with simple rules that give rise to highly complex behavior, and he proposed his general Principle of Computational Equivalence to characterize this phenomenon. One consequence of this principle is that it suggests that universal computation should be common even among systems with very simple rules.

Wolfram's concept that universal computation should be ubiquitous -- even among systems with simple rules -- also has practical implications, notably suggesting that it should be possible to make computational devices out of many new classes of physical systems, especially at the molecular scale.

"Finding the very simplest universal computers is an important way to nail down the Principle of Computational Equivalence," says Wolfram. "And Turing machines are the classic examples of computational systems."

It is this Turing machine that is the subject of the prize. The prize is open to all entrants, both amateur and professional. It has no closing date. The prize is being adjudicated by a committee consisting of Lenore Blum, Greg Chaitin, Martin Davis, Ron Graham, Yuri Matiyasevich, Marvin Minsky, Dana Scott, and Stephen Wolfram.

And this is when I put you on the spot. So in acknowledging that I indeed think the prize is a worthy endeavor, I told Ben that I would mention it and his immediate response was "Maybe one of your readers can crack this thing!" To which I responded: "If a Dr. Dobb's reader can't crack it, then it can't be cracked."

So I deftly moved the burden of solving the problem from my shoulders to your's. If you win the $25,000 prize, well, you can keep it all, but you'll have to write an article for Dr. Dobb's about it. Good luck, and keep me posted.

In a related note, it worth mentioning that Wolfram Research recently released Mathematica 6.0 and DDJ contributing editor Mike Riley talked with Tom Wickham-Jones, Director of Kernel Technology for Wolfram Research, about its new features. You can hear what Tom has to say in this Dr. Dobb's Podcast.

Posted by Jon Erickson at 08:47 AM  Permalink