Preskoči na glavno vsebino

Andrej Bauer: The synthetic Kleene-Post theorem

Datum objave: 17. 12. 2024
Seminar za temelje matematike in teoretično računalništvo
četrtek
19
december
Ura:
10.00 - 12.00
Lokacija:
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.