On the interplay between effective notions of randomness and genericity

Journal of Symbolic Logic 84 (1):393-407 (2019)
  Copy   BIBTEX

Abstract

In this paper, we study the power and limitations of computing effectively generic sequences using effectively random oracles. Previously, it was known that every 2-random sequence computes a 1-generic sequence and every 2-random sequence forms a minimal pair in the Turing degrees with every 2-generic sequence. We strengthen these results by showing that every Demuth random sequence computes a 1-generic sequence and that every Demuth random sequence forms a minimal pair with every pb-generic sequence. Moreover, we prove that for every comeager${\cal G} \subseteq {2^\omega }$, there is some weakly 2-random sequenceXthat computes some$Y \in {\cal G}$, a result that allows us to provide a fairly complete classification as to how various notions of effective randomness interact in the Turing degrees with various notions of effective genericity.

Links

PhilArchive



    Upload a copy of this work     Papers currently archived: 90,616

External links

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

Through your library

Similar books and articles

Randomness and Semimeasures.Laurent Bienvenu, Rupert Hölzl, Christopher P. Porter & Paul Shafer - 2017 - Notre Dame Journal of Formal Logic 58 (3):301-328.
Dynamic notions of genericity and array noncomputability.Benjamin Schaeffer - 1998 - Annals of Pure and Applied Logic 95 (1-3):37-69.
How much randomness is needed for statistics?Bjørn Kjos-Hanssen, Antoine Taveneaux & Neil Thapen - 2014 - Annals of Pure and Applied Logic 165 (9):1470-1483.
Continuous higher randomness.Laurent Bienvenu, Noam Greenberg & Benoit Monin - 2017 - Journal of Mathematical Logic 17 (1):1750004.
Randomness and lowness notions via open covers.Laurent Bienvenu & Joseph S. Miller - 2012 - Annals of Pure and Applied Logic 163 (5):506-518.
On Genericity and Ershov's Hierarchy.Amy Gale & Rod Downey - 2001 - Mathematical Logic Quarterly 47 (2):161-182.
Lowness for genericity.Liang Yu - 2006 - Archive for Mathematical Logic 45 (2):233-238.
Abstract complexity theory and the Δ20 degrees.Benjamin Schaeffer - 2002 - Annals of Pure and Applied Logic 115 (1-3):195-231.
Nullifying randomness and genericity using symmetric difference.Rutger Kuyper & Joseph S. Miller - 2017 - Annals of Pure and Applied Logic 168 (9):1692-1699.
Subclasses of the Weakly Random Reals.Johanna N. Y. Franklin - 2010 - Notre Dame Journal of Formal Logic 51 (4):417-426.

Analytics

Added to PP
2019-03-16

Downloads
15 (#809,553)

6 months
1 (#1,042,085)

Historical graph of downloads
How can I increase my downloads?

Author's Profile

Christopher Porter
Drake University

Citations of this work

The Equivalence of Definitions of Algorithmic Randomness.Christopher Porter - 2021 - Philosophia Mathematica 29 (2):153–194.

Add more citations

References found in this work

Demuth randomness and computational complexity.Antonín Kučera & André Nies - 2011 - Annals of Pure and Applied Logic 162 (7):504-513.
The degrees of bi-hyperhyperimmune sets.Uri Andrews, Peter Gerdes & Joseph S. Miller - 2014 - Annals of Pure and Applied Logic 165 (3):803-811.

Add more references