Original Articles |
Algorithmic Randomness of Closed Sets *
School of Mathematics, University of Leeds, Leeds LS2 9JT, UK. E-mail: georgeb{at}math.leeds.ac.uk
Department of Mathematics, University of Florida, P.O. Box 118105, Gainesville, Florida 32611, USA. E-mail: brodhead{at}math.ufl.edu; cenzer{at}math.ufl.edu; mashadeo{at}math.ufl.edu
Department of Mathematics, Dartmouth College, Hanover, NH 03755-3551, UK. E-mail: rebecca.weber{at}dartmouth.edu
Received 20 October 2006.
 |
Abstract |
|---|
We investigate notions of randomness in the space 
of non-empty closed subsets of 
. A probability measure is given and a version of the Martin-Löf test for randomness is defined. 
random closed sets exist but there are no random 
closed sets. It is shown that any random closed set is perfect, has measure 0, and has box dimension 
. A random closed set has no n-c.e. elements. A closed subset of 
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, 
but for any k, K(Tn) 
2n – k + O(1), where K(
) is the prefix-free complexity of 
{0,1}*.
Keywords: Computability; randomness; 
01 classes
*A preliminary version of this article appeared in the Proceedings of CIE 2006 [2].
CiteULike 
Connotea 
Del.icio.us What's this?
This article has been cited by other articles:
|
|
 |
|
  G. Barmpalias, D. Cenzer, J. B. Remmel, and R. Weber K-Triviality of Closed Sets and Continuous Functions J Logic Computation, August 14, 2008; (2008) exn021v1. [Abstract] [PDF]
|
|