[logic-ml] JAIST Logic Seminar Series

[Hajime Ishihara]

皆様

JAIST Logic Seminar Seriesのお知らせです。
ふるってご参加ください。

問合せ先：
石原　哉
北陸先端科学技術大学院大学 情報科学研究科
e-mail: ishihara at jaist.ac.jp

--------------------------------------------------
* 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.

-- 
Professor Hajime Ishihara
School of Information Science
Japan Advanced Institute of Science and Technology
1-1 Asahidai, Nomi, Ishikawa 923-1292, Japan
Tel: +81-761-51-1206
Fax: +81-761-51-1149
ishihara at jaist.ac.jp
http://www.jaist.ac.jp/~ishihara