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)|
References found in this work BETA
Splitting Theorems in Recursion Theory.Rod Downey & Michael Stob - 1993 - Annals of Pure and Applied Logic 65 (1):1-106.
Two Notes on Vector Spaces with Recursive Operations.J. C. E. Dekker - 1971 - Notre Dame Journal of Formal Logic 12 (3):329-334.
On Speedable and Levelable Vector Spaces.Frank A. Bäuerle & Jeffrey B. Remmel - 1994 - Annals of Pure and Applied Logic 67 (1-3):61-112.
Citations of this work BETA
No citations found.
Similar books and articles
Splittings of Effectively Speedable Sets and Effectively Levelable Sets.Roland SH Omanadze - 2004 - Journal of Symbolic Logic 69 (1):143-158.
On Complexity Properties of Recursively Enumerable Sets.M. Blum & I. Marques - 1973 - Journal of Symbolic Logic 38 (4):579-593.
Splitting Theorems for Speed-Up Related to Order of Enumeration.A. M. Dawes - 1982 - Journal of Symbolic Logic 47 (1):1-7.
Recursive Constructions in Topological Spaces.Iraj Kalantari & Allen Retzlaff - 1979 - Journal of Symbolic Logic 44 (4):609-625.
Computational Complexity, Speedable and Levelable Sets.Robert I. Soare - 1977 - Journal of Symbolic Logic 42 (4):545-563.
Definable Incompleteness and Friedberg Splittings.Russell Miller - 2002 - Journal of Symbolic Logic 67 (2):679-696.
On Subcreative Sets and S-Reducibility.John T. Gill Iii & Paul H. Morris - 1974 - Journal of Symbolic Logic 39 (4):669 - 677.
Codable Sets and Orbits of Computably Enumerable Sets.Leo Harrington & Robert I. Soare - 1998 - Journal of Symbolic Logic 63 (1):1-28.
Computability Results Used in Differential Geometry.Barbara F. Csima & Robert I. Soare - 2006 - Journal of Symbolic Logic 71 (4):1394 - 1410.
Definability, Automorphisms, and Dynamic Properties of Computably Enumerable Sets.Leo Harrington & Robert I. Soare - 1996 - Bulletin of Symbolic Logic 2 (2):199-213.
Added to index2009-01-28
Total downloads16 ( #296,373 of 2,164,542 )
Recent downloads (6 months)1 ( #347,971 of 2,164,542 )
How can I increase my downloads?