Arithmetic complexity via effective names for random sequences

DOI10.1145/2287718.2287724MaRDI QIDQ2946673zbMATH OpenOpenAlexWikidataFDO

Authors Bjørn Kjos-Hanssen, Jason Teutsch, Frank Stephan

Publication date 17 September 2015

Published in ACM Transactions on Computational Logic (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1008.4825

zbMATH Keywords

Schnorr randomnesscomputable randomnessarithmetical hierarchy

Mathematics Subject Classification ID

Algorithmic randomness and dimension (03D32) Recursively (computably) enumerable sets and degrees (03D25)

Abstract: We investigate enumerability properties for classes of sets which permit recursive, lexicographically increasing approximations, or left-r.e. sets. In addition to pinpointing the complexity of left-r.e. Martin-L"{o}f, computably, Schnorr, and Kurtz random sets, weakly 1-generics and their complementary classes, we find that there exist characterizations of the third and fourth levels of the arithmetic hierarchy purely in terms of these notions. More generally, there exists an equivalence between arithmetic complexity and existence of numberings for classes of left-r.e. sets with shift-persistent elements. While some classes (such as Martin-L"{o}f randoms and Kurtz non-randoms) have left-r.e. numberings, there is no canonical, or acceptable, left-r.e. numbering for any class of left-r.e. randoms. Finally, we note some fundamental differences between left-r.e. numberings for sets and reals.

Recommendations

• Numberings and randomness
• Computer Science Logic
• The arithmetical complexity of dimension and randomness
• The Kolmogorov complexity of random reals
• Arithmetical Measure

Cited in

(7)

• On infinite direct sums of minimal numberings of functional families
• Things that can be made into themselves
• Numberings and randomness
• Reductions between types of numberings
• Closed left-r.e. sets
• Selection by recursively enumerable sets
• Randomness below complete theories of arithmetic

This page was built for publication: Arithmetic complexity via effective names for random sequences

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2946673)