Relative computability and uniform continuity of relations

Arno M Pauly, Martin A. Ziegler


A type-2 computable real function is necessarily continuous; and this remains true for relative, i.e. oracle-based, computations. Conversely, by the Weierstrass Approximation Theorem, every continuous f:[0,1]→ℝ is computable relative to some oracle.
In their search for a similar topological characterization of relatively computable multi-valued functions f:[0,1]⇒ℝ (aka 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 yf(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.

Full Text:

7. [PDF]


Creative Commons License
This work is licensed under a Creative Commons Attribution 3.0 License.

Journal of Logic and Analysis ISSN:  1759-9008