RELATED BBC SITES
Last Updated: Monday, 26 November 2007, 11:52 GMT
 E-mail this to a friend Printable version
Proving Turing's simple computer
 By Ben Crighton BBC Radio 4, More Or Less

 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

 E-mail this to a friend Printable version

### Bookmark with:

What are these?

FROM THE OPEN UNIVERSITY

SEARCH MORE OR LESS: