Computational randomness and lowness (Q2758053)
From MaRDI portal
 | This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use this page instead for the normal view: Computational randomness and lowness |
scientific article; zbMATH DE number 1679326
| Language | Label | Description | Also known as |
|---|---|---|---|
| English | Computational randomness and lowness |
scientific article; zbMATH DE number 1679326 |
Statements
Computational randomness and lowness (English)
0 references
25 July 2002
0 references
Schnorr randomness
0 references
Martin Löf randomness
0 references
low sets
0 references
It is shown that there exist uncountably many sets that are low for the class \(C\) of Schnorr random sets (also called recursively random sets). This is a purely recursion-theoretic characterization of these sets. Lowness of a set \(A\) with respect to some class of sets \(C\) means that \(C\), relative to \(A\), is included in \(C\). This is a useful concept both in recursion theory and structural complexity. This result contrasts with a result of \textit{A. Kucera} and \textit{S. A. Terwijn} [J. Symb. Log. 64, 1396-1402 (1999; Zbl 0954.68080)] on sets which are low for the class of Martin-Löf random sets.
0 references
