Algorithmic randomness and capacity of closed sets

DOI10.2168/LMCS-7(3:16)2011zbMATH Open1237.03026arXiv1106.2993OpenAlexW1998556335MaRDI QIDQ3224682FDOQ3224682

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)

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.

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

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

zbMATH Keywords

computable analysisalgorithmic randomnesseffective capacityeffectively closed sets

Mathematics Subject Classification ID

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

Cited In (7)

• Effectively closed sets of measures and randomness
• Effectively approximating measurable sets by open sets
• Algorithmically Random Functions and Effective Capacities
• Effective randomness of unions and intersections
• Title not available (Why is that?)
• The Intersection of Algorithmically Random Closed Sets and Effective Dimension
• The interplay of classes of algorithmically random objects

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)