Schedule for: 23w5039 - Recursion Theory and its Applications

Breakfast is served daily between 7 and 9am in the Xianghu Lake National Tourist Resort

A brief introduction to IASM with important logistical information, technology instruction, and opportunity for participants to ask questions.

Lunch is served daily between 11:30am and 1:30pm in the Xianghu Lake National Tourist Resort

A compact metrizable space has computable type if for every set that is homeomorphic to that space, semicomputability is equivalent to computability. J. Miller proved that spheres have computable type, and Iljazović proved that closed manifolds have computable type. Čelar and Iljazović asked whether the product of two spaces having computable type also has computable type. We give a negative answer to that question, providing a finite simplicial complex having computable type, but whose product with the circle does not. The construction heavily relies on classical results on homotopy groups of spheres and suspensions.

Breakfast is served daily between 7 and 9am in the Xianghu Lake National Tourist Resort

I will talk about how information in a recursive enumeration can be compressed, in the sense of relative Kolmogorov complexity (rK). We introduce a strong and a weak form of compression, and we also care about the gain of compressions. It turns out that the existence of strong gainless compression is a key to provide a join operator on r.e. rK degrees, making the degree structure dense. I'll show that strong compression and weak gainless compression exist for any recursive enumeration. I'll also talk about a positional game that is crucial toward obtaining a strong gainless compression.

The tower number and ultrafilter numbers are cardinal characteristics from set theory that are defined in terms of sets of natural numbers with almost inclusion. The former is the least size of a maximal tower. The latter is the least size of a collection of infinite sets with upward closure a non-principal ultrafilter. Their analogs in computability theory will be defined in terms of collections of computable sets, given as the columns of a single set. We study their complexity using Medvedev reducibility. For instance, we show that the ultrafilter number is Medvedev equivalent to the problem of finding a function that dominates all computable functions, that is, highness. In contrast, each nonlow set uniformly computes a maximal tower. Reference: Lempp, S., Miller, J. S., Nies, A., & Soskova, M. I. (2023). Maximal Towers and Ultrafilter Bases in Computability Theory. The Journal of Symbolic Logic, 88(3), 1170-1190.

I will discuss several recent results in computable topology that establish direct connections between computable structure theory and the theory of recursive Polish spaces through recently developed effective dualities. The proofs of these dualities make use of a diverse range of techniques. I will also discuss a few applications of these effective dualities that appear to be rather fundamental in the theory of effectively presented Polish spaces.

We report on ongoing work with Belanger and Dzhafarov. In our study of the computational strength of finite pigeonhole principles (in the Weihrauch lattice), we applied combinatorial results such as graph decomposition theorems and Turán's theorem in extremal graph theory. We then discovered that certain questions we were unable to resolve were in fact equivalent to longstanding open problems in combinatorics. We shall present such results, as well as results on the relationships between jumps of finite pigeonhole principles and well-studied problems in the Weihrauch lattice.

Abstract: Floyd and Knuth studied in their 1990 paper addition machines which are machines which can add, subtract and compare integers (<,=,>) in unit time; also the reading or writing of an integer is in unit time. They showed that multiplying and dividing can be done in linear time with six registers and asked in theirOpen Problem (2) whether this bound can be broken; furthermore, they asked in Open Problem (5) of their paper whether there is a register machine which can output in subquadratic time the powers of two occurring in the binary representation of an integer. The talk answers both questions affirmatively and presents the key ideas and programs to witness this. The slides for the joint paper on addition machines are on https://www.comp.nus.edu.sg/~fstephan/logicseminar.html#weeknine A technical report version of the paper is on https://arxiv.org/abs/2111.08969 The paper appeared in the Journal of Computer and System Sciences volume 136, pages 135-156, 2023.

In this talk, I will propose a formalization of computability over finite type objects. Most of the talk is based on an ongoing joint work with Keng Meng Ng from Nanyang Techno- logical University, Singapore and Nazanin Tavana from Amirkabir University of Technology, Iran.

The consistency checking problem for algebraic delay PDEs seeks for a general method or algorithm to determine whether an arbitrarily given system of delay PDEs has a sequence solution. We solve this problem positively by proving the effective partial differential-difference Nullstellensatz, in which we show the existence of a uniform upper bound for the number of iterated applications of the distinguished difference and derivation operators, for a reduction of this consistency-checking problem to a well-studied consistency-checking problem for polynomial equations. The main approach is our technical result about algorithms performing computations in complete decidable theories, which shows that if an algorithm performing computations restricted to definable functions is guaranteed to terminate on every input, then there is a computable upper bound for the size of the output of the algorithm in terms of the size of the input. This is joint work with A. Ovchinnikov, G. Pogudin and T. Scanlon.

A tree is path-random if all of its paths are algorithmically random. Path-random trees are building blocks for models of tree-versions of Weak Konig's Lemma. Diagonalizing agains path-random trees can be challenging. We will discuss an array of such separations: positive measure trees from perfect, finite versus infinite paths and perfect from trees with one limit point. Key open questions remain, and will be presented.

A fundamental problem in abelian group theory is to decide Ext(C,A), which is the group of all extensions of C by A. We investigate the reverse mathematical strength of various statements on extensions of abelian groups.