Aspects of Algorithmically Random Objects

Abstract

For a class of objects C with some effective encoding F : k^ω → C (where k^ω is the space of infinite k-ary sequences), an object c ∈ C may be called algorithmically random if c has some F-code X ∈ k^ω that is µ-Martin-Lof random with respect to some computable probability ¨ measure µ. The structural properties of classes of random objects, such as random closed sets, have been well-studied in recent decades. Additionally, connections to properties of their members (in the case of closed sets) and of their outputs (in the case of continuous functions) have been identified. Such a random object c is structurally random, and thus satisfies properties one would expect the “typical” object in its class C to satisfy.

We show that for a computable Bernoulli measure µ on the space 3^ω, every µ-random continuous function on 2^ω (originally defined by Barmpalias et al.) extracts bits equal to the probability of a continuous function outputting a single bit. We also show that if a Turing functional F outputs bits quickly enough, then F must preserve effective Hausdorff dimension up to a multiplicative constant; this effectivizes a classical result concerning Holder-continuous ¨ functions.

We also show that the family of separating classes, a subfamily of closed sets of 2^ω, contains no random closed sets, but may be given an encoding coherent with the original encoding for closed sets. For this encoding, we define a notion of random separating class and prove results about members of such closed sets that are stronger than the ones originally proved for random closed sets. For example, we show that each random separating class has a µ-Martin-Lof random member for countably many computable Bernoulli measures µ.

We also define a notion of 1-genericity for closed sets and study properties of 1-generic closed sets that are analogous to those of random closed sets. We compare results for 1-generic closed sets and random closed sets. In particular, random closed sets have nonzero box dimension, but 1-generic closed sets have lower box dimension 0 and upper box dimension 1.