Philipp Schlicht - Computations, countable ranks and complexity of Borel codes

This talk was part of the Workshop on "Reverse Mathematics and Higher Computability Theory" held at the ESI June 30 - July 4, 2025.

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.

Видео Philipp Schlicht - Computations, countable ranks and complexity of Borel codes канала Erwin Schrödinger International Institute for Mathematics and Physics (ESI)