Please use this identifier to cite or link to this item:
https://doi.org/10.1112/jlms/jdm041
Title: | Using random sets as oracles | Authors: | Hirschfeldt, D.R. Nies, A. Stephan, F. |
Issue Date: | Jun-2007 | Citation: | Hirschfeldt, D.R., Nies, A., Stephan, F. (2007-06). Using random sets as oracles. Journal of the London Mathematical Society 75 (3) : 610-622. ScholarBank@NUS Repository. https://doi.org/10.1112/jlms/jdm041 | Abstract: | Let R be a notion of algorithmic randomness for individual subsets of . A set B is a base for R randomness if there is a Z ≥T B such that Z is R random relative to B. We show that the bases for 1-randomness are exactly the K-trivial sets, and discuss several consequences of this result. On the other hand, the bases for computable randomness include every Δ20 set that is not diagonally noncomputable, but no set of PA-degree. As a consequence, an n-c.e. set is a base for computable randomness if and only if it is Turing incomplete. © 2007 London Mathematical Society. | Source Title: | Journal of the London Mathematical Society | URI: | http://scholarbank.nus.edu.sg/handle/10635/104445 | ISSN: | 00246107 | DOI: | 10.1112/jlms/jdm041 |
Appears in Collections: | Staff Publications |
Show full 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.