Algorithmic Randomness and Capacity of Closed Sets

Details Algorithmic Randomness and Capacity of Closed Sets Algorithmic Randomness and Capacity of Closed Sets

2011-06-15

arxiv.org/abs/1106.2993v2

LMCS 7 (3:16) 2011

Computer Science

Logic in Computer Science

Scientific paper

10.2168/LMCS-7(3:16)2011

We investigate the connection between measure, capacity and algorithmic randomness for the space of closed sets. For any computable measure m, a computable capacity T may be defined by letting T(Q) be the measure of the family of closed sets K which have nonempty intersection with Q. We prove an effective version of Choquet's capacity theorem by showing that every computable capacity may be obtained from a computable measure in this way. We establish conditions on the measure m that characterize when the capacity of an m-random closed set equals zero. This includes new results in classical probability theory as well as results for algorithmic randomness. For certain computable measures, we construct effectively closed sets with positive capacity and with Lebesgue measure zero. We show that for computable measures, a real q is upper semi-computable if and only if there is an effectively closed set with capacity q.

Affiliated with

Also associated with

No associations

Rating

Algorithmic Randomness and Capacity of Closed Sets does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Algorithmic Randomness and Capacity of Closed Sets, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Algorithmic Randomness and Capacity of Closed Sets will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-658889