Degrees of randomized computability

DOI10.1017/BSL.2021.46MaRDI QIDQ5067871zbMATH OpenOpenAlexFDO

Authors Rupert Hölzl, Christopher P. Porter

Publication date 4 April 2022

Published in The Bulletin of Symbolic Logic (Search for Journal in Brave)

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

zbMATH Keywords

algebracomputabilitydiagonally noncomputableDNCLevinLV-degreenegligibilityprobabilistic algorithmrandomnesssemimeasureV'yugin

Mathematics Subject Classification ID

Other Turing degree structures (03D28) Other degrees and reducibilities in computability and recursion theory (03D30) Algorithmic randomness and dimension (03D32) Algorithmic information theory (Kolmogorov complexity, etc.) (68Q30)

Abstract: In this survey we discuss work of Levin and V'yugin on collections of sequences that are non-negligible in the sense that they can be computed by a probabilistic algorithm with positive probability. More precisely, Levin and V'yugin introduced an ordering on collections of sequences that are closed under Turing equivalence. Roughly speaking, given two such collections $mathcalA$ and $mathcalB$, $mathcalA$ is below $mathcalB$ in this ordering if $mathcalAsetminusmathcalB$ is negligible. The degree structure associated with this ordering, the Levin-V'yugin degrees (or LV-degrees), can be shown to be a Boolean algebra, and in fact a measure algebra. We demonstrate the interactions of this work with recent results in computability theory and algorithmic randomness: First, we recall the definition of the Levin-V'yugin algebra and identify connections between its properties and classical properties from computability theory. In particular, we apply results on the interactions between notions of randomness and Turing reducibility to establish new facts about specific LV-degrees, such as the LV-degree of the collection of 1-generic sequences, that of the collection of sequences of hyperimmune degree, and those collections corresponding to various notions of effective randomness. Next, we provide a detailed explanation of a complex technique developed by V'yugin that allows the construction of semi-measures into which computability-theoretic properties can be encoded. We provide two examples of the use of this technique by explicating a result of V'yugin's about the LV-degree of the collection of Martin-L"of random sequences and extending the result to the LV-degree of the collection of sequences of DNC degree.

Recommendations

• scientific article; zbMATH DE number 1531917
• Randomness, lowness and degrees
• Randomness for non-computable measures
• Randomness and reducibility
• scientific article; zbMATH DE number 1834658

Cites work

• A formal theory of inductive inference. Part I
• A formal theory of inductive inference. Part II
• A Theory of Program Size Formally Identical to Information Theory
• Algebra of invariant properties of binary sequences
• Algorithmic randomness and complexity.
• Classical recursion theory. The theory of functions and sets of natural numbers
• Computability and randomness
• Cone avoidance and randomness preservation
• Degrees of Unsolvability. (AM-55)
• Diagonally non-computable functions and fireworks
• Difference randomness
• scientific article; zbMATH DE number 4008384 (Why is no real title available?)
• scientific article; zbMATH DE number 4068853 (Why is no real title available?)
• scientific article; zbMATH DE number 3489017 (Why is no real title available?)
• scientific article; zbMATH DE number 3559552 (Why is no real title available?)
• scientific article; zbMATH DE number 3637728 (Why is no real title available?)
• scientific article; zbMATH DE number 5064956 (Why is no real title available?)
• Lattices and ordered algebraic structures
• Notions of weak genericity
• On calibration error of randomized forecasting algorithms
• On empirical meaning of randomness with respect to parametric families of probability distributions
• On initial segment complexity and degrees of randomness
• On Sequences with Non-learnable Subsequences
• Probabilistic constructions of computable objects and a computable version of Lovász local lemma
• Propagation of partial randomness
• Randomness and semimeasures
• Randomness conservation inequalities; information and independence in mathematical theories
• Randomness, relativization and Turing degrees
• Retraceable Sets
• Separations of non-monotonic randomness notions
• THE COMPLEXITY OF FINITE OBJECTS AND THE DEVELOPMENT OF THE CONCEPTS OF INFORMATION AND RANDOMNESS BY MEANS OF THE THEORY OF ALGORITHMS
• The typical Turing degree
• Turing computability. Theory and applications

Cited in

(7)

• Randomness for non-computable measures
• Random strings and truth-table degrees of Turing complete c.e. sets
• Mass Problems and Randomness
• scientific article; zbMATH DE number 3559552 (Why is no real title available?)
• Kolmogorov complexity in the USSR (1975--1982): isolation and its end
• Vladimir V'yugin: short biography and some research contributions
• On an open question regarding atoms in the Levin-V'yugin degrees

This page was built for publication: Degrees of randomized computability

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