Mathematical Structures in Computer Science · 2006 · 17 citations · 7 references
Natural SciencesComputer ScienceMathematicsProbability TheorySet TheoryTheory Of ComputationAxiomatic Set TheoryComputability TheoryTuring CompletenessTuring DegreesUndecidability
Lipschitz continuity is used as a tool for analysing the relationship between incomputability and randomness. We present a simpler proof of one of the major results in this area – the theorem of Yu and Ding, which states that there exists no cl-complete c.e. real – and go on to consider the global theory. The existential theory of the cl degrees is decidable, but this does not follow immediately by the standard proof for classical structures, such as the Turing degrees, since the cl degrees are a structure without join. We go on to show that strictly below every random cl degree there is another random cl degree. Results regarding the phenomenon of quasi-maximality in the cl degrees are also presented.
7
Recursively enumerable sets and degrees
Robert I. Soare · Bulletin of the American Mathematical Society · 1978 · 1.6K citations · Full text
Algorithmic Information Theory
Gregory J. Chaitin · IBM Journal of Research and Development · 1977 · 1K citations
Randomness, Computability, and Density
Rod Downey, Denis R. Hirschfeldt, André Nies · SIAM Journal on Computing · 2002 · 50 citations
Computability Theory and Differential Geometry
Robert I. Soare · Bulletin of Symbolic Logic · 2004 · 41 citations · Full text