We found a match
Your institution may have access to this item. Find your institution then sign in to continue.
- Title
The Random Members of a Π10 Class.
- Authors
Cenzer, Douglas; Porter, Christopher P.
- Abstract
We examine several notions of randomness for elements in a given Π10<inline-graphic></inline-graphic> class P<inline-graphic></inline-graphic>. Such an effectively closed subset P<inline-graphic></inline-graphic> of 2ωmay be viewed as the set of infinite paths through the tree TP<inline-graphic></inline-graphic> of extendible nodes of P<inline-graphic></inline-graphic>, i.e., those finite strings that extend to a member of P<inline-graphic></inline-graphic>, so one approach to defining a random member of P<inline-graphic></inline-graphic> is to randomly produce a path through TP<inline-graphic></inline-graphic> using a sufficiently random oracle for advice. In addition, this notion of randomness for elements of P<inline-graphic></inline-graphic> may be induced by a map from 2ωonto P<inline-graphic></inline-graphic> that is computable relative to TP<inline-graphic></inline-graphic>, and the notion even has a characterization in term of Kolmogorov complexity. Another approach is to define a relative measure on P<inline-graphic></inline-graphic> by conditionalizing the Lebesgue measure on P<inline-graphic></inline-graphic>, which becomes interesting if P<inline-graphic></inline-graphic> has Lebesgue measure 0. Lastly, one can alternatively define a notion of incompressibility for members of P<inline-graphic></inline-graphic> in terms of the amount of branching at levels of TP<inline-graphic></inline-graphic>. We explore some notions of homogeneity for Π10<inline-graphic></inline-graphic> classes, inspired by work of van Lambalgen. A key finding is that in a specific class of sufficiently homogeneous Π10<inline-graphic></inline-graphic> classes P<inline-graphic></inline-graphic>, all of these approaches coincide. We conclude with a discussion of random members of Π10<inline-graphic></inline-graphic> classes of positive measure.
- Subjects
MATHEMATICAL models; ALGORITHMIC randomness; COMPUTABLE functions; KOLMOGOROV complexity; EQUATIONS
- Publication
Theory of Computing Systems, 2018, Vol 62, Issue 7, p1637
- ISSN
1432-4350
- Publication type
Article
- DOI
10.1007/s00224-017-9824-3