Clockwise from the top right — Alan Turing (photo from MacTutor), Vaughan Pratt (photo from andrej.com), A New Kind of Science by Stephen Wolfram, Stephen Wolfram (photo from The American Mathematical Society).

A 50-year old mathematical problem has thrown up enormous debate in the last month, and its resolution is worth no less than $US 25000.

The half-century quest to find the simplest possible universal Turing machine was thought solved by 20-year old Birmingham undergraduate Alex Smith, who provided a 40-page proof that Wolfram's 2,3 Turing machine is indeed universal.

However, this result, and the $25,000 Wolfram 2,3 Turing Machine Research Prize, is now being seriously debated.

Professor Emeritus Vaughan Ronald Pratt, one of the earliest pioneers in the field of computer science, has questioned the proof in a none-too-subtle way by saying:

"Not wanting to push my luck I'll settle for one question. How did an argument containing such an elementary fallacy get through the filter? [...] Had I pushed my luck my second question would have been, who has verified this proof that has taught an automata theory course at a suitably accredited institution?"

You can read the whole critique here.

The issue has been raised due to the awarding of the Wolfram 2,3 Turing Machine Research Prize by Stephen Wolfram — founder of software company Wolfram Research and developer of mathematical software program Mathematica.

In 2002 Wolfram wrote his modestly entitled 1,200-page A New Kind of Science. The prize is for proving a speculation that Wolfram made, that a simplified Turing machine — which is a mathematical model of a computer, and therefore quite theoretical — could in principle run any conceivable computer program.

The idea of a Turing machine was first proposed in 1936 by British mathematician Alan Turing. The theoretical machine scans a ticker tape printed with a string of symbols, with that line of tape in a particular state. For each symbol it encounters (say an asterisk), it applies a very simple rule such as:

"If your symbol is an asterisk and the cell is in state 1, then replace this with a blank cell, move one symbol to the right, and assume you are in state 2."

For a simple example of the machine's computing power, consider the addition of integers. We can represent an integer by a string of asterisks — ** represents 2, and **** is 4. To add 2 and 4, ** and **** are printed on a tape, with a blank space between the two strings, and the row is designated to be state 0.

** _ ****

The machine then acts according to prescribed rules. In this case, the machine would start by observing the first cell and obeying the following rules:

• State 0: If cell is an asterisk, move one cell to the right;
• State 0: If cell is blank, fill cell with an asterisk, move one cell to the right and change state to state 1;
• State 1: If cell is an asterisk, move one cell to the right;
• State 1: If cell is blank, move one cell to left and change state to state 2;
• State 2: If cell is an asterisk, erase cell and stop.

• By following these rules, the machine fills in the blank cell by printing a * and goes to the end of the string of asterisks and erases the last one. In this way, we get six asterisks in a row, which is the desired result.

  Theoretically, any calculation, given enough ticker tape, can be achieved using a Turing machine. Turing himself demonstrated that such machines could be universal, meaning that they could mimic any other Turing machine if given the right ticker-tape instruction.

  This is where the Wolfram prize comes in. Research in the 1950s proved that you could not have a universal two-state, two-symbol (2,2) machine. Wolfram himself reported that you could have a two-state, five-symbol (2,5) universal machine.

  But can you have a (2,3) universal Turing machine?

  Smith's alleged proof, which aims to show that you can, is 40 pages long, and if true, is mathematically interesting, although such a simple computer would take an extremely long time and vast amount of memory to carry out even the simplest modern computing tasks.

  The debate surrounding its veracity partly concerns those chosen by Wolfram to look over the result. Pratt claims that the judges may have been unsuitable for the job. The debate has also taken a philosophical turn, with there being conjecture over what the term "universal" really means.

  The debate continues at the Wolfram forum. And Pratt and Smith themselves are politely discussing the topic. We shall follow this and let you know what happens.

  Stumbling at the final hurdle and philosophical debates over proofs are nothing new for mathematics. Multiple prizes for solving Fermat's Last theorem, possibly the most renowned mathematical conjecture, were offered in the 1800s and 1900s. In 1823 and 1850, the French Academy of Sciences offered a prize for it solution, and then in 1883 one was offered by the Academy of Brussels. In 1908, the German Friedrich Wolfskehl bequeathed 100,000 marks to the Gottingen Academy of Sciences for a complete proof of Fermat's last theorem. According to mathematical historian Howard Eves:

  "Fermat's last theorem, has the peculiar distinction of being the mathematical problem for which the greatest number of incorrect proofs have been published"

  It was finally proved in the 1990s by Andrew Wiles.

  Another mathematical problem that has brought about much debate is the Four Colour Theorem. Mapmakers have known for centuries that you never need more than four colours to colour a map so that no two adjacent regions have the same colour. Even though this seems like a simple concept, its proof is incredibly difficult, and depending on which camp you sit in, has never been shown. In 1879, English mathematician Alfred Kempe published in both Nature and the American Journal of Mathematics, a proof that was found to be in error 11 years later.

  A century passed before further headway into the problem was made. In 1976, Kenneth Appel and Wolfgang Haken finally managed to prove it in quite a simple way, however the debate surrounds their use of computers. Appel and Haken had to consider every single one of 1,936 map configurations, and this could only be done on a computer. The number of computer calculations was so vast that no human could possibly check the veracity of the proof. This poses a huge philosophical conundrum: can you trust a machine to do maths? The mathematical community split into two camps: those who were prepared to accept the computer proofs and those that demanded a simpler version that can be checked by humans.

  The Four Colour Theorem is therefore still open to be solved.

  You can read more about these mathematical controversies on Plus in an editorial on the last 100 years in maths, and a story on Fermat's last theorem.

  You can also read more on Turing on Plus.