Take the 2-minute tour ×
Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. It's 100% free, no registration required.

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

share|improve this question
add comment

1 Answer 1

up vote 3 down vote accepted

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

share|improve this answer
Thank you for your answer! –  Squark Dec 3 '12 at 18:21
add comment

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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