Andrej Bauer: The synthetic Kleene-Post theorem
Date of publication: 17. 12. 2024
Mathematics and theoretical computing seminar
Thursday
19
December
Time:
10:00 - 12:00
Location:
Jadranska 21, učilnica 3.07
Abstract: The Kleene-Post theorem claims that there exist incomparable Turing degrees, i.e., oracles such that no Turing machine reduces one to the other. We shall give a proof of the theorem in the context of synthetic computability, in which the theorem takes the form of a domain-theoretic variant of Baire category theorem in which topolological notions are modal in the sense of Swan's oracle modalities.
This is joint work with Andrew Swan.