Please use this identifier to cite or link to this item:
Title: Randomness, relativization and turing degrees
Authors: Nies, A.
Stephan, F. 
Terwijn, S.A.
Issue Date: 2005
Citation: Nies, A., Stephan, F., Terwijn, S.A. (2005). Randomness, relativization and turing degrees. Journal of Symbolic Logic 70 (2) : 515-535. ScholarBank@NUS Repository.
Abstract: We compare various notions of algorithmic randomness. First we consider relativized randomness. A set is n-random if it is Martin-Löf random relative to Øn-1. We show that a set is 2-random if and only if there is a constant c such that infinitely many initial segments x of the set are c-incompressible: C(x) ≥ |x| - c. The 'only if direction was obtained independently by Joseph Miller. This characterization can be extended to the case of time-bounded C-complexity. Next we prove some results on lowness. Among other things, we characterize the 2-random sets as those 1-random sets that are low for Chaitin's Ω. Also, 2-random sets form minimal pairs with 2-generic sets. The r.e. low for Ω sets coincide with the re. K-trivial ones. Finally we show that the notions of Martin-Löf randomness, recursive randomness, and Schnorr randomness can be separated in every high degree while the same notions coincide in every non-high degree. We make some remarks about hyperimmune-free and PA-complete degrees. © 2005, Association for Symbolic Logic.
Source Title: Journal of Symbolic Logic
ISSN: 00224812
DOI: 10.2178/jsl/1120224726
Appears in Collections:Staff Publications

Show full item record
Files in This Item:
There are no files associated with this item.


checked on Jun 4, 2020


checked on May 26, 2020

Page view(s)

checked on Jun 1, 2020

Google ScholarTM



Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.