Effectiveness for embedded spheres and balls Abstract

We consider arbitrary dimensional spheres and closed balls embedded in R n as Π 0 1 classes. Such a strong restriction on the topology of a Π0 1 class has computability theoretic repercussions. Algebraic topology plays a crucial role in our exploration of these consequences; the use of homology chains as computational objects allows us to take algorithmic advantage of the topological structure of our Π0 1 classes. We show that a sphere embedded as a Π0 1 class is necessarily located, i.e., the distance to the class is a computable function, or equivalently, the class contains a computably enumerable dense set of computable points. Similarly, a ball embedded as a Π0 1 class has a dense set of computable points, though not necessarily c.e. To prove location for balls, it is sufficient to assume that both it and its boundary sphere are Π0 1. However, the converse fails, even for arcs; using a priority argument, we prove that there is a located arc in R2 without computable endpoints. Finally, the requirement that the embedding map itself be computable is shown to be stronger than the other effectiveness criteria considered. A characterization in terms of computable local contractibility is stated; the proof will be the subject of a sequel.