On recursive bounds for the exceptional values in speed-up

DOI10.1016/0304-3975(94)00050-6zbMath0807.03026OpenAlexW2039986919WikidataQ57001783 ScholiaQ57001783MaRDI QIDQ1334675

Douglas S. Bridges, Cristian S. Calude

Publication date: 25 September 1994

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0304-3975(94)00050-6

zbMATH Keywords

exceptional valuesBlum speed-updouble recursion theorem

Mathematics Subject Classification ID

Complexity of computation (including implicit computational complexity) (03D15) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Related Items

Effective category and measure in abstract complexity theory, Effective category and measure in abstract complexity theory

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• A note on A.E. h-complex functions
• Theories of computational complexity
• Theory of Formal Systems. (AM-47)
• Easy Constructions in Complexity Theory: Gap and Speed-Up Theorems
• RECURSIVE BAIRE CLASSIFICATION AND SPEEDABLE FUNCTIONS
• A Machine-Independent Theory of the Complexity of Recursive Functions
• On the size of machines
• An Overview of the Theory of Computational Complexity
• Computational speed-up by effective operators
• On size vs. efficiency for programs admitting speed-ups