BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//talks.cam.ac.uk//v3//EN
BEGIN:VTIMEZONE
TZID:Europe/London
BEGIN:DAYLIGHT
TZOFFSETFROM:+0000
TZOFFSETTO:+0100
TZNAME:BST
DTSTART:19700329T010000
RRULE:FREQ=YEARLY;BYMONTH=3;BYDAY=-1SU
END:DAYLIGHT
BEGIN:STANDARD
TZOFFSETFROM:+0100
TZOFFSETTO:+0000
TZNAME:GMT
DTSTART:19701025T020000
RRULE:FREQ=YEARLY;BYMONTH=10;BYDAY=-1SU
END:STANDARD
END:VTIMEZONE
BEGIN:VEVENT
CATEGORIES:Isaac Newton Institute Seminar Series
SUMMARY:Weihrauch reducibility on multi-represented spaces
- Takayuki Kihara (Nagoya University)
DTSTART;TZID=Europe/London:20220610T090000
DTEND;TZID=Europe/London:20220610T100000
UID:TALK174839AThttp://talks.cam.ac.uk
URL:http://talks.cam.ac.uk/talk/index/174839
DESCRIPTION:The notion of Weihrauch reducibility is used to me
asure the computability-theoretic complexity of se
arch problems (multi-valued functions) and has bee
n studied in depth in recent years in computable a
nalysis and related areas. Weihrauch reducibility
corresponds to a relative computation that makes e
xactly one query to oracle. Often\, partial multi-
valued functions are identified with $\\forall\\ex
ists$-statements\, and through this identification
\, the classification of partial multi-valued func
tions by Weihrauch reducibility is sometimes regar
ded as a handy analogue of reverse mathematics. Th
e notion of Weihrauch reducibility is usually cons
idered on represented spaces\, but in this talk we
extend it to multi-represented spaces. We point o
ut that such an extension in important when consid
ering\, for example\, probabilistic computations.\
nIn this talk\, we first confirm that our definiti
on of Weihrauch reducibility on multi-represented
spaces agrees with extended Weihrauch reducibility
(i.e.\, instance reducibility on the Kleene-Vesle
y algebra) \;by Andrej Bauer [1]. Furthermore\
, by making this notion idempotent (i.e.\, transfo
rming Weihrauch reducibility into generalized Weih
rauch reducibility\, or applying the so-called dia
mond operator)\, we show that the induced degrees
is isomorphic to the Heyting algebra of the Lawver
e-Tierney topologies on (so\, dually isomorphic to
the co-Heyting algebra of subtoposes of) the Klee
ne-Vesley topos. Since a subtopos can be regarded
as a kind of mathematical universe\, this provides
one explanation for why the study of Weihrauch de
grees can be thought of as a kind of reverse mathe
matics.\nRegarding the logic aspect\, some parts o
f the internal logic of a sheaf subtopos of the Kl
eene-Vesley topos can be described as realizabilit
y relative to the corresponding Lawvere-Tierney to
pology and\, via the above correspondence\, also a
s realizability relative to the corresponding Weih
rauch degree on multi-represented spaces. In this
way\, for example\, one can consider realizability
relative to the Weihrauch degree on multi-represe
nted space representing probabilistic computations
.\n[1] Andrej Bauer. Instance reducibility and Wei
hrauch degrees. arXiv:2106.01734\, 18 pages\, 2021
.[3] Takayuki Kihara. Lawvere-Tierney topologies f
or computability theorists. arXiv:2106.03061\, 35
pages\, 2021.[4] Takayuki Kihara. Rethinking the n
otion of oracle: A link between synthetic descript
ive set theory and effective topos theory. arXiv:2
202.00188\, 48 pages\, 2022.
LOCATION:Seminar Room 1\, Newton Institute
CONTACT:
END:VEVENT
END:VCALENDAR