Can I read Deep $\Pi^0_1$ Classes on EtoBox?

Deep $\Pi^0_1$ Classes by Bienvenu, Laurent; Porter, Christopher P. is a scholarly article available to read on EtoBox.

What is Deep $\Pi^0_1$ Classes about?

A set of infinite binary sequences $\mathcal{C}\subseteq2^\omega$ 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 $\Pi^0_1$ classes. In this paper, we introduce the notion of depth for $\Pi^0_1$ classes, which is a stronger form of negligibility. Whereas a negligible $\Pi^0_1$ class $\mathcal{C}$ has the property that one cannot probabilistically compute a member of $\mathcal{C}$ with positive probability, a deep $\Pi^0_1$ class $\mathcal{C}$ has the property that one cannot probabilistically compute an initial segment of a member of $\mathcal{C}$ with high probability. That is, the probability of computing a length $n$ initial segment of a deep $\Pi^0_1$ 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 $\mathit{tt}$-negligibility. We also provide a number of examples of deep $\Pi^0_1$ classes that occur naturally in computability theory and algorithmic randomness. We also study deep classes in the context of mass problems, we examine the

Author

Bienvenu, Laurent; Porter, Christopher P.

Published

2014

Language

EN