Semicomputable points in Euclidean spaces

Mathieu Hoyrup (1) , Donald M Stull (1)

1 MOCQUA - Designing the Future of Computational Models

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.

Mots clés: Solovay reducibility; Convex cone; Genericity; Semicomputable point; Left-c.e. real

Domaines: Logique en informatique [cs.LO]

Mathieu Hoyrup, Donald M Stull. Semicomputable points in Euclidean spaces. MFCS 2019 - 44th International Symposium on Mathematical Foundations of Computer Science, Aug 2019, Aachen, Germany. ⟨10.4230/LIPIcs.MFCS.2019.63⟩. ⟨hal-02154825⟩