Speed-up of universal computation by caching
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)$.