Leading student community

A 20-year-old from the UK has recently proven that one of the simplest types of computers can solve every known computational problem, given enough time. Alex Smith, who is studying electrical engineering at the University of Birmingham, will receive mathematician Stephen Wolfram's $25,000 prize in a ceremony held in the home town of the famous computer scientist Alan Turing.

Wolfram offered the prize this past May for a proof to the problem, not knowing whether it would take weeks, months, years, centuries, or if it was even solvable at all. (Smith's answer arrived in June.) The purpose behind the challenge is to understand how complexity emerges from simple systems, and how a set of basic rules can lead to a very intricate result.

Smith learned about Wolfram's challenge in an online chat room, and immediately began working on the problem. His proof, which is 55 pages long, shows how the simple computer--called a "2,3 Turing machine"--is equivalent to another type of computer that has already been proven to be universal, meaning that it can solve any mathematical problem.

The 2,3 Turing machine is named because the head can be positioned in two states (e.g. up and down) and there can be three colors (e.g. orange, yellow, and white) on the computer tape. This is sometimes referred to as a "2-state, 3-symbol" machine. The head states and colors of a row depend on those from the preceding row. In this way, starting with a simple head state "up" and a color "white" can eventually result in complexpatterns further down the tape. Simpler Turing machines exist (e.g. the 1,2 Turing machine), but these are not considered to be capable of universality.



Although the proof is not considered hugely relevant to today's computer scientists, Wolfram suggests that it could inspire new research. For example, Turing machines are similar to some simple molecular automata--simple computing devices built from DNA and other biological molecules--and these might one day form the basis of DNA and molecular computers.

According to New Scientist , Smith was at first skeptical of his chances, but his mother encouraged him to go for it because it is "the kind of thing he is good at," she said.