The random members of a _1⁰ class

DOI10.1007/S00224-017-9824-3MaRDI QIDQ1787954zbMATH OpenOpenAlexFDO

Authors Douglas Cenzer, Christopher P. Porter

Publication date 5 October 2018

Published in Theory of Computing Systems (Search for Journal in Brave)

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

zbMATH Keywords

\({\Pi }_{1}^{0}\) classesalgorithmic randomnesscomputability theoryKolmogorov complexitynon-uniform probability measures

Mathematics Subject Classification ID

Algorithmic randomness and dimension (03D32) Algorithmic information theory (Kolmogorov complexity, etc.) (68Q30)

Abstract: We examine several notions of randomness for elements in a given $P{i}_1^0$ class $mathcalP$. Such an effectively closed subset $mathcalP$ of $2^{o}mega$ may be viewed as the set of infinite paths through the tree $T_{mathcalP}$ of extendible nodes of $mathcalP$, i.e., those finite strings that extend to a member of $mathcalP$, so one approach to defining a random member of $mathcalP$ is to randomly produce a path through $T_{mathcalP}$ using a sufficiently random oracle for advice. In addition, this notion of randomness for elements of $mathcalP$ may be induced by a map from $2^{o}mega$ onto $mathcalP$ that is computable relative to $T_{mathcalP}$, and the notion even has a characterization in term of Kolmogorov complexity. Another approach is to define a relative measure on $mathcalP$ by conditionalizing the Lebesgue measure on $mathcalP$, which becomes interesting if $mathcalP$ has Lebesgue measure 0. Lastly, one can alternatively define a notion of incompressibility for members of $mathcalP$ in terms of the amount of branching at levels of $T_{mathcalP}$. We explore some notions of homogeneity for $P{i}_1^0$ classes, inspired by work of van Lambalgen. A key finding is that in a specific class of sufficiently homogeneous $P{i}_1^0$ classes $mathcalP$, each of these approaches coincides. We conclude with a discussion of random members of $P{i}_1^0$ classes of positive measure.

Recommendations

• Logical Approaches to Computational Barriers
• Deep _1⁰ classes
• \({\Pi}_1^1\)-Martin-Löf random reals as measures of natural open sets
• Algorithmic Randomness of Closed Sets
• Randomness via effective descriptive set theory

Cites work

• A quest for algorithmically random infinite structures
• A quest for algorithmically random infinite structures. II
• Algorithmic Randomness of Closed Sets
• Algorithmic randomness of continuous functions
• Coherent randomness tests and computing the \(K\)-trivial sets
• Computability and Randomness
• Deep _1⁰ classes
• Degrees of difficulty of generalized r.e. separating classes
• Denjoy, Demuth and density
• Effectively closed sets and graphs of computable real functions.
• scientific article; zbMATH DE number 1303200 (Why is no real title available?)
• Lebesgue density and \(\Pi _1^0\) classes
• Martin-Löf randomness and Galton-Watson processes
• Martin-Löf randomness in spaces of closed sets
• Members of Random Closed Sets
• Randomness for non-computable measures
• THE COMPLEXITY OF FINITE OBJECTS AND THE DEVELOPMENT OF THE CONCEPTS OF INFORMATION AND RANDOMNESS BY MEANS OF THE THEORY OF ALGORITHMS
• The definition of random sequences
• The interplay of classes of algorithmically random objects
• Von Mises' definition of random sequences reconsidered
• Π₁⁰ classes with complex elements

Cited in

(6)

• Members of countable \(\Pi ^ 0_ 1\) classes
• choice classes
• Deep _1⁰ classes
• Π₁⁰ classes with complex elements
• A basis theorem for Π₁⁰ classes of positive measure and jump inversion for random reals
• Continuous randomness via transformations of 2-random sequences

This page was built for publication: The random members of a \({\Pi }_{1}^{0}\) class

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