Algorithmic randomness of closed sets
We investigate notions of randomness in the space C[2(N)] of non-empty closed subsets of {0, 1}(N). A probability measure is given and a version of the Martin-Lof test for randomness is defined. Pi(0)(2) random closed sets exist but there are no random Pi(0)(1) closed sets. It is shown that any random closed set is perfect, has measure 0, and has box dimension log(2) (4/3). A 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 T-n = T boolean AND {0, 1}", then for any random closed set [T] where T has no dead ends, K(T-n) >= n - O(l) but for any k, K(T-n) <= 2(n-k) + O(l), where K(sigma) is the prefix-free complexity of sigma epsilon {0, 1}*.
randomness computability pi(0)(1) classes