6
$\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$
4
  • $\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$ May 7, 2016 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$ May 7, 2016 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, 2016 at 10:39
  • $\begingroup$ Let us continue this discussion in chat. $\endgroup$
    – Don Arturo
    May 7, 2016 at 12:13

2 Answers 2

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$
1
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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