Deep classes

Bulletin of Symbolic Logic 22 (2):249-286 (2016)
  Copy   BIBTEX


A set of infinite binary sequences ${\cal C} \subseteq 2$ℕ is negligible if there is no partial probabilistic algorithm that produces an element of this set with positive probability. The study of negligibility is of particular interest in the context of ${\rm{\Pi }}_1^0 $ classes. In this paper, we introduce the notion of depth for ${\rm{\Pi }}_1^0 $ classes, which is a stronger form of negligibility. Whereas a negligible ${\rm{\Pi }}_1^0 $ class ${\cal C}$ has the property that one cannot probabilistically compute a member of ${\cal C}$ with positive probability, a deep ${\rm{\Pi }}_1^0 $ class ${\cal C}$ has the property that one cannot probabilistically compute an initial segment of a member of ${\cal C}$ with high probability. That is, the probability of computing a length n initial segment of a deep ${\rm{\Pi }}_1^0 $ class converges to 0 effectively in n.We prove a number of basic results about depth, negligibility, and a variant of negligibility that we call tt-negligibility. We provide a number of examples of deep ${\rm{\Pi }}_1^0 $ classes that occur naturally in computability theory and algorithmic randomness. We also study deep classes in the context of mass problems, examine the relationship between deep classes and certain lowness notions in algorithmic randomness, and establish a relationship between members of deep classes and the amount of mutual information with Chaitin’s Ω.



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

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

DEEP ${\rm{\Pi }}_1^0 $ CLASSES.Laurent Bienvenu & Christopher P. Porter - 2016 - Bulletin of Symbolic Logic 22 (2):249-286.
Computability in uncountable binary trees.Reese Johnston - 2019 - Journal of Symbolic Logic 84 (3):1049-1098.
When an Event Makes a Difference.Massimiliano Amarante & Fabio Maccheroni - 2006 - Theory and Decision 60 (2-3):119-126.


Added to PP

19 (#190,912)

6 months
6 (#1,472,471)

Historical graph of downloads
How can I increase my downloads?

Author's Profile

Christopher Porter
Drake University

Citations of this work

No citations found.

Add more citations

References found in this work

Randomness and lowness notions via open covers.Laurent Bienvenu & Joseph S. Miller - 2012 - Annals of Pure and Applied Logic 163 (5):506-518.
Complex tilings.Bruno Durand, Leonid A. Levin & Alexander Shen - 2008 - Journal of Symbolic Logic 73 (2):593-613.
The upward closure of a perfect thin class.Rod Downey, Noam Greenberg & Joseph S. Miller - 2008 - Annals of Pure and Applied Logic 156 (1):51-58.
Exact Expressions for Some Randomness Tests.Peter Gács - 1980 - Mathematical Logic Quarterly 26 (25-27):385-394.

Add more references