The importance of Π1 0 classes in effective randomness

, &
Journal of Symbolic Logic 75 (1):387-400 (2010)
  Copy   BIBTEX

Abstract

We prove a number of results in effective randomness, using methods in which Π⁰₁ classes play an essential role. The results proved include the fact that every PA Turing degree is the join of two random Turing degrees, and the existence of a minimal pair of LR degrees below the LR degree of the halting problem.

Categories

Keywords

Reprint years

DOI

10.2178/jsl/1264433928

Links

PhilArchive



    Upload a copy of this work     Papers currently archived: 93,127

External links

Setup an account with your affiliations in order to access resources via your University's proxy server

Through your library

My notes

Similar books and articles

George Barmpalias, Andrew E. M. Lewis and Keng Meng NG. The importance of Π 0 1 classes in effective randomness. The Journal of Symbolic Logic, vol. 75 (2010), pp. 387–400. - George Barmpalias, Andrew E. M. Lewis and Frank Stephan. Π 0 1 classes, LR degrees and Turing degrees. Annals of Pure and Applied Logic, vol. 156 (2008), pp. 21–38. - Antonin Kučera. Measure, Π 0 1 classes and complete extensions of PA. Recursion Theory Week (Oberwofach, 1984). Lecture Notes in Mathematics, vol. 1141. Springer, Berlin, 1985, pp. 245–259. - Frank Stephan. Martin-Löf randomness and PA complete sets. Logic Colloquium '02. Lecture Notes in Logic, vol. 27, Association for Symbolic Logic, La Jolla, CA, 2006, pp. 342–348. [REVIEW]Douglas Cenzer - 2012 - Bulletin of Symbolic Logic 18 (3):409-412.
Π 1 0 classes, L R degrees and Turing degrees.George Barmpalias, Andrew E. M. Lewis & Frank Stephan - 2008 - Annals of Pure and Applied Logic 156 (1):21-38.
Randomness, Lowness and Degrees.George Barmpalias, Andrew E. M. Lewis & Mariya Soskova - 2008 - Journal of Symbolic Logic 73 (2):559 - 577.
Benign cost functions and lowness properties.Noam Greenberg & André Nies - 2011 - Journal of Symbolic Logic 76 (1):289 - 312.
Mass problems and randomness.Stephen G. Simpson - 2005 - Bulletin of Symbolic Logic 11 (1):1-27.
Randomness, relativization and Turing degrees.André Nies, Frank Stephan & Sebastiaan A. Terwijn - 2005 - Journal of Symbolic Logic 70 (2):515-535.
On the interplay between effective notions of randomness and genericity.Laurent Bienvenu & Christopher P. Porter - 2019 - Journal of Symbolic Logic 84 (1):393-407.
The Turing degrees below generics and randoms.Richard A. Shore - 2014 - Journal of Symbolic Logic 79 (1):171-178.
Van Lambalgen's Theorem and High Degrees.Johanna N. Y. Franklin & Frank Stephan - 2011 - Notre Dame Journal of Formal Logic 52 (2):173-185.
Turing degrees and randomness for continuous measures.Mingyang Li & Jan Reimann - 2024 - Archive for Mathematical Logic 63 (1):39-59.

Analytics

Added to PP
2010-09-12

Downloads
58 (#284,128)

6 months
9 (#355,374)

Historical graph of downloads
How can I increase my downloads?

Author's Profile

Andrew Lewis
Graduate Theological Union

Citations of this work

A Hierarchy of Computably Enumerable Degrees.Rod Downey & Noam Greenberg - 2018 - Bulletin of Symbolic Logic 24 (1):53-89.
Low upper bounds in the LR degrees.David Diamondstone - 2012 - Annals of Pure and Applied Logic 163 (3):314-320.
Algorithmic randomness and measures of complexity.George Barmpalias - 2013 - Bulletin of Symbolic Logic 19 (3):318-350.

View all 7 citations / Add more citations

References found in this work

Classical Recursion Theory.Peter G. Hinman - 2001 - Bulletin of Symbolic Logic 7 (1):71-73.
Calibrating randomness.Rod Downey, Denis R. Hirschfeldt, André Nies & Sebastiaan A. Terwijn - 2006 - Bulletin of Symbolic Logic 12 (3):411-491.
Almost everywhere domination and superhighness.Stephen G. Simpson - 2007 - Mathematical Logic Quarterly 53 (4):462-482.
Mass problems and hyperarithmeticity.Joshua A. Cole & Stephen G. Simpson - 2007 - Journal of Mathematical Logic 7 (2):125-143.

View all 6 references / Add more references