s chief scientist of the Internet portal Yahoo, Dr. Udi Manber had a profound problem: how to differentiate human intelligence from that of a machine.
His concern was more than academic. Rogue computer programs masquerading as teenagers were infiltrating Yahoo chat rooms, collecting personal information or posting links to Web sites promoting company products. Spam companies were creating havoc by writing programs that swiftly registered for hundreds of free Yahoo e-mail accounts then used them for bulk mailings.
"What we needed," said Dr. Manber, "was a simple way of telling a human user from a computer program."
So, in a September 2000 conference call, Dr. Manber discussed the problem with a group of computer science researchers at Carnegie Mellon University. The result was a long-term project that is just now beginning to bear fruit.
The roots of Dr. Manber's philosophical conundrum lay in a paper written 50 years earlier by the mathematician Dr. Alan Turing, who imagined a game in which a human interrogator was connected electronically to a human and a computer in the next room. The interrogator's task was to pose a series of questions that determined which of the other participants was the human. The human helped him, while the computer did its best to thwart him.
Dr. Turing suggested that a machine could be said to think if the human interrogator could not distinguish it from the other human. He went on to predict that by 2000, computers would be able to fool the average interrogator over five minutes of questioning at least 30 percent of the time.
Although the Turing test, as it is now called, spawned a vibrant field of research known as artificial intelligence, his prediction has proved false. Today's computers are capable of feats Dr. Turing never imagined, yet in many simple tasks, a typical 5-year-old can outperform the most powerful computers.
Indeed, the abilities that require much of what is usually described as intelligence, like medical diagnosis or playing chess, have proved far easier for computers than seemingly simpler abilities: those requiring vision, hearing, language or motor control.
"Abilities like vision are the result of billions of years of evolution and difficult for us to understand by introspection, whereas abilities like multiplying two numbers are things we were explicitly taught and can readily express in a computer program," said Dr. Jitendra Malik, a professor specializing in computer vision at the University of California at Berkeley.
Dr. Manuel Blum, a professor of computer science at Carnegie Mellon who took part in the Yahoo conference, realized that the failures of artificial intelligence might provide exactly the solution Yahoo needed. Why not devise a new sort of Turing test, he suggested, that would be simple for humans but would baffle sophisticated computer programs.
Dr. Manber liked the idea, so with his Ph.D. student Luis von Ahn and others Dr. Blum devised a collection of cognitive puzzles based on the challenging problems of artificial intelligence. The puzzles have the property that computers can generate and grade the tests even though they cannot pass them. The researchers decided to call their puzzles Captchas, an acronym for Completely Automated Public Turing Test to Tell Computers and Humans Apart (on the Web at www.captcha.net).
One puzzle, called Gimpy, consists of a display of seven distorted, overlapping words chosen at random from a dictionary of simple words. Solving the puzzle requires identifying three of the seven words and typing them into the box provided. The Carnegie Mellon group also created a simplified version of Gimpy - a single distorted word displayed against a complicated background. It is now part of Yahoo's registration process.
Another Captcha, called Sounds, consists of a distorted, computer-generated sound clip containing a word or sequence of numbers. To solve the puzzle, a user must listen to the clip and type the word or numbers into the box provided.
The idea of using puzzles to prevent automated registrations was not new. Other e-commerce sites, including the AltaVista search engine and eBay's PayPal service, were experiencing problems like Yahoo's and independently came up with Captcha-like puzzles. Through its acquisitions, Hewlett-Packard holds a patent on text-based Captchas.
Still, researchers credit Dr. Blum for the breadth of his vision. Dr. Blum "did a great thing by recognizing that this problem is much more than solving a nuisance for Yahoo and AltaVista," said Dr. Andrei Broder, who helped develop the AltaVista puzzle and is now at I.B.M.
As a cryptographer, Dr. Blum was familiar with the constant efforts of cryptographic researchers to advance the field by cracking codes to discover their weaknesses.
He hoped to start a similar dynamic for Captchas, spurring researchers to try to create better Captchas while building computer programs that crack existing ones.
"Captchas are useful for companies like Yahoo, but if they're broken it's even more useful for researchers," Dr. Blum said. "It's like there are two lollipops and no matter what you get one of them."