Speed-up of universal computation by caching

Question

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

Answer 1

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