On recursive bounds for the exceptional values in speed-up (Q1334675): Difference between revisions

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_ i\) (Turing machine \(i\)) accepts \(A\) in \(\text{DTIME}(T(n))\), there exists \(j\) such that \(M_ 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.