Algorithmic Randomness and Capacity of Closed Sets
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 eff...
| Main Authors: | , , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Logical Methods in Computer Science e.V.
2011-09-01
|
| Series: | Logical Methods in Computer Science |
| Subjects: | |
| Online Access: | https://lmcs.episciences.org/1020/pdf |
| _version_ | 1827322942730534912 |
|---|---|
| author | Douglas Cenzer Paul Brodhead Ferit Toska Sebastian Wyman |
| author_facet | Douglas Cenzer Paul Brodhead Ferit Toska Sebastian Wyman |
| author_sort | Douglas Cenzer |
| collection | DOAJ |
| description | 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. |
| first_indexed | 2024-04-25T01:36:49Z |
| format | Article |
| id | doaj.art-9f67e37928e34cbe89677a5f6081b8ec |
| institution | Directory Open Access Journal |
| issn | 1860-5974 |
| language | English |
| last_indexed | 2024-04-25T01:36:49Z |
| publishDate | 2011-09-01 |
| publisher | Logical Methods in Computer Science e.V. |
| record_format | Article |
| series | Logical Methods in Computer Science |
| spelling | doaj.art-9f67e37928e34cbe89677a5f6081b8ec2024-03-08T09:17:23ZengLogical Methods in Computer Science e.V.Logical Methods in Computer Science1860-59742011-09-01Volume 7, Issue 310.2168/LMCS-7(3:16)20111020Algorithmic Randomness and Capacity of Closed SetsDouglas CenzerPaul BrodheadFerit ToskaSebastian WymanWe 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.https://lmcs.episciences.org/1020/pdfcomputer science - logic in computer sciencemathematics - logicf.4.1 |
| spellingShingle | Douglas Cenzer Paul Brodhead Ferit Toska Sebastian Wyman Algorithmic Randomness and Capacity of Closed Sets Logical Methods in Computer Science computer science - logic in computer science mathematics - logic f.4.1 |
| title | Algorithmic Randomness and Capacity of Closed Sets |
| title_full | Algorithmic Randomness and Capacity of Closed Sets |
| title_fullStr | Algorithmic Randomness and Capacity of Closed Sets |
| title_full_unstemmed | Algorithmic Randomness and Capacity of Closed Sets |
| title_short | Algorithmic Randomness and Capacity of Closed Sets |
| title_sort | algorithmic randomness and capacity of closed sets |
| topic | computer science - logic in computer science mathematics - logic f.4.1 |
| url | https://lmcs.episciences.org/1020/pdf |
| work_keys_str_mv | AT douglascenzer algorithmicrandomnessandcapacityofclosedsets AT paulbrodhead algorithmicrandomnessandcapacityofclosedsets AT ferittoska algorithmicrandomnessandcapacityofclosedsets AT sebastianwyman algorithmicrandomnessandcapacityofclosedsets |