Journal of Symbolic Logic 64 (3):1037-1064 (1999)
|Abstract||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)|
|Through your library||Configure|
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 downloads2 ( #245,680 of 722,764 )
Recent downloads (6 months)0
How can I increase my downloads?