5
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Yuval Filmus May 7 '16 at 10:21
  • $\begingroup$ 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". $\endgroup$ – Yuval Filmus May 7 '16 at 10:23
  • 1
    $\begingroup$ 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$. $\endgroup$ – Don Arturo May 7 '16 at 10:39
  • $\begingroup$ Let us continue this discussion in chat. $\endgroup$ – Don Arturo May 7 '16 at 12:13
1
$\begingroup$

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$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.