Book contents
- Frontmatter
- Contents
- Preface
- Participants Photograph
- Generic absoluteness for Σ1 formulas and the continuum problem
- Axioms of generic absoluteness
- Generalised dynamic ordinals — universal measures for implicit computational complexity
- The Worm principle
- “One is a lonely number”: logic and communication
- Computable versions of the uniform boundedness theorem
- Symmetry of the universal computable function: A study of its automorphisms, homomorphisms and isomorphic embeddings
- PCF theory and Woodin cardinals
- Embedding finite lattices into the computably enumerable degrees — a status survey
- Dimension theory inside a homogeneous model
- Reals which compute little
- Bisimulation invariance and finite models
- Choice principles in constructive and classical set theories
- Ash's theorem for abstract structures
- Martin-Löf random and PA-complete sets
- Learning and computing in the limit
- References
Martin-Löf random and PA-complete sets
Published online by Cambridge University Press: 31 March 2017
- Frontmatter
- Contents
- Preface
- Participants Photograph
- Generic absoluteness for Σ1 formulas and the continuum problem
- Axioms of generic absoluteness
- Generalised dynamic ordinals — universal measures for implicit computational complexity
- The Worm principle
- “One is a lonely number”: logic and communication
- Computable versions of the uniform boundedness theorem
- Symmetry of the universal computable function: A study of its automorphisms, homomorphisms and isomorphic embeddings
- PCF theory and Woodin cardinals
- Embedding finite lattices into the computably enumerable degrees — a status survey
- Dimension theory inside a homogeneous model
- Reals which compute little
- Bisimulation invariance and finite models
- Choice principles in constructive and classical set theories
- Ash's theorem for abstract structures
- Martin-Löf random and PA-complete sets
- Learning and computing in the limit
- References
Summary
Abstract. A set A is Martin-Lof random iff the class ﹛A﹜ does not have measure 0. A set A is PA-complete if one can compute relative to A a consistent and complete extension of Peano Arithmetic. It is shown that every Martin-Lof random set either permits to solve the halting problem K or is not PA-complete. This result implies a negative answer to the question of Ambos-Spies and Kucera whether there is a Martin-Lof random set not above K which is also PA-complete.
Introduction. Gacs [3] and Kucera [7, 8] showed that every set can be computed relative to a Martin-Lof random set. In particular, for every set B there is a Martin-Lof random set A such that where K is the halting problem. A can even be chosen such that the reduction from B to A is a weak truth-table reduction, Merkle and Mihailovic [12] give a simplified proof for this fact.
A natural question is whether it is necessary to go up to the degree of in order to find the random set A. Martin-L of random sets can be found below every set which is PA-complete, so there are Martin-Lof random sets in low and in hyperimmune-free Turing degrees. A set A is called PA-complete if one can compute relative to A a complete and consistent extension of the set of first-order formulas provable in Peano Arithmetic. An easier and equivalent definition of being PA-complete is to say that given any partial-recursive and ﹛0, 1﹜-valued function, one can compute relative to A a total extension Ψ of. One can of course choose Ψ such that also Ψ is ﹛0, 1﹜-valued.
Extending all possible ﹛0, 1﹜-valued partial-recursive functions is as difficult as to compute a ﹛0, 1﹜-valued DNR function. A diagonally nonrecursive (DNR) function f satisfies whenever is defined.
- Type
- Chapter
- Information
- Logic Colloquium '02 , pp. 342 - 348Publisher: Cambridge University PressPrint publication year: 2006
References
- 6
- Cited by