Implicit measurements of dynamic complexity properties and splittings of speedable sets

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)
DOI 10.2307/2586618
 Save to my reading list
Follow the author(s)
My bibliography
Export citation
Find it on Scholar
Edit this record
Mark as duplicate
Revision history
Request removal from index
Download options
Our Archive

Upload a copy of this paper     Check publisher's policy     Papers currently archived: 27,215
Through your library
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.

Add more references

Citations of this work BETA

No citations found.

Add more citations

Similar books and articles
On Complexity Properties of Recursively Enumerable Sets.M. Blum & I. Marques - 1973 - Journal of Symbolic Logic 38 (4):579-593.
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.
Computability Results Used in Differential Geometry.Barbara F. Csima & Robert I. Soare - 2006 - Journal of Symbolic Logic 71 (4):1394 - 1410.

Monthly downloads

Added to index


Total downloads

16 ( #296,373 of 2,164,542 )

Recent downloads (6 months)

1 ( #347,971 of 2,164,542 )

How can I increase my downloads?

My notes
Sign in to use this feature

There  are no threads in this forum
Nothing in this forum yet.

Other forums