Algorithmic randomness and capacity of closed sets

DOI10.2168/LMCS-7(3:16)2011MaRDI QIDQ3224682zbMATH OpenOpenAlexFDO

Authors Paul Brodhead, Douglas Cenzer, Ferit Toska, Sebastian Wyman

Publication date 2 April 2012

Published in Logical Methods in Computer Science (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1106.2993

zbMATH Keywords

algorithmic randomnesscomputable analysiseffective capacityeffectively closed sets

Mathematics Subject Classification ID

Algorithmic randomness and dimension (03D32) Theory of numerations, effectively presented structures (03D45) Computation over the reals, computable analysis (03D78)

Abstract: 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.

Recommendations

• scientific article; zbMATH DE number 7311154
• The interplay of classes of algorithmically random objects
• Algorithmically Random Functions and Effective Capacities
• Logical Approaches to Computational Barriers
• Martin-Löf randomness in spaces of closed sets

Cited in

(7)

• Effective randomness of unions and intersections
• Algorithmically Random Functions and Effective Capacities
• The interplay of classes of algorithmically random objects
• Effectively approximating measurable sets by open sets
• The Intersection of Algorithmically Random Closed Sets and Effective Dimension
• scientific article; zbMATH DE number 7311154 (Why is no real title available?)
• Effectively closed sets of measures and randomness

This page was built for publication: Algorithmic randomness and capacity of closed sets

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3224682)