Lowness properties and randomness

The set A is low for (Martin-Löf) randomness if each random set is already random relative to A . A is K -trivial if the prefix complexity K of each initial segment of A is minimal, namely ∀ n K ( A ↾ n ) ⩽ K ( n ) + O ( 1 ) . We show that these classes coincide. This answers a question of Ambos-Spi...

Full description

Saved in:
Bibliographic Details
Published in:Advances in mathematics (New York. 1965) 2005-10, Vol.197 (1), p.274-305
Main Author: Nies, André
Format: Article
Language:English
Subjects:
[formula omitted]-trivial
Kolmogorov prefix complexity
Low for random
Randomness
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:The set A is low for (Martin-Löf) randomness if each random set is already random relative to A . A is K -trivial if the prefix complexity K of each initial segment of A is minimal, namely ∀ n K ( A ↾ n ) ⩽ K ( n ) + O ( 1 ) . We show that these classes coincide. This answers a question of Ambos-Spies and Kučera in: P. Cholak, S. Lempp, M. Lerman, R. Shore, (Eds.), Computability Theory and Its Applications: Current Trends and Open Problems, American Mathematical Society, Providence, RI, 2000: each low for Martin-Löf random set is Δ 2 0 . Our class induces a natural intermediate Σ 3 0 ideal in the r.e. Turing degrees, which generates the whole class under downward closure. Answering a further question in P. Cholak, S. Lempp, M. Lerman, R. Shore, (Eds.), Computability Theory and Its Applications: Current Trends and Open Problems, American Mathematical Society, Providence, RI, 2000, we prove that each low for computably random set is computable.
ISSN:0001-8708
1090-2082
DOI:10.1016/j.aim.2004.10.006