ON RECURSIVE BOUNDS FOR THE EXCEPTIONAL VALUES IN SPEED-UP

Authors
BRIDGES D CALUDE C
Citation
D. Bridges et C. Calude, ON RECURSIVE BOUNDS FOR THE EXCEPTIONAL VALUES IN SPEED-UP, Theoretical computer science, 132(1-2), 1994, pp. 387-394
Citations number
19
Categorie Soggetti
Computer Sciences","Computer Science Theory & Methods
Journal title
Theoretical computer science → ACNP
ISSN journal
03043975
Volume
132
Issue
1-2
Year of publication
1994
Pages
387 - 394
Database
ISI
SICI code
0304-3975(1994)132:1-2<387:ORBFTE>2.0.ZU;2-K
Abstract
This note contains a proof that there is no recursive function of the initial index that gives a bound for the exceptional values in Blum sp eed-up, but that there is a recursive bounding function of the speed-u p index. All the proofs given are constructive.