zbMATH — the first resource for mathematics

Lowness for the class of random sets. (English) Zbl 0954.68080
The original Martin-Löf definition defines a random sequence as a sequence which passes all computable randomness tests. For every non-recursive set (binary sequence) \(A\), we can consider, instead, tests which are computable relative to the oracle \(A\), and thus get a relativized version of randomness. Since by adding an oracle we add new tests, the class \(\text{RAND}^A\) of all resulting random sequences usually decreases: \(\text{RAND}^A\subset \text{RAND}\), and \(\text{RAND}^A\neq \text{RAND}\). The authors prove, however, that there exists an r.e. non-recursive oracle \(A\) for which \(\text{RAND}^A= \text{RAND}\). This proof provides an answer to a longstanding open question by M. van Lambalgen and D. Zambella.

68Q30 Algorithmic information theory (Kolmogorov complexity, etc.)
Full Text: DOI
[1] DOI: 10.1007/BF02757864 · Zbl 0272.28012 · doi:10.1007/BF02757864
[2] DOI: 10.1016/S0019-9958(86)80004-3 · Zbl 0628.03024 · doi:10.1016/S0019-9958(86)80004-3
[3] On sequences with simple initial segments (1990)
[4] Recursively enumerable sets and degrees (1987)
[5] Recursion theory week 1984 1141 pp 245– (1985)
[6] Algorithmic randomness and lowness (1997)
[7] The axiomatization of randomness 55 pp 1143– (1990)
[8] DOI: 10.1016/0168-0072(93)90209-V · Zbl 0788.68068 · doi:10.1016/0168-0072(93)90209-V
[9] DOI: 10.1016/S0019-9958(66)80018-9 · Zbl 0244.62008 · doi:10.1016/S0019-9958(66)80018-9
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.