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.

SCOPUSTM   
Citations

47
checked on Jun 23, 2018

WEB OF SCIENCETM
Citations

42
checked on May 30, 2018

Page view(s)

25
checked on Apr 20, 2018

Google ScholarTM

Check

Altmetric


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