# Understanding Levin's Universal Search

I am having troubles understanding Levin's universal search method. In Scholarpedia, http://www.scholarpedia.org/article/Universal_search, it is claimed that “If there exists a program $p$, of length $l(p)$, that can solve the problem in time $t$, then Universal Search will solve the problem in a time $2^{l(p)+1}t$ at most.” How do they arrive at this number? Here is what I tried.

If we put all programs in a list, it looks like $e,0,1,00,01,10,11,000,001,010,011,100,101,110,111,0000,\ldots$ Generally, the first occurence of a program of length $l$ is at the $n$th position, with $n=2^l-1$.

Now, I have encountered two different dovetailing procedures in the literature. The first describes executing program 1 every second step, program 2 every second of the remaining steps, program 3 every second of the remaining steps etc. This leads to the following execution sequence of the programs $n=1,2,3,4,5,6,\ldots$: $1213121412131215121312141213121612\ldots$ At step $i$ then $n$th program will have been run for $i/2^n$ steps. In the example above $i=34$. Thus, for $n=1,2,3,4,5,6$ we get $17,8,4,2,1,1$ (rounded) which is roughly correct.

Now, suppose there exists a program $p$ that computes a string $x$ in time $t$, whose position is $n$ in the lexicographic enumeration. This means that it will be the value of our time step $i$: $t=i/2^n=i/2^{2^{l(p)}}$. Therefore, $i=2^{2^{l(p)}}t$, which doesn't match the claim $2^{l(p)+1}t$.

In a different description, the execution is done in phases such that the first $i$ programs are run for 1 step at phase $i$. Therefore, before phase $i$, the $n$th program will have been executed $i-n$ times. We require the $n$th program to be executed $t=i-n$ times. Then, we get $i=2^{l(p)}+t$, which is the number of phases. The number of time steps to get to phase $i$ is $i^{2}/2$ (the area of the triangle). Hence we get $\left(2^{l(p)}+t\right)^{2}/2$, which is much larger than $2^{l(p)+1}t$.

Looking at the expression $2^{l(p)+1}t$ it looks like every program up to length $l(p)$ is executed for exactly $t$ time steps. But I thought, Levin search allocates execution time such that shorter programs are favoured?

Where is my mistake? Any help is greatly appreciated.

• Have you tried looking at Levin's original paper? It's apparently only two pages long. Also, Scholarpedia could be wrong. The important thing is that the simulation only has a multiplicative overhead. The exact constant ($2^{l(p)}$ or $2^{2^{l(p)}}$) is not so important. – Yuval Filmus May 7 '16 at 10:21
• The original algorithm of Levin, as well as the best known modern equivalent (due to the author), are described in a technical report of Marcus Hutter titled "The Fastest and Shortest Algorithm for All Well-Defined Problems". – Yuval Filmus May 7 '16 at 10:23
• I am aware of that paper, and I have looked into many descriptions of Levin Search and it just doesn't make sense to me. For example, Hutter writes “a time fraction $2^{-l(p)}$ is devoted to execute $p$”. What do we expect then? If a time $t$ has been devoted to p, then $t=t_{0}2^{-l(p)}$. Then, for a shorter program of length k the devoted time is $t_{0}2^{-k}=2^{l(p)-k}t$. The total time needed to arrive at $p$ is the sum of this number over $2^{l(p)+1}$ programs shorter than $l(p)$. Without even diving into details it is clear that the result will be much higher than $2^{l(p)}t$. – Don Arturo May 7 '16 at 10:39
• – Don Arturo May 7 '16 at 12:13

You do not need dovetailing when $$t(n)$$ can be quickly computed. Also, note that $$l$$ is an absolute CONSTANT. The only function is $$t$$ but the variable is the input string length $$n$$, hence we write $$t(n)$$.
So when you are given an input string $$x$$ of length $$|x|=n$$, Levin search just does as follows:
Knowing an upperbound for the fixed length of $$p$$ (i.e. $$l$$), quickly compute the upperbound for runtime $$t(n)$$, for each program represented by a tring $$M$$ of length $$|M|=\leq l$$, simulate $$M$$ on input $$x$$.
Here is the part that is TOTALLY missing from your post: If some $$M$$ outputs a result $$s$$, use the verifier for the language to see if $$s$$ is the string being searched for.
This is only possible if the language is in $$NP$$.