Computability in Europe 2006
Logical Approaches to Computational Barriers

Print current page  Print this page

Regular Talk:
Random Closed Sets

Speaker: Douglas Cenzer
Author(s): Paul Brodhead, Douglas Cenzer and Seyyed Dashti
Presentation: paul.pdf
Slot: Tue, 14:30-14:50, Faraday A (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 Valid HTML 4.01! Valid CSS! eXTReMe Tracker hit counters by www.free-counters.net