Douglas Cenzer ; Paul Brodhead ; Ferit Toska ; Sebastian Wyman - Algorithmic Randomness and Capacity of Closed Sets

lmcs:1020 - Logical Methods in Computer Science, September 23, 2011, Volume 7, Issue 3 - https://doi.org/10.2168/LMCS-7(3:16)2011
Algorithmic Randomness and Capacity of Closed SetsArticle

Authors: Douglas Cenzer ; Paul Brodhead ; Ferit Toska ; Sebastian Wyman

    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.


    Volume: Volume 7, Issue 3
    Published on: September 23, 2011
    Imported on: December 27, 2010
    Keywords: Computer Science - Logic in Computer Science,Mathematics - Logic,F.4.1
    Funding:
      Source : OpenAIRE Graph
    • Collaboration in Computability; Funder: National Science Foundation; Code: 0554841
    • SM: Logic Year at the University of Florida; Funder: National Science Foundation; Code: 0532644

    Consultation statistics

    This page has been seen 2174 times.
    This article's PDF has been downloaded 273 times.