“It’s amazing,” said Norvig, now director of research at Google, where he has been for the past five-and-a-half years. “I came here because I thought it was an interesting place from a technical point of view. I was working in this very narrow, specific domain. Now it’s this thing that everybody in the world knows about.”

Google’s home page is, of course, one of the most popular destinations on the internet. Behind the familiar and seemingly unchanging search box, Norvig and his team are constantly running a series of experiments to improve the quality of the results it throws up.

On any given day, Google may be testing a couple of new tweaks of its algorithms — the formulas that decide where web pages appear in its listings. Norvig said the company may divert 0.1% of its traffic through a trial version of its search engine to see if users like the results.

“We have to be careful,” he said. “We usually make sure they are only small changes. We don’t want to hurt our users by exposing them to this experience. Every month there are a couple of changes. We measure that we are definitely better.”

For all the fascination with Google’s multitude of other initiatives — for example, its news and e-mail services, its desktop software tools and, most recently, its purchase of the You Tube video-sharing site — its core remains web search. Eric Schmidt, Google’s chief executive, said his growing army of engineers spends 70% of its time on search.

Some of this work is simple hygiene. Google is engaged in a constant cat-and-mouse game with firms seeking to boost their websites’ ranking artificially. With the growth of e-commerce and online advertising, a high position in the index is a matter of great commercial importance.

“Most people seem to think that their page should be the first,” said Norvig. When Google deems that firms have resorted to unfair or manipulative tactics, it steps in to block them. “They’ll do something, we’ll detect it, we’ll put them back down (the index),” said Norvig. “Eventually none of it will work, but it’s an ongoing battle.”

More fundamentally, Google is trying to find better ways to give its users the information and answers they want. “We are at the very beginning of search,” said Norvig. He said his colleagues were “disappointed” that most searches still start by typing a couple of words into a box on a web page.

Google works reasonably well when the information sought is contained within the text of a document available on the web. But this is only a start. It wants to allow its users to find answers from pictures, videos and books. Under the Google Print initiative, it is working with publishers and university libraries to digitise hundreds of thousands of books, thus making them searchable — in many cases, providing access to many titles that were previously all but unobtainable.

Norvig said: “We need to understand where words are on a page, we need to understand diagrams. We need to update our algorithms to understand what the right answer is from a 500-page book. We are doing all that.”

Google is also working on speech-recognition technology so that, within a few years, you will simply be able to “tell” your mobile phone what you are looking for, and Google will go off and find it.

But the holy grail is natural language, or semantic, search — enabling users to pose queries, not with a couple of words, but with a properly phrased question.

Today’s search engines can help with something simple, such as “what is the capital of Japan?” But they struggle with more complex questions, such as “what companies has IBM bought in the past five years?”

The enormous profitability of search advertising is attracting new challengers to this field. Powerset, which hopes to develop a next-generation search engine based on natural language processing, recently raised $12.5m (£6.6m) with the help of a stellar cast of Silicon Valley entrepreneurs, including the founders of PayPal and Napster, and two early “Googlers”. Hakia, a New York firm advised by Yorick Wilks of Sheffield University, is also developing a “ meaning-based” search engine.

Google is relaxed about the threat. Norvig said: “Anybody who is concentrating on search is great because it pushes all of us to get better. You have to wonder where they’re going. Is this a complete solution or is this a component of a solution?” Norvig’s colleague Louis Monier — the French founder of the Alta Vista search engine, who is now at Google working on a secret project — said he gets a dozen invitations a year to join new search companies.

“Every time, they have maybe one small lever that they suspect is huge. They don’t realise that [all] they have [is] a better door latch on a [Boeing] 747. Now all they have to do is build a 747. None of those ideas I’ve seen are compelling.”

It is often said that the rival that will overthrow Google is only a click away. Monier is sceptical. “It’s very difficult to innovate on the scale that we do,” he said. “You need a really radical idea, and need to execute it well.”

Explore Tech & Web

• Personal Tech

• The Web

• Gadgets & Gaming

Times recommends

• Tech world prepares for cut-price Apple laptops
• Google takes sober look at drunken e-mails
• BlackBerry Storm joins the touchscreen scrum