Please use this identifier to cite or link to this item:
https://doi.org/10.2178/jsl/1120224726
DC Field | Value | |
---|---|---|
dc.title | Randomness, relativization and turing degrees | |
dc.contributor.author | Nies, A. | |
dc.contributor.author | Stephan, F. | |
dc.contributor.author | Terwijn, S.A. | |
dc.date.accessioned | 2013-07-04T07:40:57Z | |
dc.date.available | 2013-07-04T07:40:57Z | |
dc.date.issued | 2005 | |
dc.identifier.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 | |
dc.identifier.issn | 00224812 | |
dc.identifier.uri | http://scholarbank.nus.edu.sg/handle/10635/39408 | |
dc.description.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. | |
dc.description.uri | http://libproxy1.nus.edu.sg/login?url=http://dx.doi.org/10.2178/jsl/1120224726 | |
dc.source | Scopus | |
dc.type | Article | |
dc.contributor.department | COMPUTER SCIENCE | |
dc.description.doi | 10.2178/jsl/1120224726 | |
dc.description.sourcetitle | Journal of Symbolic Logic | |
dc.description.volume | 70 | |
dc.description.issue | 2 | |
dc.description.page | 515-535 | |
dc.identifier.isiut | 000229451200011 | |
Appears in Collections: | Staff Publications |
Show simple item record
Files in This Item:
There are no files associated with this item.
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.