3
$\begingroup$

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

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Andrew MacFie Oct 11 '15 at 0:24
4
$\begingroup$

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

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