<p>Using a pairing function we can allow $s$ to be defined on $\mathbb{N}^2$. Let $s(i,j)=1$ if and only if the $i$'th program $P_i$ halts in at most $2^j$ steps. Then $V$ can test whether $P_i$ halts by testing $s(i,1),s(i,2),\dots$. If $U(P_i)$ halts in at most $2^j$ steps then $V(P_i)$ halts in about $(i+j)^2$ time, assuming the pairing function is sensible. This means that if $U(P)$ halts in $t$ steps then $V(P)$ halts in about
$$(2^{|P|}+\log t)^2\leq \max(4\cdot 2^{2|P|},4(\log t)^2)$$
steps. But $(\log t)^2=o(t)$.</p>

CC BY-SA 3.0
2012-12-03T14:40:55.770Z
2012-12-03T15:04:42.730Z
2012-12-03T15:04:42.730Z
Colin McQuillan
<p>A universal computer is a program that can execute any other program. It is interesting to ask whether there are "booster" computers that execute programs faster than they execute "on their own". In the simplest sense of the question, the answer is negative, as can be seen by the following argument.</p>

<p>Suppose $V$ is a universal computer. Consider the following program $P$: "Run $V$ on my own source code. If it halts in less than $n$ steps, produce output which is different than the output of $V(P)$. Otherwise produce the output '0' (say)". It is clear that $V$ will take at least $n$ steps to execute $P$ and $P$ will execute in approximately $n$ steps on its own. So $P$ and $V(P)$ take approximately the same time.</p>

<p>However, what happens if we allow a pre-computed cache of arbitrary size? Formally, we consider a universal Turing machine with the addition of a special read-only tape on which an infinite computable bit-string $s$ is written in the initial state. Fix $U$ an "ordinary" universal computer program, i.e. $U$ doesn't use the special tape. The question is then </p>

<blockquote>
  <p>Can we construct $V$ a program (using the special tape) and $s$ as above s.t. for any $U$-program $P$ if $U(P)$ halts in $t$ steps then $V(P)$ halts in at most $max(f(t), g(|P|))$ steps where $f \in o(t)$ and $g$ is computable?</p>
</blockquote>

<p>Repeating the self-referential construction above only yields that the time complexity of $s$ has to be at least $f^{-1}$</p>

CC BY-SA 3.0
2015-10-11T00:24:46.223Z
Interesting... If we replace $n$ with some rapidly growing $a_n$ in the definition of $P$, as $n$ varies we get a sequence of inputs $P$ where the output is $0$ but on which $V$ takes approx. $a_n$ steps. This means $V$ can perform arbitrarily worse on this particular set of inputs than the algorithm that just prints $0$ and halts.
Andrew
<cc.complexity-theory><time-complexity><universal-computation><advice-and-nonuniformity>
Speed-up of universal computation by caching
Vanessa
# Speed-up of universal computation by caching

(Asked by: username_0 on 2012-12-03)

A universal computer is a program that can execute any other program. It is interesting to ask whether there are "booster" computers that execute programs faster than they execute "on their own". In the simplest sense of the question, the answer is negative, as can be seen by the following argument.

Suppose $V$ is a universal computer. Consider the following program $P$: "Run $V$ on my own source code. If it halts in less than $n$ steps, produce output which is different than the output of $V(P)$. Otherwise produce the output '0' (say)". It is clear that $V$ will take at least $n$ steps to execute $P$ and $P$ will execute in approximately $n$ steps on its own. So $P$ and $V(P)$ take approximately the same time.

However, what happens if we allow a pre-computed cache of arbitrary size? Formally, we consider a universal Turing machine with the addition of a special read-only tape on which an infinite computable bit-string $s$ is written in the initial state. Fix $U$ an "ordinary" universal computer program, i.e. $U$ doesn't use the special tape. The question is then

> Can we construct $V$ a program (using the special tape) and $s$ as above s.t. for any $U$-program $P$ if $U(P)$ halts in $t$ steps then $V(P)$ halts in at most $max(f(t), g(|P|))$ steps where $f \in o(t)$ and $g$ is computable?

Repeating the self-referential construction above only yields that the time complexity of $s$ has to be at least $f^{-1}$

**Tags:** cc.complexity-theory, time-complexity, universal-computation, advice-and-nonuniformity
> **Comments:**
> **username_1**: Interesting... If we replace $n$ with some rapidly growing $a_n$ in the definition of $P$, as $n$ varies we get a sequence of inputs $P$ where the output is $0$ but on which $V$ takes approx. $a_n$ steps. This means $V$ can perform arbitrarily worse on this particular set of inputs than the algorithm that just prints $0$ and halts.  

---

## 1 answers

### Answer by username_2 on 2012-12-03. Score: 4 | Accepted answer

Using a pairing function we can allow $s$ to be defined on $\mathbb{N}^2$. Let $s(i,j)=1$ if and only if the $i$'th program $P\_i$ halts in at most $2^j$ steps. Then $V$ can test whether $P\_i$ halts by testing $s(i,1),s(i,2),\dots$. If $U(P\_i)$ halts in at most $2^j$ steps then $V(P\_i)$ halts in about $(i+j)^2$ time, assuming the pairing function is sensible. This means that if $U(P)$ halts in $t$ steps then $V(P)$ halts in about
$$(2^{|P|}+\log t)^2\leq \max(4\cdot 2^{2|P|},4(\log t)^2)$$
steps. But $(\log t)^2=o(t)$.


---

