皆様
JAIST Logic Seminar Seriesのお知らせです。 ふるってご参加ください。
問合せ先： 石原 哉 北陸先端科学技術大学院大学 情報科学研究科 e-mail: [email protected]
-------------------------------------------------- * JAIST Logic Seminar Series *
* This seminar is held as a part of the EU FP7 Marie Curie Actions IRSES project COMPUTAL (http://computal.uni-trier.de/).
Date: Monday 29 July, 2013, 15:00-17:00
Place: JAIST, Collaboration room 7 (I-56) (Access: http://www.jaist.ac.jp/english/location/access.html)
Speaker: Professor Martin Ziegler (Technische Universitaet Darmstadt)
Title: HENKIN CONTINUITY OF MULTIVALUED FUNCTIONS (joint work with Arno Pauly)
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 $f:[0;1]\to\mathbb{R}$ is computable relative to some oracle.
In their search for a similar topological characterization of relatively computable \emph{multi-}valued functions $f:[0;1]\rightrightarrows\mathbb{R}$ (aka 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 \emph{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 arise of (linearly) ordering quantifiers---yet none turns out as satisfactory.
We are thus led to a concept of uniform continuity based on the \textsf{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 $\omega$-th level also sufficient --- for relative computability. A refined, quantitative analysis exhibits a similar topological characterization of relative polynomial-time computability.