Computability in Europe 2006
Logical Approaches to Computational Barriers


Regular Talk:
Random Closed Sets


Speaker: Douglas Cenzer
Author(s): Paul Brodhead, Douglas Cenzer and Seyyed Dashti
Slot: Array, 14:30-14:50, col. 1

Abstract

We investigate notions of randomness in the space of closed subsets of the
Cantor space. A probability measure is given and a version of Martin-Lof Tests
for randomness is defined. It is shown that a random closed set is perfect and
has no computable 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. This leads to some results on a Chaitin-style notion of randomness
for closed sets. 


websites: Arnold Beckmann 2006-05-08