Mathematics – Logic
Scientific paper
2011-05-16
Mathematics
Logic
23 pages, 5 figures
Scientific paper
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]->R is computable relative to some oracle. In their search for a similar topological characterization of relatively computable multivalued functions f:[0,1]=>R (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 in f(x), new ways of (linearly) ordering quantifiers arise, yet none of them turn out as satisfactory. We are thus led to a notion of uniform continuity based on the Henkin Quantifier; and prove it necessary for relative computability. In fact iterating this condition yields a strict hierarchy of notions each necessary, and the omega-th level also sufficient, for relative computability.
Pauly Arno
Ziegler Martin
No associations
LandOfFree
Relative Computability and Uniform Continuity of Relations does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Relative Computability and Uniform Continuity of Relations, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Relative Computability and Uniform Continuity of Relations will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-77187