Intermediate intrinsic density and randomness

Article type: Research Article

Authors: Miller, Justin^{; *}

Affiliations: Department of Mathematics, University of Notre Dame, 255 Hurley Bldg Notre Dame, IN 46556, USA. jmille74@nd.edu

Correspondence: [*] Corresponding author. jmille74@nd.edu.

Abstract: Given any 1-random set X and any r in (0,1), we construct a set of intrinsic density r which is computable from both r and X. For almost all r, this set will be the first known example of an intrinsic density r set which cannot compute any r-Bernoulli random set. To achieve this, we shall formalize the into and within noncomputable coding methods which work well with intrinsic density.

Keywords: Intrinsic density, randomness, computability

DOI: 10.3233/COM-210309

Journal: Computability, vol. 10, no. 4, pp. 327-341, 2021