Muchnik degrees and Medvedev degrees of the randomness notions

News
Sep 2018, accepted
11 Mar 2018, submitted to a Journal

Title
Muchnik degrees and Medvedev degrees of the randomness notions

Type
Research paper

Publication
The joint proceedings for ALC2015 and ALC2017 that will be published via World Scientific

Abstract
The main theme of this paper is computational power when a machine is allowed to access random sets.
The computability depends on the randomness notions and we compare them by Muchnik and Medvedev degrees.
The central question is whether, given an random oracle, one can compute a more random set.
The main result is that, for each Turing functional,
there exists a Schnorr random set whose output is not computably random.

download
Muchnikdegrees