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.
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.
Just to add to what Pål GD said, remember that you're running all the programs of length $i$ or less, and letting them run for at most $i$ seconds. So it might be that there's a program that gets the right answer that is 100 characters long, but it takes 120 seconds to run. Call that program $P$. On $i=100$ you'll check this program, but it takes too long to run so you discard it. After checking all the programs of length 100, you find none of them give the right answer, so you try programs of length $101$ and all the programs you tried before. So you retry $P$, the program that (we know) will give you the right answer, but it still takes too long so you discard it. We keep that process up, until we get to $i=120$. Then we try all the programs of length $\leq 120$, and when we get to $P$ we let it run for long enough for it to give the right answer. Then we stop -- we've found the algorithm we wanted. The iteration we're on is $i = 120$, because although the length of the program $P$ is less (we would write $|P|=100$), we had to wait until the amount of time it took was 120 seconds ($s=120$). So $i=\mathrm{max}\{|P|,s\}$ simply means the maximum of the length of the program $P$ and the amount of time it took to run $s$.
Another way to look at it is for a program $P$ that takes $s$ seconds to produce the right answer, we have to check at least $|P|$ iterations, and at least $s$ iterations before we'll find it, because if $i < |P|$ then we haven't checked that program yet, and if $i < s$ then we haven't let the program run for long enough.
Note that this method of searching is only guaranteed to get you an answer if there is one; it is not guaranteed to find the shortest or quickest answer. The reason for that should be apparent if you consider that the process terminates as soon as it finds a program that gives the right answer.
