Computability- and Category theoretic Perspectives on Descriptive Set Theory
July 16th - 18th 2018
School of Management Room 239
Bay Campus, Swansea University, Swansea, UK

Preliminary Schedule
Monday Tuesday Wednesday
09:30 ITTMs and ordinary differential equations (Sabrina Ouazzani)
10:00 Welcome & Introduction Discussion: Future Collaborations
10:30 Coffee Break Coffee Break Coffee Break
11:00 Computability, Endofunctors & Hypercomputation (Arno Pauly) Hausdorff dimension and Kolmogorov complexity (Don Stull) Proving Sigma^0_3-Determinacy from ITTM's (Philip Welch)
12:00 Writability and reachability for alpha-tape infinite time Turing machines  (Philipp Schlicht) Discussion: Cardinal invariants and counterexampels to the projection theorem A tutorial on domains for computable analysis (Jens Blanck)
13:00 Lunch Lunch Lunch
14:00 Discussion: The ITTM endofunctor Point degree spectra of represented spaces (Arno Pauly) Discussion time & Closing
15:00 Coffee Break Coffee Break
15:30 Coffee Break Excursion  to the Gower, Three Cliffs Bay
16:00 On the complexity of fluctuation bounds for Krasnoselski's iteration (Eike Neumann)

Abstracts

Computability, Endofunctors & Hypercomputation (Arno Pauly) [Slides]
What is the connection between concepts from descriptive set theory such as point classes or classes of measurable or piecewise defined functions, endofunctors on the category of represented spaces, and models of hypercomputation in computable analysis? I'll give some examples from the quest towards an explanation.

Writability and reachability for alpha-tape infinite time Turing machines (Philipp Schlicht)
The writability strength of infinite time Turing machines, that were introduced by Hamkins and Kidder, and their variants is closely related to classes studied in descriptive set theory such as Pi^1_1 and Sigma^1_2. Here we study infinite time Turing machines with tape length alpha (denoted T_alpha), which were introduced by Benjamin Rin to strengthen the omega-tape machines. It was known that for some countable ordinals alpha, these machines’ properties are quite different from those of the omega-tape case, for instance T_alpha might not be able to reach all its cells as halting positions. We show that the least such alpha equals the least alpha that is uncountable in L_{lambda_alpha}, where lambda_alpha is the supremum of halting times of T_alpha. This is joint work with Benjamin Rin and Merlin Carl. 

On the complexity of fluctuation bounds for Krasnoselski's iteration (Eike Neumann)
Consider a 1-Lipschitz self-map of a convex compact subset of a uniformly convex real Banach space. By Schauder's fixed point theorem this map has at least one fixed point. Fixed points of the function can be numerically approximated by Krasnoselski's iteration, where a given point is mapped forward under the function and the result is averaged with the point itself. Krasnoselski's theorem (1955) asserts that this iteration converges to a fixed point for every starting point but does not yield any effective error bounds or rates of convergence.

In fact it can be shown that the problem of finding rates of convergence for Krasnoselski's iteration is uncomputable (Kohlenbach, 2001) and even effectively $\Sigma^0_2$-complete (N, 2015) already over the compact unit interval. Hence, in order to get information about the quality of convergence, logically weaker quantitative versions of the convergence statement have to be considered. Kohlenbach (2001) constructed by means of proof mining uniform primitive recursive rates of asymptotic regularity and metastability for a more general class of iterations. Metastability turns out to be strictly stronger than asymptotic regularity in this case.

It is natural to ask if metastability is somehow best possible or if there is a better quantitative measure of convergence available for the Krasnoselski iteration. For instance, Avigad & Rute (2014) and Kohlenbach & Safarik (2014) have studied fluctuation bounds for various problems, which are stronger than metastability but still weaker than rates of convergence. In this talk I show that the problem of finding fluctuation bounds for the Krasnoselski iteration in separable infinite-dimensional real Hilbert space is again effectively $\Sigma^0_2$-complete.

Hausdorff dimension and Kolmogorov complexity (Don Stull)
In this talk we will discuss recent work, joint with Neil Lutz, which uses tools from computability theory to study problems in fractal geometry. Specifically, we will focus on the Hausdorff dimension of projections of Euclidean sets. Using the Kolmogorov complexity characterization of effective dimension and the point-to-set principle, we will prove two new theorems giving lower bounds on the Hausdorff dimension of projected sets. We will give an overview of this approach, and discuss new research directions.

On the point degree spectrum (Arno Pauly) [Slides]
We can understand topological properties of spaces via the degrees realized by their points. Kihara and P used this connection to answer a decades old question by Jayne on the number of sigma-homeomorphism types of Polish spaces. Recent work by Kihara, Ng and P has traced in detail the connection between countably-based topological spaces and substructures of the enumeration degrees. The talk will be designed to give an overview of what is going on, and what might be waiting for us.

Proving Sigma^0_3-Determinacy from ITTM's (Philip Welch)
We consider higher type recursion in the style of Kleene, where he showed that wellfounded computation trees with Turing machines placed at the nodes calling TM's at immediate sub-nodes as subroutines, form a model of recursion where the semi-recursive sets are the Pi^1_1 sets of integers.   A complete Pi^1_1 set is recursively isomorphic (in the usual Turing sense) to a listing of the open games won by Player I, in other words a G-Sigma^0_1-set. One has a stronger model of recursion by replacing TM's with ITTM's. Analysing the semi-recursive sets in this context allows the results about Sigma^0_1 to be lifted to Sigma^0_3. This study is thus an application of ITTM theory to classical descriptive set theory.

Excursion
The Gower peninsular next to Swansea is an area of astounding beauty, and the current forecast for Tuesday predicts a sunny day. The plan is to take the Bus 82 from Elba Crescent (departing at 3:32pm) to the central bus station, and change to the Bus 118 towards Rhossili there. Scheduled arrival at Shepherds is 4:23pm. A short and not particularly difficult hike brings us to the Three Cliffs Bay, which particularly at low tide offers some nice views.  Accompanying persons are welcome, but will have to buy their own bus ticket (return about £5).