[Solved]: What is a lay explanation for universal search?

Problem Detail: 

I am reading a book on a computer science topic but lack some of the prerequisite background. Normally when I run into terms I don't understand I simply look them up, but for Universal Search I simply haven't been able to find an explanation suitable for a reader without a background in statistics/computer science.

I've been reading this article on Universal Search from Scholarpedia, which seems to cover the topic. I'd appreciate an explanation for what Universal Search (or Levin Search) means.

Asked By : arman

Answered By : Pål GD

Think of it like this. You have a problem, with input $x$ and you know how to verify a solution if you ever found one (like the inverse of a matrix or whatever you'd like to imagine).

Now, take your favourite programming language (say Python), and create every single Python program consisting of at most 10 characters! Then you run all those programs with your input for 10 seconds each, each on input $x$. If none of them give you the answer, you go all the way to 11. Run each program of at most 11 characters (including the ones you already tried, of course) for 11 seconds each, on input $x$. If none of them give you the correct answer, you continue to 12 and so on.

More formally, in iteration $i$, you run all programs of length at most $i$ (finitely many, but of course exponential in $i$), each for $i$ seconds (or steps).

There is a program, say $P$ that gives the correct output in $s$ seconds. When you have come to iteration $i = \max\{|P|, s\}$, this program will be run for at least $s$ seconds, and you will output both $P$ and the solution.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/40638