LIPIcs.MFCS.2019.48.pdf
- Filesize: 469 kB
- 13 pages
Document
Semicomputable Points in Euclidean Spaces
Authors
-
Part of:
Volume:
44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019)
Series: Leibniz International Proceedings in Informatics (LIPIcs)
Conference: Mathematical Foundations of Computer Science (MFCS) - License:
Creative Commons Attribution 3.0 Unported license
- Publication Date: 2019-08-20
Cite As Get BibTex
Mathieu Hoyrup and Donald M. Stull. Semicomputable Points in Euclidean Spaces. In 44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 138, pp. 48:1-48:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
https://doi.org/10.4230/LIPIcs.MFCS.2019.48
Abstract
We introduce the notion of a semicomputable point in R^n, defined as a point having left-c.e. projections. We study the range of such a point, which is the set of directions on which its projections are left-c.e., and is a convex cone. We provide a thorough study of these notions, proving along the way new results on the computability of convex sets. We prove realization results, by identifying computability properties of convex cones that make them ranges of semicomputable points. We give two applications of the theory. The first one provides a better understanding of the Solovay derivatives. The second one is the investigation of left-c.e. quadratic polynomials. We show that this is, in fact, a particular case of the general theory of semicomputable points.
Subject Classification
ACM Subject Classification
- Theory of computation → Computability
Keywords
- Semicomputable point
- Left-c.e. real
- Convex cone
- Solovay reducibility
- 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.
-
Stephen Boyd and Lieven Vandenberghe. Convex Optimization. Cambridge University Press, New York, NY, USA, 2004.
-
Vasco Brattka and Gero Presser. Computability on subsets of metric spaces. Theoretical Computer Science, 305(1-3):43-76, 2003.
-
Mathieu Hoyrup. Genericity of Weakly Computable Objects. Theory Comput. Syst., 60(3):396-420, 2017.
-
Mathieu Hoyrup, Diego Nava Saucedo, and Don M. Stull. Semicomputable Geometry. In Ioannis Chatzigiannakis, Christos Kaklamanis, Dániel Marx, and Donald Sannella, editors, 45th International Colloquium on Automata, Languages, and Programming, ICALP 2018, July 9-13, 2018, Prague, Czech Republic, volume 107 of LIPIcs, pages 129:1-129:13. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 2018.
-
Martin Kummer and Marcus Schäfer. Computability of convex sets. In Ernst W. Mayr and Claude Puech, editors, STACS 95, pages 550-561, Berlin, Heidelberg, 1995. Springer Berlin Heidelberg.
-
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.
-
Martin Ziegler. Computability on Regular Subsets of Euclidean Space. Mathematical Logic Quarterly, 48(S1):157-181, 2002.