A machine processing Klein bottles into strings of bits.

Descriptive complexity on non-Polish spaces

Consider a space (like \(\mathbb{R}\) for example). Similarly to traditional computability theory (that encodes elements of \(\mathbb{N}\) to finite strings of bits), we encode every element of the space with infinite sequences of bits. Then, we ask the following question: how can we describe the complexity of any subset \(A\) of this space?

There are two possible approaches to this question. The first is descriptive set theory, which classifies sets according to their topological properties. The second is algorithmic, and considers the complexity of an algorithm deciding whether a point belong in \(A\) or not. In this talk, we show that these two approaches are equivalent in the context of countably-based spaces, but that they do not agree on the space of real polynomials (a famous example of coPolish space). We then relate this mismatch between these two notions of complexity to the mismatch between the topological and sequential aspects of the topology.

For more details, you can read the associated article!