Premium
Using random sets as oracles
Author(s) -
Hirschfeldt Denis R.,
Nies André,
Stephan Frank
Publication year - 2007
Publication title -
journal of the london mathematical society
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.441
H-Index - 62
eISSN - 1469-7750
pISSN - 0024-6107
DOI - 10.1112/jlms/jdm041
Subject(s) - randomness , set (abstract data type) , base (topology) , mathematics , combinatorics , degree (music) , discrete mathematics , turing , computer science , algorithm , physics , statistics , mathematical analysis , acoustics , programming language
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 Δ 2 0 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.