Article contents
A random set which only computes strongly jump-traceable c.e. sets
Published online by Cambridge University Press: 12 March 2014
Abstract
We prove that there is a , 1-random set Y such that every computably enumerable set which is computable from Y is strongly jump-traceable.
We also show that for every order function h there is an ω-c.e. random set Y such that every computably enumerable set which is computable from Y is h-jump-traceable. This establishes a correspondence between rates of jump-traceability and computability from ω-c.e. random sets.
- Type
- Research Article
- Information
- Copyright
- Copyright © Association for Symbolic Logic 2011
References
REFERENCES
- 3
- Cited by