LAUSR.org creates dashboard-style pages of related content for over 1.5 million academic articles. Sign Up to like articles & get recommendations!

The Random Members of a Π10${\Pi }_{1}^{0}$ Class

Photo from wikipedia

We examine several notions of randomness for elements in a given Π10${\Pi }_{1}^{0}$ class P$\mathcal {P}$. Such an effectively closed subset P$\mathcal {P}$ of 2ωmay be viewed as the set… Click to show full abstract

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

Keywords: class; measure; members class; random members; notion

Journal Title: Theory of Computing Systems
Year Published: 2017

Link to full text (if available)


Share on Social Media:                               Sign Up to like & get
recommendations!

Related content

More Information              News              Social Media              Video              Recommended



                Click one of the above tabs to view related content.