Manuel Blum came to Carnegie Mellon as a visiting professor in 1999 and has been the Bruce Nelson Professor of Computer Science since 2001. The 1995 winner of the A.M. Turing Award, he is a member of the National Academy of Sciences and the National Academy of Engineering and a fellow of the American Academy of Arts and Sciences. Husband of Lenore Blum, Distinguished Career Professor of Computer Science, they are together the parents of a third member of the SCS faculty, Computer Science Professor Avrim Blum. Manuel Blum recently spoke to Joanna Steward, founding managing editor of The Link, about problem-solving strategies and why Paul Erdös was correct when he said that mathematicians are machines that turn coffee into theorems.
Solving Hard Problems
I'd like to understand how to create high-level plans or strategies for solving hard mathematics and computer science problems. But what does it mean to devise a strategy? How do humans create strategies? How can we get machines to create them?
When you have a really hard problem and you've studied the literature, thought about the problem and looked in many different directions for a solution, and none of the ideas work, where can you find new ideas? One way to create a strategy where none exists is to take the problem that you want to solve and modify it. Simplify it or change it in some way so that it becomes easier to solve. Solve the simpler problem and then use that solution as a kind of template--a strategy--for solving the original problem.
For example, in Avrim's algorithm design class (15-451), which I greatly enjoy teaching, the TAs help me to modify each week's homework problems. That way the students can't just look up answers. It's important to keep the guts of the problems, and also to create problems that are new. We talk over the changes--what the TAs decided to modify, whether the changes are instructive, whether the problem has lost or gained something important, and so on. Basically, I get to try out some of my informal ideas about strategies and how to go about changing problems to make them easier or different.
Turning Coffee into Theorems
One of the things we humans learn is that when you're working out a hard problem and you aren't getting anywhere, it's a good idea to take a break--go out and get a cup of coffee. When you come back, hopefully refreshed, you can often come up with some idea you didn't have before.
But how do you turn advice like that into advice for a computer? You can't tell a computer to take a coffee break. So what's going on in our minds when we take that coffee break? Part of it is that when we come back, we are not back at exactly the same point where we were before. We start fresh in a new state. It's the sort of thing that humans do — and computers can be made to do it, too.
Rip Van Winkle
I remember when I was young thinking, "Wouldn't it be neat if we could just go to sleep for a hundred years and wake up and see what the world was like." Wouldn't it be neat to see the progress that had been made?
I feel like I'm living that right now--I don't have to go to sleep! The world is changing so quickly. Advances in science--in health, biology, computer science, physics, all of these things--are moving so quickly that we're constantly faced with a new world.
In the 19th century, we got used to the fact that machines could do hard physical labor better than humans. In the 20th century, computers became better than humans at memorization and information retrieval. Now we're in the 21st century. I don't know exactly how it's going to work out, but I personally believe that computers are going to be able to do any intellectual activity that humans can do. It's something I'm looking forward to seeing.
(John Barna photo)
Jason Togyer | 412-268-8721 | jt3y [atsymbol] cs.cmu.edu