The Intersection of Algorithmically Random Closed Sets and Effective Dimension
Article No.: 24, Pages 1 - 19
Abstract
In this article, we study several aspects of the intersections of algorithmically random closed sets. First, we answer a question of Cenzer and Weber, showing that the operation of intersecting relatively random closed sets (random with respect to certain underlying measures induced by Bernoulli measures on the space of codes of closed sets), which preserves randomness, can be inverted: a random closed set of the appropriate type can be obtained as the intersection of two relatively random closed sets. We then extend the Cenzer/Weber analysis to the intersection of multiple random closed sets, identifying the Bernoulli measures with respect to which the intersection of relatively random closed sets can be non-empty. We lastly apply our analysis to provide a characterization of the effective Hausdorff dimension of sequences in terms of the degree of intersectability of random closed sets that contain them.
References
[1]
Logan M. Axon. 2015. Martin-Löf randomness in spaces of closed sets. The Journal of Symbolic Logic 80, 2 (2015), 359–383.
[2]
Logan M. Axon. 2018. Martin-Löf random generalized Poisson processes. Annals of Pure and Applied Logic 169, 4 (2018), 261–276.
[3]
George Barmpalias, Katie Brodhead, Douglas Cenzer, Seyyed Dashti, and Rebecca Weber. 2007. Algorithmic randomness of closed sets. J. Logic Comput. 17, 6 (2007), 1041–1062.
[4]
Laurent Bienvenu, Mathieu Hoyrup, and Alexander Shen. 2017. Layerwise computability and image randomness. Theory of Computing Systems 61, 4 (2017), 1353–1375.
[5]
Katie Brodhead, Douglas Cenzer, Ferit Toska, and Sebastian Wyman. 2011. Algorithmic randomness and capacity of closed sets. Log. Methods Comput. Sci. 7, 3:16 (2011), 1–16.
[6]
Douglas Cenzer and Rebecca Weber. 2013. Effective randomness of unions and intersections. Theory Comput. Syst. 52, 1 (2013), 48–64.
[7]
Quinn Culver and Christopher P. Porter. 2016. The interplay of classes of algorithmically random objects. Journal of Logic and Analysis 7 (2016), 1–25.
[8]
David Diamondstone and Bjørn Kjos-Hanssen. 2012. Martin-Löf randomness and Galton-Watson processes. Ann. Pure Appl. Logic 163, 5 (2012), 519–529. APALD7
[9]
Rodney Downey and Denis Hirschfeldt. 2010. Algorithmic randomness and complexity. Springer, New York.
[10]
Johanna N. Y. Franklin and Christopher P. Porter. 2020. Key developments in algorithmic randomness. In Algorithmic Randomness: Progress and Prospects, Johanna N. Y. Franklin and Christopher P. Porter (Eds.). Lecture Notes in Logic, Vol. 50. Cambridge University Press, Cambridge, UK.
[11]
John M. Hitchcock. 2005. Correspondence principles for effective dimensions. Theory of Computing Systems 38, 5 (2005), 559–571.
[12]
Mathieu Hoyrup and Cristóbal Rojas. 2009a. An application of Martin-Löf randomness to effective probability theory. In Conference on Computability in Europe. Springer, Heidelberg, Germany, 260–269.
[13]
Mathieu Hoyrup and Cristóbal Rojas. 2009b. Applications of effective probability theory to Martin-Löf randomness. In International Colloquium on Automata, Languages, and Programming. Springer, Heidelberg, Germany, 549–561.
[14]
Ming Li and Paul Vitányi. 2008. An Introduction to Kolmogorov Complexity and Its Applications (4th ed.). Springer, Cham, Switzerland. 792 pages.
[15]
Jack H. Lutz. 2003. The dimension of individual strings and sequences. Information and Computation 187, 1 (2003), 49–79.
[16]
Jack H. Lutz and Neil Lutz. 2018. Algorithmic information, plane Kakeya sets, and conditional dimension. ACM Transactions on Computation Theory 10, 2 (2018), 1–22.
[17]
Elvira Mayordomo. 2002. A Kolmogorov complexity characterization of constructive Hausdorff dimension. Inform. Process. Lett. 84, 1 (2002), 1–3. http://www.sciencedirect.com/science/article/pii/S0020019002003435.
[18]
André Nies. 2009. Computability and randomness, Vol. 51. Oxford University Press, New York, NY.
[19]
Alexander Shen. 1986. One more definition of random sequence with respect to computable measure. In First World Congress of the Bernoulli Society on Math. Statistics and Probability Theory, Tashkent. VNU Science Press, Utrecht, The Netherlands, 71.
[20]
Alexander Shen, Vladimir A. Uspensky, and Nikolay Vereshchagin. 2017. Kolmogorov Complexity and Algorithmic Randomness, Vol. 220. American Mathematical Soc., Providence, Rhode Island.
[21]
Robert I. Soare. 2016. Turing computability. In Theory and Applications of Computability. Springer, Heidelberg, Germany.
[22]
Michiel Van Lambalgen. 1990. The axiomatization of randomness. The Journal of Symbolic Logic 55, 3 (1990), 1143–1167.
[23]
Alexander K. Zvonkin and Leonid A. Levin. 1970. The complexity of finite objects and the development of the concepts of information and randomness by means of the theory of algorithms. Russian Mathematical Surveys 25, 6 (1970), 83.
Index Terms
- The Intersection of Algorithmically Random Closed Sets and Effective Dimension
Recommendations
Members of Random Closed Sets
CiE '09: Proceedings of the 5th Conference on Computability in Europe: Mathematical Theory and Computational PracticeThe members of Martin-Löf random closed sets under a distribution studied by Barmpalias et al. are exactly the infinite paths through Martin-Löf random Galton-Watson trees with survival parameter $\frac{2}{3}$. To be such a member, a sufficient ...
Random closed sets
CiE'06: Proceedings of the Second conference on Computability in Europe: logical Approaches to Computational BarriersWe investigate notions of randomness in the space ${\mathcal {C}}[2^{\mathbb {N}}]$ of nonempty closed subsets of {0,1}ℕ. A probability measure is given and a version of the Martin-Löf Test for randomness is defined. Π02 random closed sets exist but ...
Comments
Information & Contributors
Information
Published In
October 2022
279 pages
Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected].
Publisher
Association for Computing Machinery
New York, NY, United States
Publication History
Published: 20 October 2022
Online AM: 25 June 2022
Accepted: 15 May 2022
Revised: 17 November 2021
Received: 25 January 2021
Published in TOCL Volume 23, Issue 4
Check for updates
Author Tags
Qualifiers
- Research-article
- Refereed
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- 0Total Citations
- 62Total Downloads
- Downloads (Last 12 months)13
- Downloads (Last 6 weeks)1
Reflects downloads up to 22 Oct 2024
Other Metrics
Citations
View Options
Get Access
Login options
Check if you have access through your login credentials or your institution to get full access on this article.
Sign inFull Access
View options
View or Download as a PDF file.
PDFeReader
View online with eReader.
eReaderFull Text
View this article in Full Text.
Full TextHTML Format
View this article in HTML Format.
HTML Format