ADVERTISEMENT

A New Kind of Science Author Pays Brainy Undergrad $25,000 for Identifying Simplest Computer

But will it jumpstart Stephen Wolfram's scientific revolution?
Turing machine



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.

The 2,2 Turing machine was obviously simple, Wolfram says. Not so for the incrementally more complex version with two states and three colors (2,3), so if he was right about simple rules always breeding complexity, he wrote in the book, the 2,3 Turing machine should in fact be universal.

Of course, simplicity is in the eye of the beholder. The 2,3 Turing machine described in the dense new 40-page proof "chews up a lot of tape" to perform even a simple job, Smith says. Programming it to calculate 2 + 2, he notes, would take up more memory than any known computer contains. And image processing? "It probably wouldn't finish before the end of the universe," he says.

Coming up with the proof "looked hard," says Wolfram, who won a MacArthur Foundation "genius" grant when he was 22 years old but says he prefers building software tools to cranking out proofs. His company produces the number-crunching software Mathematica.

Smith, however, who counts among his hobbies playing Dungeons & Dragons and writing programs in obscure computer languages, needed a diversion on his summer holiday in Birmingham, where his parents teach mathematics in the university's economics department. Basically, says the two-time reservist for the U.K.'s International Mathematical Olympiad team, "I had nothing else to do."

Smith says he saw the outline of the answer—the pattern of dots to put on the Turing machine's tape—while lying in bed. Five weeks later, he submitted an initial proof that he knew was flawed, but when Wolfram Research sent back comments and hadn't found any other problems with it, he says he was encouraged enough to spend another week or so tinkering with it.

Wolframania?

Smith's was in fact the only serious submission, Wolfram says. Wolfram Research enlisted an employee and two paid consultants to check the details of the proof and ran it past an eight-person prize committee of well-known mathematicians and computer scientists.

The precocious prizewinner is "absolutely very clever," says computer scientist Lenore Blum of Carnegie Mellon University, a member of the committee, who says the award may renew interest in the complexity of simple Turing machines and other models. "It's getting eyes on a problem that people haven't thought about for a long time."

Of course, there may be a reason the problem languished. "Finding the smallest universal [Turing machines] is a neat recreational pursuit," quantum computation researcher Scott Aaronson of the Massachusetts Institute of Technology says, but "it's no longer seen as connected to the central questions of the field."

Martin Davis, a retired professor of mathematics and computer science at New York University who also sat on the prize committee, adds, "I don't think anything is going to hinge on whether that Turning machine is universal or not."

And what of the broader goal outlined in NKS? Wolfram says the new proof has no direct connection to his belief that cellular automata explain just about everything. And although he says that his view may take a couple of decades to gain acceptance, he does see slow progress. By his count, "zillions of papers…take what I do and apply it to lots of other systems"—with a few more published every day, he says.

That could be because cellular automata date back to the 1950s, Aaronson says. "The impact of NKS on all the areas of computer science and physics I'm familiar with has been basically zero," he says. "As far as I can tell, the main impact is that people now sometimes use the adjective 'Wolframian' to describe breathtaking claims for the trivial or well-known." Davis offers a sunnier take: "The book has a lot of beautiful pictures."

Smith, who says he plans to put the money in the bank until he can think of something to do with it, seems accustomed to receiving blank stares for his efforts. "The sort of thing I do normally doesn't have much a use. This isn't much different."

Rights & Permissions
Share this Article:

Comments

You must sign in or register as a ScientificAmerican.com member to submit a comment.
Scientific American Holiday Sale

Black Friday/Cyber Monday Blow-Out Sale

Enter code:
HOLIDAY 2014
at checkout

Get 20% off now! >

X

Email this Article

X