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}}(p)$be the mass problem of infinite bit sequencesy(i.e.,$\{0,1\}$-valued functions) such that for each computable bit sequencex, the bit sequence$ x {\,\leftrightarrow\,} y$has asymptotic lower density at mostp(where$x {\,\leftrightarrow\,} y$has a$1$in positionniff$x(n) = y(n)$). We show that all members of this family of mass problems parameterized by a realpwith$0 p$for each computable setx. We prove that the Medvedev (and hence Muchnik) complexity of the mass problems${\mathcal {B}}(p)$is the same for all$p \in (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.Next, together with Joseph Miller, we obtain a proper hierarchy of the mass problems of type$\text {IOE}$: we show that for any order functiongthere exists a faster growing order function$h $such that$\text {IOE}(h)$is strictly above$\text {IOE}(g)$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}} (p)$is the least size of a setGof bit sequences such that for each bit sequencexthere is a bit sequenceyinGso that$\underline \rho (x {\,\leftrightarrow\,} y)>p$. We prove within ZFC all the coincidences of cardinal characteristics that are the analogs of the results above.