SIX SIMPLE RULES: Wolfram Research, the company founded by A New Kind of Science author Stephen Wolfram, has awarded $25,000 to an undergraduate for proving that a simple model called a 2,3 Turing machine, visualized in action here, can perform any conceivable computation. The machine scans the boxes in each row and applies one of six rules to generate the row underneath.
Image: WOLFRAM RESEARCH
Five years ago, grown-up wunderkind Stephen Wolfram did his darnedest to alter the course of scientific history. The former particle physicist, who is by all accounts a genius, poured two decades worth of heady thoughts on the nature of computers, mathematics and the universe into an ambitious 1,200-page tome modestly entitled A New Kind of Science.
And when that didn't sway his peers, he offered cash.
This week, Wolfram's software company, Wolfram Research, announced that it is awarding a $25,000 prize to an undergraduate student for proving a speculation made in the book—that a very simplified Turing machine, a mathematical model of a computer, could in principle run any conceivable computer program, from crunching math problems to sharpening images. In computer science lingo, that's called universality.
Wolfram's book explored the theme that extreme complexity can blossom from very simple rules, especially those of so-called cellular automata, which resemble ever expanding games of tic-tac-toe and can produce complex, nonrepeating patterns reminiscent of everything from snowflakes to quantum mechanics to natural selection. The former child prodigy argued that such models might offer a better way of understanding physics and even biology than can the traditional tools of calculus.
One of Wolfram's main conjectures was that nearly any simple set of abstract rules should be equivalent to a universal Turing machine in the complexity it can produce. The existence of the new proof, he tells ScientificAmerican.com, adds weight to the idea.
It also marks a "monument in the computational universe," Wolfram says. "This is the end of the road. This is the simplest conceivable universal Turning machine."
Critics of Wolfram's book (and there were many) accused him of claiming others' pioneering work as his own and overselling its significance to boot. Five years later, computation experts see little sign that Wolfram's ideas have gained traction. And some of their reactions to the award suggest that its most important consequence will be to furnish young Alex Smith with some extra spending money.
Smith, 20, a third-year electrical and computer engineering student at the University of Birmingham in England, heard about the Turing machine prize in an online chat room after Wolfram Research put the money up for grabs in May for the fifth anniversary of A New Kind of Science (NKS). "I decided to have a go at it and see what I got," he says. "It clearly wasn't easy, because people wouldn't offer a prize like that if they had been able to solve it themselves."
Named for the British mathematician Alan Turing, who proposed the concept in 1936, a Turing machine can be thought of as a device that scans a ticker tape printed with a string of colored dots (or 0s and 1s—it doesn't really matter). The machine has multiple settings or states, and for each dot it encounters it carries out some rule that depends on its setting, such as "if the dot is orange, change it to yellow, advance to the next dot and switch to setting 2" [see image above]. One Turing machine might be capable of solving arithmetic problems and another might be good at searching databases.
But Turing also demonstrated that one such machine could be universal, meaning that it could mimic any other Turing machine if given the right ticker-tape instruction. The discovery laid the foundation for modern computer science and explains why a single computer can simultaneously play music, connect to the Internet and run a word processor.
Simplify, Simplify
Intrigued by the limits of computation, researchers during the 1950s and 1960s whittled universal Turing machines to smaller and smaller sizes for fun. They learned that a two-state, two-color (2,2) Turing machine was not universal, but one with seven states and four colors was. In NKS, Wolfram reported a proof by one of his employees that two states and five colors sufficed for universality.
See what we're tweeting about
1 Comments
Add CommentI think a more meaningful automata design would be to be able to change the Rule memory, and not just the "data memory". If you dip into nature, you need a random operator, which may enable optimization (e.g., doing something), but loosing the exact same reproducable path it came from. Of course, given a random resource, implies every outcome is possible, thus, effectively calculable.
Reply | Report Abuse | Link to thisjriam1945@aol.com