Please use this identifier to cite or link to this item:
|Title:||Randomness, relativization and turing degrees||Authors:||Nies, 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. 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.
checked on Jun 4, 2020
WEB OF SCIENCETM
checked on May 26, 2020
checked on Jun 1, 2020
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.