Algorithmic Randomness of Closed Sets
George Barmpalias, Paul Brodhead, Douglas Cenzer, S. Ghazaleh Dashti, Richard Weber · Journal of Logic and Computation · 2007
We investigate notions of randomness in the space C[2 N] of nonempty closed subsets of {0, 1} N. A probability measure is given and a version of the Martin-Löf test for randomness is defined. Π 0 2 random closed sets exist but there are no random Π 0 1 closed sets. It is shown that any random 4 closed set is perfect, has measure 0, and has box dimension log2. A 3 random closed set has no n-c.e. elements. A closed subset of 2 N may be defined as the set of infinite paths through a tree and so the problem of compressibility of trees is explored. If Tn = T ∩ {0, 1} n, then for any random closed set [T] where T has no dead ends, K(Tn) ≥ n − O(1) but for any k, K(Tn) ≤ 2 n−k + O(1), where K(σ) is the prefix-free complexity of σ ∈ {0, 1} ∗. 1