On Languages Reducible to Algorithmically Random Languages
Ronald V. Book · SIAM Journal on Computing · 1994
In this paper languages “bounded reducible” to algorithmically random languages are studied; these are the languages whose characteristic sequences are algorithmically random (as defined by Martin-Löf [Inform. and Control, 9(), pp. 602–619]); here RAND denotes the class of algorithmically random languages. The reducibilities $ \leqslant ^\mathcal{R} $ are very general but are defined so that if $A \in \mathcal{R}(B)$, then there is a machine M with the properties that $L(M,B) = A$ and every computation of M relative to any oracle halts. Book, Lutz, and Wagner [Math. Systems Theory, 27 (1994), pp. 201–209] studied ALMOST-$\mathcal{R}$, defined to be { $A|$ for almost every B, $A \leqslant _\mathcal{R} B$ }. They showed that ALMOST-$\mathcal{R} = \mathcal{R}({\text{RAND}}) \cap {\text{REC}}$, where ${\text{REC}}$ denotes the class of recursive languages, so that ALMOST-$\mathcal {R}$ is the “recursive part” of $\mathcal{R}({\text{Rand}})$. In this paper this characterization is strengthened by showing that for every$B \in {\text{RAND}}$, ALMOST-$\mathcal{R} = \mathcal{R}({B{RAND}}) \cap {\text{REC}}$. A pair $(A,B)$ of languages is an independent pair of algorithmically random languages if $A \oplus B \in {\text{RAND}}$. In this paper it is shown that for every $\mathcal {R}$ and for every independent pair $(A,B)$, ALMOST-$\mathcal {R} = \mathcal{R}(A) \cap \mathcal{R}(B)$.