Abstract

A mass problem is a set of functions $\omega \to \omega $. For mass problems ${\mathcal {C}}, {\mathcal {D}}$, one says that ${\mathcal {C}}$ is Muchnik reducible to ${\mathcal {D}}$ if each function in ${\mathcal {C}}$ is computed by a function in ${\mathcal {D}}$. In this paper we study some highness properties of Turing oracles, which we view as mass problems. We compare them with respect to Muchnik reducibility and its uniform strengthening, Medvedev reducibility.For $p \in [0,1]$ let ${\mathcal {D}}$ be the mass problem of infinite bit sequences y such that for each computable bit sequence x, the bit sequence $ x {\,\leftrightarrow\,} y$ has asymptotic lower density at most p = y$ ). We show that all members of this family of mass problems parameterized by a real p with $0 p$ for each computable set x. We prove that the Medvedev complexity of the mass problems ${\mathcal {B}}$ is the same for all $p \in $, 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.Next, together with Joseph Miller, we obtain a proper hierarchy of the mass problems of type $\text {IOE}$ : we show that for any order function g there exists a faster growing order function $h $ such that $\text {IOE}$ is strictly above $\text {IOE}$ in the sense of Muchnik reducibility.We study cardinal characteristics in the sense of set theory that are analogous to the highness properties above. For instance, ${\mathfrak {d}} $ is the least size of a set G of bit sequences such that for each bit sequence x there is a bit sequence y in G so that $\underline \rho >p$. We prove within ZFC all the coincidences of cardinal characteristics that are the analogs of the results above.