On recursive bounds for the exceptional values in speed-up
type: Item
instance of: scholarly article
title: On recursive bounds for the exceptional values in speed-up
zbMATH Open document ID: 0807.03026
DOI: 10.1016/0304-3975(94)00050-6
published in: Theoretical Computer Science
publication date: 1994-09-25T00:00:00Z
review text: 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.
reviewed by: William Gasarch
Mathematics Subject Classification ID: 03D15
Mathematics Subject Classification ID: 68Q15
zbMATH DE Number: 643683
zbMATH Keywords: Blum speed-up
zbMATH Keywords: exceptional values
zbMATH Keywords: double recursion theorem
Wikidata QID: Q57001783
author: Douglas Bridges
author: Cristian S. Calude
MaRDI profile type: Publication
full work available at URL: 0304-3975(94)00050-6
OpenAlex ID: W2039986919
cites work: A Machine-Independent Theory of the Complexity of Recursive Functions
cites work: On the size of machines
cites work: Q4285775
cites work: Theories of computational complexity
cites work: RECURSIVE BAIRE CLASSIFICATION AND SPEEDABLE FUNCTIONS
cites work: A note on A.E. h-complex functions
cites work: An Overview of the Theory of Computational Complexity
cites work: On size vs. efficiency for programs admitting speed-ups
cites work: Q5592246
cites work: Q4153600
cites work: Computational speed-up by effective operators
cites work: Q3680279
cites work: Q5680997
cites work: Q4053629
cites work: Theory of Formal Systems. (AM-47)
cites work: Q4088272
cites work: Easy Constructions in Complexity Theory: Gap and Speed-Up Theorems
DBLP publication ID: journals/tcs/BridgesC94
description: scientific article; zbMATH DE number 643683