Muchnik degrees and cardinal characteristics

DOI10.1017/JSL.2020.1MaRDI QIDQ5159485zbMATH OpenOpenAlexFDO

Authors Benoit Monin, André Nies

Publication date 27 October 2021

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

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

zbMATH Keywords

cardinal characteristicsmass problemMedvedev reducibilityMuchnik reducibilityTuring functional \(\Gamma\)

Mathematics Subject Classification ID

Other Turing degree structures (03D28) Other degrees and reducibilities in computability and recursion theory (03D30) Applications of computability and recursion theory (03D80) Cardinal characteristics of the continuum (03E17)

Abstract: For $pin[0,1]$ let $mathcalD(p)$ be the mass problem of infinite bit sequences~$y$ (i.e., $0,1$-valued functions) such that for each computable bit sequence $x$, the bit sequence $xleftrightarrowy$ has asymptotic lower density at most $p$ (where $xleftrightarrowy$ has a $1$ in position $n$ iff $x(n)=y(n)$). We show that all members of this family of mass problems parameterized by a real $p$ with $0<p<1/2$ have the same complexity in the sense of Muchnik reducibility. We prove this by showing Muchnik equivalence of the problems $mathcalD(p)$ with the mass problem $mathrmIOE(2^{2^n})$. As a dual of the problem $mathcalD(p)$, define $mathcalB(p)$, for $0lep<1/2$, to be the set of bit sequences $y$ such that $underlineho(xleftrightarrowy)>p$ for each computable set~$x$. We prove that the Medvedev (and hence Muchnik) complexity of the mass problems $mathcalB(p)$ is the same for all $pin(0,1/2)$, by showing that they are Medvedev equivalent to the mass problem of functions bounded by $2^{2^n}$ that are almost everywhere different from each computable function. Together with Joseph Miller, we obtain a proper hierarchy of the mass problems of type $mathrmIOE$: We study cardinal characteristics in the sense of set theory that are analogous to the highness properties above.

Recommendations

• Mass Problems and Randomness
• The strength of the Besicovitch-Davies theorem
• Mass problems and almost everywhere domination
• Theory and Applications of Models of Computation
• An analogy between cardinal characteristics and highness properties of oracles

Cites work

• A unifying approach to the Gamma question
• An analogy between cardinal characteristics and highness properties of oracles
• An answer to the gamma question
• Asymptotic density and the coarse computability bound
• Asymptotic density, computable traceability, and 1-randomness
• Cardinal invariants, non-lowness classes, and Weihrauch reducibility
• Combinatorial Cardinal Characteristics of the Continuum
• Computability and complexity. Essays dedicated to Rodney G. Downey on the occasion of his 60th birthday
• Computability and randomness
• Error-correcting codes for list decoding
• Forcing with bushy trees
• scientific article; zbMATH DE number 787541 (Why is no real title available?)
• Many different covering numbers of Yorioka's ideals
• Relativized Schnorr tests with universal behavior
• The gamma question for many-one degrees

Cited in

(9)

• Computable analogs of cardinal characteristics: prediction and rearrangement
• Highness properties close to PA completeness
• An analogy between cardinal characteristics and highness properties of oracles
• MASS PROBLEMS AND HYPERARITHMETICITY
• The strength of the Besicovitch-Davies theorem
• Intervals of the Muchnik lattice
• A unifying approach to the Gamma question
• An answer to the gamma question
• Martin-Löf random quantum states

This page was built for publication: Muchnik degrees and cardinal characteristics

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