Dr Takayuki Kihara | Weihrauch reducibility on multi-represented spaces

Speaker(s): Dr Takayuki Kihara (Nagoya University) Date: 10 June 2022 - 09:00 to 10:00 Venue: INI Seminar Room 1 Session Title: Weihrauch reducibility on multi-represented spaces Event: [SASW09] International conference on computability, complexity and randomness The notion of Weihrauch reducibility is used to measure the computability-theoretic complexity of search problems (multi-valued functions) and has been studied in depth in recent years in computable analysis and related areas. Weihrauch reducibility corresponds to a relative computation that makes exactly one query to oracle. Often, partial multi-valued functions are identified with $\forall\exists$-statements, and through this identification, the classification of partial multi-valued functions by Weihrauch reducibility is sometimes regarded as a handy analogue of reverse mathematics. The notion of Weihrauch reducibility is usually considered on represented spaces, but in this talk we extend it to multi-represented spaces. We point out that such an extension in important when considering, for example, probabilistic computations. In this talk, we first confirm that our definition of Weihrauch reducibility on multi-represented spaces agrees with extended Weihrauch reducibility (i.e., instance reducibility on the Kleene-Vesley algebra) by Andrej Bauer [1]. Furthermore, by making this notion idempotent (i.e., transforming Weihrauch reducibility into generalized Weihrauch reducibility, or applying the so-called diamond operator), we show that the induced degrees is isomorphic to the Heyting algebra of the Lawvere-Tierney topologies on (so, dually isomorphic to the co-Heyting algebra of subtoposes of) the Kleene-Vesley topos. Since a subtopos can be regarded as a kind of mathematical universe, this provides one explanation for why the study of Weihrauch degrees can be thought of as a kind of reverse mathematics. Regarding the logic aspect, some parts of the internal logic of a sheaf subtopos of the Kleene-Vesley topos can be described as realizability relative to the corresponding Lawvere-Tierney topology and, via the above correspondence, also as realizability relative to the corresponding Weihrauch degree on multi-represented spaces. In this way, for example, one can consider realizability relative to the Weihrauch degree on multi-represented space representing probabilistic computations. [1] Andrej Bauer. Instance reducibility and Weihrauch degrees. arXiv:2106.01734, 18 pages, 2021. [3] Takayuki Kihara. Lawvere-Tierney topologies for computability theorists. arXiv:2106.03061, 35 pages, 2021. [4] Takayuki Kihara. Rethinking the notion of oracle: A link between synthetic descriptive set theory and effective topos theory. arXiv:2202.00188, 48 pages, 2022.