# 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. May 7, 2016 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". May 7, 2016 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$. May 7, 2016 at 10:39
• May 7, 2016 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$$.

Consider the following schedule:

for k = 1, 2, 3, 4...:
T_k = 2^k
for all programs p ordered by increasing length:
if floor(T_k 2^{-l(p)}) > 0:  # equiv to: if l(p) ≤ k
run p for T_k 2^{-l(p)} steps  # = 2^{k-l(p)}
if p has halted (on its own) and the output string matches the target:
return p
else:
break # no longer program will run either


By Kraft's inequality, we know that $$\sum_p 2^{-\ell(p)} \leq 1$$. Thus, at each phase $$k$$, the total amount of computation for this phase is $$\sum_p \lfloor T_k 2^{-\ell(p)}\rfloor \leq T_k$$. (Note that $$\lfloor T_K 2^{-\ell(q)}\rfloor = T_K 2^{-\ell(q)}$$ when $$\lfloor T_K 2^{-\ell(q)}\rfloor > 0$$.)

Now, suppose that a program $$q$$ requires $$\tau$$ steps to produce the target output. Then the first phase $$K$$ where $$q$$ receives sufficient allocated time, that is, at which $$T_K 2^{-\ell(q)} \geq \tau$$ such that $$q$$ halts is $$K = \min \{K : 2^{K}2^{-\ell(q)}\geq \tau\} = \lceil \ell(q)+\log_2 \tau \rceil$$. It follows that $$T_K \leq 2\tau 2^{\ell(q)}$$.

Finally, the total amount of computation spent until $$q$$ halts is at most $$\sum_{k=1}^K T_k = 2 T_K -2 \leq 4\tau2^{\ell(q)}$$.