id: 00643683
dt: j
an: 00643683
au: Bridges, Douglas; Calude, Cristian
ti: On recursive bounds for the exceptional values in speed-up.
so: Theor. Comput. Sci. 132, No.1-2, 387-394 (1994).
py: 1994
pu: Elsevier Science Publishers, Amsterdam
la: EN
cc: 
ut: Blum speed-up; exceptional values; double recursion theorem
ci: 
li: doi:10.1016/0304-3975(94)00050-6
ab: We state Blum’s original speed-up theorem in extremely concrete terms.
    Let $f$ be any recursive function. We think of $f$ as being
    slow-growing (e.g., $f(n) = \log n$). There exists a recursive set $A$
    such that the following occurs. For all $i$ such that $M\sb i$ (Turing
    machine $i$) accepts $A$ in $\text{DTIME}(T(n))$, there exists $j$ such
    that $M\sb j$ accepts $A$ in $\text{DTIME}(f(T(n)))$ steps on all but a
    finite number of values (called ‘exceptional values’). The original
    proof was nonconstructive in that you cannot obtain $j$ from $i$. The
    paper under review asks the following two questions: (1) Given $i$, can
    you effectively find a bound on the exceptional values? (2) Given $j$,
    can you effectively find a bound on the exceptional values? This paper
    proves that for question (1) the answer is NO, but for question (2) the
    answer is YES. The proof of the NO answer uses the double recursion
    theorem.
rv: W.I.Gasarch (College Park)