BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//Talks.cam//talks.cam.ac.uk//
X-WR-CALNAME:Talks.cam
BEGIN:VEVENT
SUMMARY:Weihrauch reducibility on multi-represented spaces - Takayuki Kiha
 ra (Nagoya University)
DTSTART:20220610T080000Z
DTEND:20220610T090000Z
UID:TALK174839@talks.cam.ac.uk
DESCRIPTION:The notion of Weihrauch reducibility is used to measure the co
 mputability-theoretic complexity of search problems (multi-valued function
 s) and has been studied in depth in recent years in computable analysis an
 d related areas. Weihrauch reducibility corresponds to a relative computat
 ion that makes exactly one query to oracle. Often\, partial multi-valued f
 unctions are identified with $\\forall\\exists$-statements\, and through t
 his identification\, the classification of partial multi-valued functions 
 by Weihrauch reducibility is sometimes regarded as a handy analogue of rev
 erse mathematics. The notion of Weihrauch reducibility is usually consider
 ed on represented spaces\, but in this talk we extend it to multi-represen
 ted spaces. We point out that such an extension in important when consider
 ing\, for example\, probabilistic computations.\nIn this talk\, we first c
 onfirm that our definition of Weihrauch reducibility on multi-represented 
 spaces agrees with extended Weihrauch reducibility (i.e.\, instance reduci
 bility on the Kleene-Vesley algebra)&nbsp\;by Andrej Bauer [1]. Furthermor
 e\, by making this notion idempotent (i.e.\, transforming Weihrauch reduci
 bility 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 isomorp
 hic to the co-Heyting algebra of subtoposes of) the Kleene-Vesley topos. S
 ince a subtopos can be regarded as a kind of mathematical universe\, this 
 provides one explanation for why the study of Weihrauch degrees can be tho
 ught of as a kind of reverse mathematics.\nRegarding the logic aspect\, so
 me parts of the internal logic of a sheaf subtopos of the Kleene-Vesley to
 pos can be described as realizability relative to the corresponding Lawver
 e-Tierney topology and\, via the above correspondence\, also as realizabil
 ity relative to the corresponding Weihrauch degree on multi-represented sp
 aces. In this way\, for example\, one can consider realizability relative 
 to the Weihrauch degree on multi-represented space representing probabilis
 tic computations.\n[1] Andrej Bauer. Instance reducibility and Weihrauch d
 egrees. arXiv:2106.01734\, 18 pages\, 2021.[3] Takayuki Kihara. Lawvere-Ti
 erney topologies for computability theorists. arXiv:2106.03061\, 35 pages\
 , 2021.[4] Takayuki Kihara. Rethinking the notion of oracle: A link betwee
 n synthetic descriptive set theory and effective topos theory. arXiv:2202.
 00188\, 48 pages\, 2022.
LOCATION:Seminar Room 1\, Newton Institute
END:VEVENT
END:VCALENDAR