Using random sets as oracles | Zendy

Hirschfeldt Denis R. | Zendy; Nies André | Zendy; Stephan Frank | Zendy

AI Assistant Blog Pricing

Home ZAIA Blog

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.

This content is not available in your region!

Continue researching here.

Having issues? You can contact us here

Accelerating Research