Relative computability and uniform continuity of relations
Pauly, Ziegler · Journal of Logic and Analysis · 2013
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.