scientific article; zbMATH DE number 3559552
Let \(\Omega\) be the set of all infinite binary sequences. Let further \(\mathcal D\) be the class of all \(A\subseteq\Omega\) which are unions of Turing degrees and measurable by the universal enumerable (semicomputable) measure [\textit{A. K. Zvonkin} and \textit{L. A. Levin}, Uspehi mat. Nauk 25, Nr. 6(156), 85-127 (1970; Zbl 0222.02027)]. A set is called negligible iff the universal enumerable measure of \(A\) is \(0\). The preorder ``\(A\leq B\leftrightarrow A\smallsetminus B\) negligible on \(\mathcal D\) is introduced and the quotient \(L=_{df}\mathcal D/_\equiv\) is investigated, \((A\equiv B\leftrightarrow A\leq B\wedge B\leq A)\). lt turns out that [\(L,\leq\)] is a Boolean algebra whose operations are induced by set-theoretic union and intersection. Further four elements of \(L\) are known: \(0, 1\), the set a defined by all computable sequences, and the set b defined by all sequences random in the sense of Kolmogorov and Martin-Löf and those sequences Turing-equivalent to them. The following result guarantees the existence of a further element of \(L\): There exist an effective operator \(F\) and a set \(B\subseteq\Omega\) such that \(B\) is included in the domain of \(F\) (and coincides with it except for a set of measure 0), \(\mu(B)>0\), and \(\mu(G(F(B))) =0\) for every effective operator \(G\) (\(\mu\) is the Lebesgue measure). Moreover, \(F(B)\) does not contain computable sequences.
- Non-stochastic infinite and finite sequences
- Computational depth and reducibility
- Turing cones and set theory of the reals
- Randomness for non-computable measures
- Indifferent Sets
- Limit Theorems for the Maximal Random Sums
- On a conjecture of Kůrka. A Turing machine with no periodic configurations
- Computational depth and reducibility
- On Turing dynamical systems and the Atiyah problem
- Large Turing independent sets
- Degrees of randomized computability
- Turing invariant sets and the perfect set property
- Diagonally non-computable functions and fireworks
- Kolmogorov complexity in the USSR (1975--1982): isolation and its end
- On empirical meaning of randomness with respect to parametric families of probability distributions
- On an open question regarding atoms in the Levin-V'yugin degrees
This page was built for publication:
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4132513)