Skip to Main content Skip to Navigation
Conference papers

Semicomputable geometry

Mathieu Hoyrup 1 Diego Nava Saucedo 1 Donald Stull 1
1 MOCQUA - Designing the Future of Computational Models
Inria Nancy - Grand Est, LORIA - FM - Department of Formal Methods
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.
Complete list of metadata

Cited literature [15 references]  Display  Hide  Download

https://hal.inria.fr/hal-01770562
Contributor : Mathieu Hoyrup <>
Submitted on : Thursday, April 19, 2018 - 11:32:36 AM
Last modification on : Tuesday, December 18, 2018 - 4:38:25 PM
Long-term archiving on: : Tuesday, September 18, 2018 - 12:45:09 PM

Identifiers

  • HAL Id : hal-01770562, version 1

Collections

Citation

Mathieu Hoyrup, Diego Nava Saucedo, Donald Stull. Semicomputable geometry. ICALP 2018 - 45th International Colloquium on Automata, Languages, and Programming, Jul 2018, Prague, Czech Republic. ⟨hal-01770562⟩

Share

Metrics

Record views

269

Files downloads

211