Please use this identifier to cite or link to this item:
Title: Using random sets as oracles
Authors: Hirschfeldt, D.R.
Nies, A.
Stephan, F. 
Issue Date: Jun-2007
Source: 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.
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
ISSN: 00246107
DOI: jlms/jdm041
Appears in Collections:Staff Publications

Show full item record
Files in This Item:
There are no files associated with this item.


checked on Feb 20, 2018

Page view(s)

checked on Mar 12, 2018

Google ScholarTM



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