1 Relative computability and uniform continuity of relations

Abstract: A type-2 computable real function is necessarily continuous; and this remains true for computations relative to any oracle. Conversely, by the Weierstrass Approximation Theorem, every continuous f: [0; 1] → R is computable relative to some oracle. In their search for a similar topological characterization of relatively computable multi-valued functions f: [0; 1] ⇒ R (also known as multi-functions or relations), Brattka and Hertling (1994) have considered two notions: weak continuity (which is weaker than relative computability) and strong continuity (which is stronger than relative computability). Observing that uniform continuity plays a crucial role in the Weierstrass Theorem, we propose and compare several notions of uniform continuity for relations. Here, due to the additional quantification over values y ∈ f (x), new ways arise of (linearly) ordering quantifiers—yet none turns out as satisfactory. We are thus led to a concept of uniform continuity based on the Henkin quantifier; and prove it necessary for relative computability of compact real relations. In fact iterating this condition yields a strict hierarchy of notions each necessary — and the ω-th level also sufficient — for relative computability. A refined, quantitative analysis exhibits a similar topological characterization of relative polynomial-time computability