### Relative computability and uniform continuity of relations

#### Abstract

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

In their search for a similar topological characterization of relatively computable

We are thus led to a concept of uniform continuity based on the

*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*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.#### Full Text:

7. [PDF]DOI: https://doi.org/10.4115/jla.2013.5.7

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

Journal of Logic and Analysis ISSN: 1759-9008