[CS] Tiago Royer Dissertation Defense/Jul 3, 2025

[via cs]

This is an announcement of Tiago Royer's Dissertation Defense.
===============================================
Candidate: Tiago Royer

Date: Thursday, July 03, 2025

Time:  9 am CST


Location: JCL 298

Title: Asymptotic Notions of Computability

Abstract: In computability theory, the classical definition of a Turing machine M solving a problem requires M to always halt and always give the right answer. If we relax the "always" to "almost always", we give rise to asymptotic notions of computability, where now M halts and gives correct answers only asymptotically always. There are four asymptotic notions of computability: generic, coarse, dense, and effective dense computability.

This dissertation studies these asymptotic notions of computability, specifically the degree structures arising from the associated reducibilities. Two of the main results concerns minimal pairs: pairs of sets which are both noncomputable, and which have no common computational power. We prove that there are only measure-0 many minimal pairs for the generic degrees (which is in contrast with the classic Turing degrees, for which there are measure-1 many minimal pairs) and construct a $\Delta^0_2$ minimal pair for the coarse degrees.

The third main result concerns attractive degrees. The formalization of the asymptotic notions of computability can be generalized to provide a notion of distance between Turing degrees, called the Hausdorff distance H. It turns out that for every set A, there are either measure-1 many sets which are at a distance 1 from A, or there are measure-1 many such sets which are at a distance 1/2 from A. The former are called dispersive, and the latter are called attractive. We provide a Kolmogorov-complexity flavored sufficient condition for a set to be attractive.

Advisors: Denis Hirschfeldt, Janos Simon

Committee: Denis Hirschfeldt, Stuart Kurtz, Janos Simon

Zoom Link https://uchicago.zoom.us/j/94392607719?pwd=jvl6EyKaAJyE3LKcAxdrEUIldpHhzz.1

Advisors: Janos Simon