Logical Approaches to Computational Barriers

Random Closed Sets

Speaker:
| Douglas Cenzer |

Author(s): |
Paul Brodhead, Douglas Cenzer and Seyyed Dashti |

Slot: |
Array, 14:30-14:50, col. 1 |

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 |