Computations, countable ranks and complexity of Borel codes

Philipp Schlicht (U Siena)

Jul 02. 2025, 16:00 — 16:45

The decision time of an infinite time algorithm is the supremum of halting times for real inputs. More abstractly, it is the length of a certain rank on a subset of the Cantor space. We are interested in cases where these ordinals are countable and discuss results on their supremum and on the converse problem which subsets of the Cantor space admit a rank of countable length (at the second level of the Borel hierarchy). The results lead to the problem of the complexity of codes for projective (without parameters) Borel sets in analogy with Louveau's separation theorem. We describe partial results based on a recent paper with Merlin Carl and Philip Welch. 

Further Information
Venue:
ESI Schrödinger and Boltzmann Lecture Hall
Recordings:
Recording
Associated Event:
Reverse Mathematics (Thematic Programme)
Organizer(s):
Juan Aguilera (TU Vienna)
Linda Brown Westrick (Penn State U)
Noam Greenberg (Victoria U of Wellington)
Denis Hirschfeldt (U of Chicago)