The classes of algorithmically random reals

Abstract

This work outlines various definitions of Martin-Löf randomness (the standard definition of algorithmic randomness), computable randomness, Schnorr randomness and Kurtz randomness, and describes how these ideas can be extended to an infinite hierarchy of randomness classes that is based on the arithmetic hierarchy. We provide a characterization of Kurtz randomness based on computable machines. Furthermore, we investigate s-randomness, and provide a characterization of the s-randomness classes in terms of prefix-free machines. Whilst standard randomness only requires random numbers to avoid measure zero sets, .s-randomness takes the Hausdorff dimension of a measure zero set into account as well, to create a dense collection of randomness classes.