Departmental Colloquium
Patrick Lutz
UC Berkeley
Martin's Conjecture and order-preserving functions
Abstract: 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).
Friday April 19, 2024 at 3:00 PM in 636 SEO