BBC News
Launch consoleBBC NEWS CHANNEL
Last Updated: Monday, 26 November 2007, 11:52 GMT
Proving Turing's simple computer
By Ben Crighton
BBC Radio 4, More Or Less

Electrical and computer engineering undergraduate Alex Smith
Early on in his research, Alex was confident he would find the solution
A 20-year-old Birmingham University student has won a $25,000 (12,500) maths prize for proving that a certain type of very simple computer, given enough time and memory, could solve any problem that a supercomputer could solve.

Alex Smith, an electrical and computer engineering undergraduate, first heard about the prize in an internet chatroom earlier this year.

He spent his summer holidays trying to crack it, and insists it was the challenge, not the money, that appealed to him.

"It was just something to have a go at, and see how far I could go before getting stuck," he told BBC Radio 4's numbers programme, More Or Less.

Turing machines

The idea of a simple computer that could solve any problem came from the brilliant British mathematician Alan Turing in the 1930s.

Ever since Turing first proposed the idea of a universal machine, mathematicians have been competing to find the simplest one
Turing, who later played a vital role in deciphering secret German codes during World War II, was the first to realise that there could be a single "universal computer" that could be programmed to do any task.

Instead of having a different machine for each task, you could have just one piece of hardware and simply change the software.

Turing machines are not real computers, but hypothetical ones, arranged by "state" and "colour".

Ever since Turing first proposed the idea of a universal machine, mathematicians have been competing to find the simplest one.

It was already known that a two-state, two-colour machine could not be universal, but in his 2002 book A New Kind of Science, another British mathematician Stephen Wolfram speculated that a Turing machine with two states and three colours might be.

The problem was that Wolfram could not prove it. So in May this year he offered a cash prize to anyone who could.

'Obvious' solution

Alex Smith submitted his initial solution in just five weeks.

There was no actual moment of surprise because it became more and more obvious as time went on
Alex Smith, Wolfram Turing prize winner
He says: "It was maybe a couple of weeks until the second version and then maybe a few more weeks before all the loose ends were tied up."

Seemingly unfazed by winning Wolfram's prize, he says it became clear quite early on that he would solve the problem.

"There was no actual moment of surprise because it became more and more obvious as time went on.

"By the time it was announced, I already knew I'd won," he adds.

Maybe it is just as well that the two, three Turing machine is an imaginary one. If it actually existed, users might get frustrated. According to Alex, even a simple sum like two plus two could take a while.

He says: "You wouldn't get it finished in a reasonable time at all. We're talking about millennia, maybe until the end of the Universe. I haven't worked it out exactly."

Practical applications?

So has Stephen Wolfram's quest for the simplest universal Turing machine been a purely academic exercise?

Wolfram has written on his personal blog that he thinks there are practical applications.

He says: "When we think of nanoscale computers, we usually imagine carefully engineering them to mimic the architecture of the computers we know today... [but] we don't have to carefully build things up with engineering.

"We can just go out and search in the computational universe, and find things like universal computers - that are simple enough that we can imagine making them out of molecules."

Back in Birmingham, Alex is not sure what he will do with his $25,000 prize.

He says: "I've just put it in the bank for the time being, and I'm going to leave most of it there until something comes up."

More Or Less will be broadcast on Monday, 26 November, 2007, on BBC Radio 4 at 1630 GMT and is presented by Tim Harford. You can also listen again to the programme after it has been broadcast from the More Or Less website. You can also subscribe to the podcast

RELATED BBC LINKS

RELATED INTERNET LINKS
The BBC is not responsible for the content of external internet sites


FEATURES, VIEWS, ANALYSIS
Has China's housing bubble burst?
How the world's oldest clove tree defied an empire
Why Royal Ballet principal Sergei Polunin quit

PRODUCTS & SERVICES

banner watch listen bbc sport Americas Africa Europe Middle East South Asia Asia Pacific