Please use this identifier to cite or link to this item: https://doi.org/10.2178/jsl/1120224726
Title: Randomness, relativization and turing degrees
Authors: Nies, A.
Stephan, F. 
Terwijn, S.A.
Issue Date: 2005
Source: Nies, A.,Stephan, F.,Terwijn, S.A. (2005). Randomness, relativization and turing degrees. Journal of Symbolic Logic 70 (2) : 515-535. ScholarBank@NUS Repository. https://doi.org/10.2178/jsl/1120224726
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
URI: http://scholarbank.nus.edu.sg/handle/10635/39408
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.

SCOPUSTM   
Citations

71
checked on Dec 13, 2017

WEB OF SCIENCETM
Citations

67
checked on Nov 1, 2017

Page view(s)

67
checked on Dec 9, 2017

Google ScholarTM

Check

Altmetric


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