iPod Mathematical Riddle Solved
Weekend Edition Math Guy Keith Devlin takes up a problem originally posed in the 1930s that said it was possible to develop small intelligent machines like iPods and laptops. That problem was recently solved by a 20-year-old student in Birmingham, England.
SCOTT SIMON, host:
This is WEEKEND EDITION from NPR News. I'm Scott Simon.
Coming up, Norman Mailer's literary legacy.
But first, one thing we've learned from the world of math is that old theories never die. They just get recomputed or something like that. A 20-year-old student in Birmingham, England has a solution to a problem originally posed in the 1930s that proved it was possible to develop small, intelligent machines like iPods and laptops.
Our Math guy Keith Devlin brings us the proof. He joins us now from campus of Stanford University. Keith, thanks for being with us.
Dr. KEITH DEVLIN (Executive Director, Center for Study of Language Information, Stanford University): Hi, Scott. Good to be here.
SIMON: Now, it all started, as I gather, with a man named Alan Turing.
Dr. DEVLIN: True.
SIMON: A mathematician of some note, really one of the great heroes of World War II, and he never lifted a rifle.
Dr. DEVLIN: Yeah, it was really quite a remarkable story. In the 1930s, this young, Cambridge mathematician developed this theoretical idea of computation, and he invented things called Turing machines, which were hypothetical computing devices, studied them, discovered that it should, in principle, be possible to build a computer which could be programmed to carry out any competition you want it to do, then you fast forward to the Second World War when you needed computers, in particular, to break the German Enigma codes.
And along comes Turing, goes to the secret research establishment in Bletchley Park in England and helps to build the first computer, one of the first computers. And, therefore - in his own lifetime, he's able to see - put into practice something which, as a young person, he proved purely as a mathematical, hypothetical concept.
SIMON: Now the person to get involve next in the process was Stephen Wolfram.
Dr. DEVLIN: There was some work on this in the '60s and the '70s. Marvin Minsky, a computer scientist at MIT, showed that you could build one of these so-called universal Turing machines - one of these programmable machines -which had just four internal machine states and computed on just seven symbols. And that was pretty simple: If it's four states, seven symbols. The program to make this thing work is only 28 instructions long as opposed to the millions of lines in Microsoft Windows and so forth, so very, very simple. The question was: Could you make it even simpler?
In the 1990s, along comes Stephen Wolfram who had already made a big name for himself as a mathematician then made himself a small - maybe even a medium-sized fortune - by building the very powerful mathematical software system called Mathematica. He began to look at these Turing machines and, in particular, this question: What's the simplest device that's programmable to carry out any computation? And he came up with a candidate: It has just two internal states and it computes on just three symbols. He was able to gather some evidence that suggested that these machines - this very simple machine could be programmed to carry out any computation, but he wasn't able to prove it.
He wrote a book in 2002 called "A New Kind of Science" in which he described this problem, challenged people to solve it - nobody did. Early this year, Wolfram goes on the Web and announces a $25,000 price to the first person that can show that his little machine - two states, three symbols - could carry out any computation. That's the problem that this young, English, computer science student called Alex Smith proved a few weeks ago.
SIMON: Why would a 20-year-old set out to make this proof?
(Soundbite of laughter)
Dr. DEVLIN: It's something that's doable. You don't need a lot of mathematical knowledge in order to attack these things. They're about the basic aspects of computation. You can learn all of the facts you need in an afternoon. It really comes down to whether you're smart mathematically, whether you can think deeply, and whether you can think through a problem that will take 40 or 50 pages to write out the solution. We're all wondering what's going to happen to him when he graduates and goes on and creates some kind of a career.
SIMON: I understand the faculty at Stanford says they anticipate a vacancy very soon.
(Soundbite of laughter)
Dr. DEVLIN: I'll tell you what, Scott, we always keep our an eye on these bright, young people, and we do what we can to get them here. Stanford doesn't stay at the top of the pile by accident. We work very hard at doing that.
SIMON: Keith, you're always at the top of our pile. Thank you.
(Soundbite of laughter)
Dr. DEVLIN: I'd love to be there, Scott.
SIMON: Keith Devlin is executive director of the Center for the Study of Language and Information at Stanford. He joined us from their studios in Palo Alto.
Copyright © 2007 NPR. All rights reserved. Visit our website terms of use and permissions pages at www.npr.org for further information.
NPR transcripts are created on a rush deadline by an NPR contractor. This text may not be in its final form and may be updated or revised in the future. Accuracy and availability may vary. The authoritative record of NPR’s programming is the audio record.