On relative randomness (Q688792): Difference between revisions

In algorithmic complexity theory, an element is declared random iff it does not belong to any constructive set of measure 0. In particular, ``relative'' randomness is defined as follows. Assume that an infinite binary sequence \(\alpha\) is given. By an \(\alpha\)-algorithm, we mean an algorithm that uses \(\alpha\) as an oracle. An interval \(I\) on a set of all binary sequences is a set of all sequences \(\beta\) that start with a given finite sequence \(\beta_ 1 \dots \beta_ p\). The measure \(\mu\) is defined as follows: for each interval \(I\) determined by a sequence \(\beta_ 1 \dots \beta_ p\), the measure \(\mu(I)\) of this intervals is \(2^{-p}\). We say that a set \(S\) of infinite binary sequences has \(\alpha\)-constructive measure 0, if there exists an \(\alpha\)-algorithm that for every \(n\), generates a sequence \(I_{mn}\) of intervals such that \(S \subseteq I_ n=\cup_ mI_{mn}\), and \(\mu(I_ n) \leq 2^{- n}\). A sequence \(\beta\) is called \(\alpha\)-random (or, to be more precise, \(\alpha-1\)-random) if it does not belong to any set of \(\alpha\)- constructive measure 0 (or, equivalently, for which the one-element set \(\{\beta\}\) is not of \(\alpha\)-constructive measure 0). Crudely speaking, if \(\beta\) is \(\alpha\)-random, this means in particular, that knowing \(\alpha\) will not help in computing \(\beta\). A natural question is: does this also mean that knowing \(\beta\) does not help in computing \(\alpha\)? This question was raised by M. van Lambalgen and D. Zambella. The author provides the following answer: there exist \(\alpha\) and \(\beta\) such that \(\beta\) is \(\alpha\)-random while \(\alpha\) is recursive in \(\beta\). Other results on relative randomness are also proved.