Honored professor stumps computers
Manuel Blum is just as interested in deciphering what a computer can do as what it can't do.
Blum's pioneering work in computers — the Carnegie Mellon University professor is now tackling a program to curb identity theft — has merited his election to the National Academy of Sciences, one of the nation's highest honors for a scientist or engineer. Only 72 people were elected this year to the 1,900-member academy, which advises the government on scientific matters.
"It's not something you apply for. I was very surprised," Blum said.
Six other CMU faculty members belong to the organization, which was created by Abraham Lincoln and once counted Albert Einstein among its members.
Within the world of computer scientists, Blum, 64, is known as one of the founders of complexity theory, which holds that some problems are too complex for a computer to solve — yet.
"I don't think there's anything we can do that a computer won't eventually be able to do," Blum said.
In the real world, knowing what a computer can't do allows people to design security systems that can't be beaten by a machine. For example, Blum and a team of CMU colleagues created a test Yahoo uses to ensure that people who register for an e-mail account are indeed human beings and not computer programs.
The Internet equivalent of telemarketers use computer programs to register for multiple e-mail addresses so they can flood people with unwanted advertisements, called spam.
The test is simple. An applicant for an e-mail account, after supplying his name, address and other information, is asked to type a word that appears, somewhat distorted, on the screen in front of them. Blum said his 5-year-old grandson can recognize the words the test uses, but computer programs are unable to respond.
Much to Yahoo's consternation, Blum has insisted on making public the program's technical specifications.
"It's a challenge to the AI (artificial intelligence) community: I'll show you how this program works. Now beat it," Blum said.
Blum taught at the University of California at Berkeley for 30 years before he and his wife, Lenore, also a computer science professor, came to CMU in 1999. CMU's draw for the Blums was personal as well as professional: Their son, Avrim, 35, is a computer science professor at CMU.
"CMU had been trying to get them for a while, but I think it was their grandkids that made them finally come," Avrim Blum said.
James Morris, dean of CMU's school of computer science, knew Manuel Blum when they both were students at the Massachusetts Institute of Technology.
"He's done very important ground-breaking research in lots of aspects of computer science, but he's also a wonderful colleague and leader who's inspired his students to do great things," Morris said.
John Gill, a professor of electrical engineering at Stanford University and a former student of Blum, said complexity theory has helped computer scientists understand the limits of their programs —and has kept them from wasting their time with the impossible.
Complexity theory also has contributed to cryptography, the science of writing messages in code, which is another one of Blum's endeavors.
"A lot of modern cryptography depends on the assumption that there are some things that might be hard to do," Gill said.
Blum is a native of Venezuela whose parents fled Romania on the eve of World War II. In Venezuela, they taught him to speak German, which hardly anyone in that country spoke. When he came to America at age 4, they taught Blum to speak Spanish, which, at the time, relatively few people in this country spoke.
Surrounded by people who spoke a language he didn't understand, Blum grew up thinking he wasn't all that bright. He set out to study human intelligence at the Massachusetts Institute of Technology in the hopes of making himself smarter. It also helped him learn the limits of what machines can do.
In tackling identity theft, Blum explained that computers can be used to steal personal information, such as passwords, credit card numbers or Social Security numbers, that people use to verify their identity when conducting business on-line.
The key, Blum said, is to come up with a test that is unique to each person and that can't be learned by a computer. Like the Yahoo test, it would be a computer program that a computer couldn't beat.
"I love this contradictory sort of stuff. I love to be able to do something that should be impossible," Blum said.