Departmental Colloquium: Martin’s Conjecture and order-preserving functions, by Patrick Lutz
April 19, 2024
3:00 PM - 3:50 PM
Patrick Lutz (UC Berkeley): Martin's Conjecture and order-preserving functions
The field of computability theory studies the complexity of uncomputable problems. In this study, a special role is played by the Halting Problem. Not only is it the first problem proved to be uncomputable, it also seems to be the simplest "natural" uncomputable problem. Martin's Conjecture is a long-standing open problem in computability theory which gives a partial explanation for this phenomenon. A key idea behind Martin's Conjecture is to view the Halting Problem not just as a problem, but as an operator on problems, which takes any problem to a strictly harder one. Martin's Conjecture consists of a classification of such operators, which says, in part, that the Halting Problem is the minimal non-trivial operator. I will discuss the background and motivation for Martin's Conjecture, as well as recent progress by Benjamin Siskind and myself which essentially completes a proof of the conjecture for a special class of operators called "order-preserving" (i.e. those which preserve the relative complexity of problems).
Please click here to make changes to, or delete, this seminar announcement.
Date posted
Apr 25, 2024
Date updated
Apr 25, 2024
Speakers
