On relative randomness

Automata and formal grammars in connection with logical questions (03D05) Constructive and recursive analysis (03F60) Other constructive mathematics (03F65) Algorithmic information theory (Kolmogorov complexity, etc.) (68Q30)

Review text

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.

Recommendations

Cites work

Cited in

(34)

This page was built for publication: On relative randomness

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