Highness properties close to PA completeness

Suppose we are given a computably enumerable object. We are interested in the strength of oracles that can compute an object that approximates this c.e. object. It turns out that in many cases arising from algorithmic randomness or computable analysis, the resulting highness property is either close...

Full description

Saved in:
Bibliographic Details
Published in:Israel journal of mathematics 2021-09, Vol.244 (1), p.419-465
Main Authors: Greenberg, Noam, Miller, Joseph S., Nies, André
Format: Article
Language:English
Subjects:
Algebra
Analysis
Applications of Mathematics
Completeness
Computation
Group Theory and Generalizations
Lower bounds
Martingales
Mathematical and Computational Physics
Mathematics
Mathematics and Statistics
Theoretical
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:Suppose we are given a computably enumerable object. We are interested in the strength of oracles that can compute an object that approximates this c.e. object. It turns out that in many cases arising from algorithmic randomness or computable analysis, the resulting highness property is either close to, or equivalent to being PA complete. We examine, for example, majorizing a c.e. martingale by an oracle-computable martingale, computing lower bounds for two variants of Kolmogorov complexity, and computing a subtree of positive measure with no dead-ends of a given ∏ 1 0 tree of positive measure. We separate PA completeness from the latter property, called the continuous covering property. We also separate the corresponding principles in reverse mathematics.
ISSN:0021-2172
1565-8511
DOI:10.1007/s11856-021-2200-7