Date/Time : 05 Mar 2025 17:00
Venue : S17 #04-04 (SR3)
Speaker : Subin Pulari, LaBRI

Measuring the informational content of real numbers has been a significant area of inquiry in algorithmic information theory. Finite-state compressibility (or finite-state dimension) of a real number is a value in [0, 1] which quantifies the amount of information/randomness in the real number as measured using finite-state automata. Finite-state dimension is the lower asymptotic ratio of compression achievable on an infinite string using information-lossless finite-state compressors. Interestingly, the finite-state dimension of a real number is also equal to the block Shannon entropy rate of the infinite sequence representing the expansion of the real number in a base b. A line of work, originating from Schnorr and Stimm (1972), has established that a number is Borel normal in base b if and only if its base b expansion has finite-state compressibility equal to 1, i.e., is incompressible. Hence, normal numbers are precisely the class of numbers that are incompressible using finite-state compressors.

Most of the prior research on finite-state dimension has relied on combinatorial methods. In this talk we explore how tools from Fourier analysis can be employed to gain new insights into the compressibility of real numbers by solving an open question posed by Lutz and Mayordomo regarding the existence of absolutely dimensioned numbers.

Absolutely normal numbers, being finite-state incompressible in every base of expansion, are precisely those numbers which have finite-state dimension equal to 1 in every base. At the other extreme, for example, every rational number has 0 finite-state dimension in every base. Generalizing this, Lutz and Mayordomo asked the following question: Does there exist any s strictly between 0 and 1 and a real number r such that r has finite state dimension equal to s in every base?. In this talk we use several tools involving exponential sums and techniques from Schmidt’s work in 1960 to construct, for any given s in (0,1], a real number r having finite-state compressibility equal to s in every base.

We also discuss further applications of exponential sums in analyzing and characterizing the finite-state compressibility of real numbers.

Add to calendar :

Date/Time : 19 Feb 2025 17:00
Venue : S17 #04-04 (SR3)
Speaker : Makoto Tatsuta, National Institute of Informatics

Separation logic is successful for software verification of heap-manipulating programs. Numbers are necessary to be added to separation logic for verification of practical software where numbers are important. However, properties of the validity such as decidability and complexity for separation logic with numbers have not been fully studied yet. This paper presents the translation of Pi-0-1 formulas in Peano arithmetic to formulas in a small fragment of separation logic with numbers, which consists only of the intuitionistic points-to predicate, 0 and the successor function.
Then this paper proves that a formula in Peano arithmetic is valid in the standard model if and only if its translation in this fragment is valid in the standard interpretation. As a corollary, this paper also gives a perspective proof for the undecidability of the validity in this fragment. Since Pi-0-1 formulas can describe consistency of logical systems and non-termination of computations, this result also shows that these properties discussed in Peano arithmetic can also be discussed in such a small fragment of separation logic with numbers.

Add to calendar :

Date/Time : 05 Feb 2025 17:00
Venue : S17 #04-04 (SR3)
Speaker : Frank Stephan, National University of Singapore

The talk presents joint work with David Belanger (Singapore), C.T.~Chong (Singapore), Rupert Hoelzl (Munich), Gordon Hoi (Singapore), Sanjay Jain (Singapore), Dilip Raghavan (Singapore), Frank Stephan (Singapore), Daniel Turetsky (Wellington) and Jing Zhang (Toronto) published in four papers. The first one dealt with comparing the growth behaviour of functions or families of functions partial-recursive relative to an oracle and classified oracles with respect to this measure. The second, third and fourth papers are about reverse mathematics and study weakly represented families, that are families of functions computed relative to some oracle in the second order part of the model (all functions in the family use the same oracle). These families are used as a tool to define notions like dominated (every weakly represented family is dominated by some function in the model), hyperimmune, biimmune and so on. Furthermore, one can such families also use as a hypothesis space for classes to be learnt – this extends the study to inductive inference. This is a survey talk with sample proofs.

Add to calendar :

Date/Time : 18 Dec 2024 17:00
Venue : S17 #05-11 (SR5)
Speaker : Manlio Valenti, Swansea University

Recall that, in a partial order P, b is a minimal cover of b if the interval (a,b) is empty. A strengthening of this notion is the one of strong minimal cover, namely b is a strong minimal cover of a if c<b implies c\le a. In this talk, we provide a complete characterization of how minimal covers and strong minimal covers in the Weihrauch degrees look like. As a consequence, we obtain that the Weihrauch degree of the identity problem id can be defined as the highest top of a strong minimal cover, or the least degree whose upper cone is dense. In other words, “being (uniformly) computable” is a first-order definable property in (W,<). This implies that the first-order theory of the Weihrauch degrees (below id) is recursively isomorphic to the third-order theory of true arithmetic.

This is joint work with Steffen Lempp, Joe Miller, Arno Pauly, and Mariya Soskova.

Add to calendar :

Date/Time : 26 Nov 2024 14:00
Venue : S16 #05-18
Speaker : Patrick Lutz, University of California, Berkeley

Recently, there has been a spate of work applying tools from computability theory to prove theorems about Hausdorff dimension and packing dimension. Central to these applications are computability-theoretic analogues of Hausdorff dimension and packing dimension, known respectively as effective Hausdorff dimension and effective packing dimension. A fact which is useful for many applications is that for sufficiently simple sets—in particular, for Pi-0-1 sets—Hausdorff dimension and effective Hausdorff dimension agree. Unfortunately, the corresponding statement for packing dimension is known to fail. In particular, an example due to Conidis shows that there is a Pi-0-1 set of packing dimension 0 and effective packing dimension 1. In this talk, I will consider the question of exactly how bad this failure is. In particular, given a Pi-0-1 set E, what is the minimum complexity of an oracle A for which the packing dimension of E is equal to the effective packing dimension of E relative to A? Surprisingly, it turns out that there is not always even a hyperarithmetic oracle. I will also discuss to what extent this affects potential applications of effective packing dimension.

Add to calendar :

Date/Time : 13 Nov 2024 17:00
Venue : S17 #04-04 (SR3)
Speaker : Dilip Raghavan, National University of Singapore

I will present some recent consistency results on nowhere dense ultrafilters and a weakening of selectivity.

Add to calendar :

Date/Time : 06 Nov 2024 17:00
Venue : S17 #04-04 (SR3)
Speaker : Michael Takaaki Leong,

A weakening of a Suslin tree, known as a Suslin lattice, was introduced by Dilworth, Odell, and Sari in 2007, and subsequently investigated by Raghavan and Yorioka in 2012. In this talk, we will show that the compatibility of a Suslin lattice with Martin’s Axiom and its variants mirrors that of a Suslin tree by showing that a fragment of Martin’s Axiom suffices to imply the non-existence of a Suslin lattice. We will also discuss the possible consistency of a Suslin lattice with the P-ideal Dichotomy.

Add to calendar :

Date/Time : 30 Oct 2024 16:45
Venue : S17 #04-06 (SR1)
Speaker : Desmond Lau,

We develop a forcing framework based on the idea of amalgamating language fragments into a theory with a canonical term model. We then demonstrate the usefulness of this framework by applying it to variants of the extended Namba problem, as well as to the analysis of models of certain theories with constraints in interpretation (TCIs). Separately, we look at small extensions of V as generalised degrees of computability over V. Using TCIs, we formalise and investigate the complexity of certain methods one can use to define, in V, subclasses of degrees over V. Finally, we give a characterisation of the complexity of forcing.

Add to calendar :

Date/Time : 23 Oct 2024 17:00
Venue : S17 #04-04 (SR3)
Speaker : Ellen Hammatt, Victoria University of Wellington

In this talk we investigate what happens when we take concepts from computable structure theory and forbid the use of unbounded search. In other words, we discuss the primitive recursive content of structure theory. The central definition is that of punctual structures, introduced by Kalimullin, Melnikov and Ng in 2017. We investigate various concepts from computable structure theory in the primitive recursive case. A common theme is that new techniques are required in the primitive recursive case. In particular we will focus on topics such as finite punctual dimension, punctual 1-decidability and the punctual degrees. Where the punctual degrees is a degree structure within punctual presentations of a fixed structure which is induced by primitive recursive isomorphisms. I will present various results from my PhD thesis as well as pose some open questions in the area.

Add to calendar :