David Bourget (Western Ontario)
David Chalmers (ANU, NYU)
Rafael De Clercq
Ezio Di Nucci
Jonathan Jenkins Ichikawa
Jack Alan Reynolds
Learn more about PhilPapers
Journal of Symbolic Logic 64 (3):1037-1064 (1999)
We prove that any speedable computably enumerable set may be split into a disjoint pair of speedable computably enumerable sets. This solves a longstanding question of J.B. Remmel concerning the behavior of computably enumerable sets in Blum's machine independent complexity theory. We specify dynamic requirements and implement a novel way of detecting speedability-by embedding the relevant measurements into the substage structure of the tree construction. Technical difficulties in satisfying the dynamic requirements lead us to implement "local" strategies that only look down the tree. The (obvious) problems with locality are then resolved by placing an isomorphic copy of the entire priority tree below each strategy (yielding a self-similar tree). This part of the construction could be replaced by an application of the Recursion Theorem, but shows how to achieve the same effect with a more direct construction
|Keywords||No keywords specified (fix it)|
|Categories||categorize this paper)|
Setup an account with your affiliations in order to access resources via your University's proxy server
Configure custom proxy (use this if your affiliation does not provide a proxy)
|Through your library|
References found in this work BETA
Rod Downey & Michael Stob (1993). Splitting Theorems in Recursion Theory. Annals of Pure and Applied Logic 65 (1):1-106.
J. C. E. Dekker (1971). Two Notes on Vector Spaces with Recursive Operations. Notre Dame Journal of Formal Logic 12 (3):329-334.
Frank A. Bäuerle & Jeffrey B. Remmel (1994). On Speedable and Levelable Vector Spaces. Annals of Pure and Applied Logic 67 (1-3):61-112.
Citations of this work BETA
No citations found.
Similar books and articles
Roland SH Omanadze (2004). Splittings of Effectively Speedable Sets and Effectively Levelable Sets. Journal of Symbolic Logic 69 (1):143-158.
M. Blum & I. Marques (1973). On Complexity Properties of Recursively Enumerable Sets. Journal of Symbolic Logic 38 (4):579-593.
A. M. Dawes (1982). Splitting Theorems for Speed-Up Related to Order of Enumeration. Journal of Symbolic Logic 47 (1):1-7.
Iraj Kalantari & Allen Retzlaff (1979). Recursive Constructions in Topological Spaces. Journal of Symbolic Logic 44 (4):609-625.
Robert I. Soare (1977). Computational Complexity, Speedable and Levelable Sets. Journal of Symbolic Logic 42 (4):545-563.
Russell Miller (2002). Definable Incompleteness and Friedberg Splittings. Journal of Symbolic Logic 67 (2):679-696.
John T. Gill Iii & Paul H. Morris (1974). On Subcreative Sets and S-Reducibility. Journal of Symbolic Logic 39 (4):669 - 677.
Leo Harrington & Robert I. Soare (1998). Codable Sets and Orbits of Computably Enumerable Sets. Journal of Symbolic Logic 63 (1):1-28.
Barbara F. Csima & Robert I. Soare (2006). Computability Results Used in Differential Geometry. Journal of Symbolic Logic 71 (4):1394 - 1410.
Leo Harrington & Robert I. Soare (1996). Definability, Automorphisms, and Dynamic Properties of Computably Enumerable Sets. Bulletin of Symbolic Logic 2 (2):199-213.
Added to index2009-01-28
Total downloads15 ( #253,346 of 1,935,154 )
Recent downloads (6 months)1 ( #434,530 of 1,935,154 )
How can I increase my downloads?