LIPIcs.ICALP.2018.129.pdf
- Filesize: 0.5 MB
- 13 pages
Document
Semicomputable Geometry
Authors
-
Part of:
Volume:
45th International Colloquium on Automata, Languages, and Programming (ICALP 2018)
Series: Leibniz International Proceedings in Informatics (LIPIcs)
Conference: International Colloquium on Automata, Languages, and Programming (ICALP) - License:
Creative Commons Attribution 3.0 Unported license
- Publication Date: 2018-07-04
Cite As Get BibTex
Mathieu Hoyrup, Diego Nava Saucedo, and Don M. Stull. Semicomputable Geometry. In 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 107, pp. 129:1-129:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
https://doi.org/10.4230/LIPIcs.ICALP.2018.129
Abstract
Computability and semicomputability of compact subsets of the Euclidean spaces are important notions, that have been investigated for many classes of sets including fractals (Julia sets, Mandelbrot set) and objects with geometrical or topological constraints (embedding of a sphere). In this paper we investigate one of the simplest classes, namely the filled triangles in the plane. We study the properties of the parameters of semicomputable triangles, such as the coordinates of their vertices. This problem is surprisingly rich. We introduce and develop a notion of semicomputability of points of the plane which is a generalization in dimension 2 of the left-c.e. and right-c.e. numbers. We relate this notion to Solovay reducibility. We show that semicomputable triangles admit no finite parametrization, for some notion of parametrization.
Subject Classification
ACM Subject Classification
- Theory of computation → Computability
Keywords
- Computable set
- Semicomputable set
- Solovay reducibility
- Left-ce real
- Genericity
Metrics
- Access Statistics
-
Total Accesses (updated on a weekly basis)
0PDF Downloads
References
-
George Barmpalias and Andrew Lewis-Pye. Differences of halting probabilities. J. Comput. Syst. Sci., 89:349-360, 2017.
-
Mark Braverman and Michael Yampolsky. Computability of Julia Sets. Springer, 2008.
-
Konrad Burnik and Zvonko Iljazovic. Computability of 1-manifolds. Logical Methods in Computer Science, 10(2), 2014.
-
Rod Downey and Denis Hirschfeldt. Algorithmic Randomness and Complexity. Springer-Verlag New York, Inc., Secaucus, NJ, USA, 2010.
-
Daniel Graça, Cristóbal Rojas, and Ning Zhong. Computing geometric Lorenz attractors with arbitrary precision. To appear in Transactions of the American Mathematical Society, 2017.
-
Peter Hertling. Is the Mandelbrot set computable? Math. Log. Q., 51(1):5-18, 2005.
-
Mathieu Hoyrup. Genericity of weakly computable objects. Theory Comput. Syst., 60(3):396-420, 2017.
-
Zvonko Iljazovic. Co-c.e. spheres and cells in computable metric spaces. Logical Methods in Computer Science, 7(3), 2011.
-
Joseph S. Miller. Effectiveness for embedded spheres and balls. Electronic Notes in Theoretical Computer Science, 66(1):127-138, 2002. CCA 2002, Computability and Complexity in Analysis (ICALP 2002 Satellite Workshop).
-
Joseph S. Miller. On work of Barmpalias and Lewis-Pye: A derivation on the D.C.E. reals. In Adam R. Day, Michael R. Fellows, Noam Greenberg, Bakhadyr Khoussainov, Alexander G. Melnikov, and Frances A. Rosamond, editors, Computability and Complexity - Essays Dedicated to Rodney G. Downey on the Occasion of His 60th Birthday, volume 10010 of Lecture Notes in Computer Science, pages 644-659. Springer, 2017.
-
André Nies. Computability and randomness. Oxford logic guides. Oxford University Press, 2009.
-
Robert Rettinger and Xizhong Zheng. Solovay reducibility on d-c.e real numbers. In Lusheng Wang, editor, Computing and Combinatorics, 11th Annual International Conference, COCOON 2005, Kunming, China, August 16-29, 2005, Proceedings, volume 3595 of Lecture Notes in Computer Science, pages 359-368. Springer, 2005.
-
B. Schroeder. Ordered Sets: An Introduction. Birkhäuser Boston, 2003.
-
Klaus Weihrauch and T. Deil. Berechenbarkeit auf cpo-s. Informatik-Berichte, 63, 1980.
-
Xizhong Zheng and Robert Rettinger. On the extensions of Solovay-reducibility. In Kyung-Yong Chwa and J. Ian Munro, editors, Computing and Combinatorics, 10th Annual International Conference, COCOON 2004, Jeju Island, Korea, August 17-20, 2004, Proceedings, volume 3106 of Lecture Notes in Computer Science, pages 360-369. Springer, 2004.