Abstracts

• Djamel Eddine Amir (Loria)

Separating computability notions 

Computable analysis provides ways of representing points in a topological space i.e. of defining a notion of computable points of the space. In this talk, we investigate when two topologies on the same space induce different sets of computable points. We first study a purely topological version of the problem, we obtain a characterization  leading to an effective version and we prove that two topologies satisfying this condition induce different sets of computable points. Along the way, we propose an effective version of the Baire category theorem which captures the construction technique and enables one to build points satisfying some properties for each of the two topologies. Finally, we generalize the result to three topologies and give an application to prove that certain sets do not have computable type, i.e. have a homeomorphic copy that is semicomputable but not computable.

• Laurent Bienvenu (LaBRI)

Probabilistic vs deterministic gamblers

An infinite binary sequence is called unpredictable (or computably random) if no computable strategy can successfully guess the value of its bits by betting money on them. This definition only considers deterministic strategies. Would allowing probabilistic strategies give a stronger definition? In other words, is there an infinite sequence which cannot be predicted by deterministic strategies but can be predicted, with positive probability, by a probabilistic strategy ? We will show that, surprisingly, the answer is positive.

• Manon Blanc (LIX)

A characterization of polynomial time computable functions from the integers to the reals using discrete ordinary differential equations

La classe des fonctions des entiers vers les entiers calculables en temps polynomial a récemment été caractérisée en utilisant des EDOs discrètes. De fait, le rôle essentiel des EDOs, et des outils qui s'y rapportent comme les changements de variables pour capturer les mesures de calculabilité et de complexité, ont été soulignés.

Dans cette présentation, je montrerai comment étendre cette approche pour caractériser de manière algébrique la classe des fonctions de N dans R calculables en temps polynomial (au sens de l'analyse calculable).

• Bernadette Charron-Bost (DIENS)

Cancelled

Computable functions in an anonymous multi-agent network

We characterize exactly the class of functions that can be computed in a network of identical and anonymous agents, and propose two universal algorithms that compute any function in this class.

• Guilhem Gamard (Loria)

Rice-like theorems for automata networks

An automata network (AN for short) is a finite digraph where each node holds a state, chosen among a finite set, that evolves in function of the states of its inbound neighbors. Time is discrete and all nodes evolve synchronously and in parallel, similarly to what happens in a cellular automaton. In other terms, the differences between a cellular automaton and an automata network is that the "grid" is an arbitrary finite digraph, and that different nodes may have different update functions. ANs have been used to model neural networks, dynamics of expression and inhibition of genes, distributed algorithms, and more. Although ANs look like a model of computation, they are not Turing-complete, for they lack unbounded memory. Still, they are subject to some kind of "Rice theorems", i.e., results along the lines of: "any nontrivial property of the function computed by an automata network is computationally hard to test". In this talk, we will review several results that fit this pattern, as well as pieces of proof that hopefully may be reused in other contexts. 

• Léo Gayral (IMT)

Computational Complexity of Chaotic Gibbs Measures

In 2010, Chazottes and Hochman proved that a 3D finite-range potential can induce a chaotic system of Gibbs measures, in the sense that there is no family of measures $\left(\mu_\beta\right)_{\beta\in\mathbb{R}}$ that converges as the temperature goes to 0. This result was later refined using 2D potentials by both Chazottes-Shinoda and Valle-Vedove.

This talk is a preview of a current work in progress, in which we aim at improving the latter results by having a control on the set of zero-temperature limit Gibbs measures. The main result is that any Π₂-computable set of measures, up to some affine transform, can be obtained as the set of adherence values for some finite-range potential, regardless of the chosen sequence $\left(\mu_\beta\right)_{\beta\in\mathbb{R}}$. To do so, we will in particular use the hierarchical structure of aperiodic tilings to control the frequencies of patterns.

• Riccardo Gozzi (LIX)

Analog characterization of FPSPACE and PSPACE

During this talk I am going to present an analog characterization of standard complexity classes by means of systems of polynomial ordinary differential equations, or ODEs, with a particular focus on the polynomial-space classes, FPSPACE and PSPACE. I will introduce the concept of analog computation in relation with the GPAC model, which stands for Generable Purpose Analog Computation model. I will then describe the different approaches taken in litterature to modify the model in order to simplify its formulation and improve its computational power. Following this guideline, I will then explain how these modifications led to an equivalence between this model and the setting of computable analysis, meaning that every function that can be computed within the computable analysis framework can also be computed by the GPAC model, and viceversa. This particular equivalence can be also extended to the case of the standard complexity calss P, once Turing machine computations are successfully simulated by continuous solutions of polynomial ODEs. I will show that the same treatment can be reserved to characterize the classes FPSPACE and PSPACE as well, as long as some care is taken while choosing the right encoding for Turing machine configurations. A more detailed description of the classes of dynamical systems that are capable of achieving this goal will be given, explaining some technical details of the construction involved.

• Benjamin Hellouin (LRI)

Le problème du domino apériodique en (presque) toute dimension

Le problème du domino consiste à prendre un jeu de couleurs et à chercher un pavage, i.e. une coloration de la grille $Z^2$, qui évite un ensemble de motifs interdits donnés en entrée. Ce problème est indécidable ($Sigma_0^1$-complet) en dimension 2 et plus, une conséquence de l'existence d'ensemble de motifs interdits qui ne permettent de paver le plan que de manière apériodique. De manière générale, les considérations d'(a)périodicité ont façonné en profondeur ce domaine de recherche. On peut naturellement demander si chercher spécifiquement des pavages (a)périodiques est plus ou moins difficile que le problème de base. Le cas périodique n'apporte rien de plus, mais le cas apériodique est significativement plus difficile que le domino et peut échapper à la hiérarchie arithmétique. Encore plus surprenant, cette séparation ne commence qu'à partir de la dimension 3 ou 4. Je ferai un panorama de deux résultats: en dimension 2, le domino apériodique est co-récursivement énumérable-complet ; en dimension > 3, il est hors de la hiérarchie arithmétique. Le cas de la dimension 3 reste ouvert. Je mentionnerai quelques résultats similaires sur le domino apériodique dans les espaces de pavages plus généraux. Résultats en collaboration avec Antonin Callard, Anaël Grandjean et Pascal Vanier.

• Alonso Herrera Nunez (Université Paul Sabatier)

Embedding universal Turing machines in the dynamics of smooth maps

The Church-Turing thesis states that any reasonably flexible and broad model of computation can do what a Turing machine can, and no more, providing a robust definition of computation. Among the several existing models of computation, we restrict ourselves to Turing machines, as they provide a suitable framework to investigate the connections between computation and dynamical systems. In the context of symbolic dynamics, cellular automata appear as natural models for universal computation, with examples piling up left and right, notably Conway's Game of Life and Wolfram's Rule 110 are Turing universal. In a non-discrete system, as the ones usually used to model real phenomena, computation is a far more delicate topic. Several formalities need to be addressed to deal with computational questions. Moore's generalized shifts, are Turing machines viewed as dynamical systems, their dynamics are ruled by functions defined to mimic the transitions of the machine. They embed naturally in continuous spaces by identifying their underlying symbolic space with a two dimensional Cantor set. Their dynamics, ruled by piece-wise linear maps, follow each transition of the machine with each iteration. As shown by Moore the linear maps can be smoothly extended to a map on R^2, or a flow on R^3. This and other constructions, however, are quite delicate. In particular, an arbitrary small perturbation would break them. On the other hand, there seems to be some flexibility in many of the choices involved in the construction, and it is not clear how prevalent universality is within different classes of systems. The purpose of our present work is to investigate this problem. In this exposition we briefly survey Moore's generalized shift construction and present a result that can be seen as a lower bound on the abundance of universal maps within the restrictive class of diffeomorphisms of the disk. More precisely, we show Theorem 1 The set of all Turing universal diffeomorphisms of the disk to itself is an uncountable dense set in the space of all disk diffeomorphisms. This result shows that diffeomorphisms that exhibit pathological behaviours are everywhere in their spaces, as 'programming' the machine allows to force the system, or a part of it, to behave in a pathological way. An example of this `programming' technique is given, where we show that there exist diffeomorphisms of the disk that present non-statistical behaviour. Roughly speaking, a map is non-statistical if it is not possible to describe its limiting behaviour in statistical terms, for a large collection of points in the ambient space. Combining this with Theorem 1, we obtain Theorem 2 The set of non-statistical diffeomorphisms of the disk is an uncountable and dense set in the space of disk diffeomorphisms.

• Bastien Laboureix (Loria)

Les claviers, un nouveau modèle de calcul

Imaginez que vous êtes en train de travailler tranquillement sur votre ordinateur, en sirotant un bon café quand, tout à coup, vous renversez votre tasse sur votre clavier. Après séchage, votre clavier refonctionne mais de manière bizarre. Les touches sur lesquelles vous appuyez ne produisent pas l'effet escompté : vous appuyez sur "g", le clavier écrit "gh" ; vous appuyez sur "a", le clavier efface la dernière lettre et déplace le curseur à gauche. Pouvez-vous alors écrire un mot donné avec votre clavier ? Tous les mots ? Selon les opérations autorisées (écriture de lettres, effacement, déplacement de curseur), les claviers étudiés se placent à différents étages de la hiérarchie de Chomsky et offrent diverses question de complexité ou de décidabilité. Cet exposé est une présentation des résultats de l'article original publié à MFCS 2021 : Yoan Géran, Bastien Laboureix, Corto Mascle, Valentin D. Richard: Keyboards as a New Model of Computation. MFCS 2021: 49:1-49:20.

• Dominique Larchey-Wendling (Loria)

The Coq Library of Undecidability Proofs

La librairie Coq des preuves d'indécidabilité est un effort collaboratif, en croissance constante, de mécanisation de problèmes indécidables ainsi, bien-sûr, que des preuves d'indécidabilité associées. Elle est fondée sur la notion de réduction synthétique. Autrement dit, elle exploite la notion interne de calculabité des réductions écrites dans la logique constructive du système Coq (excluant l'utilisation d'axiomes). Cette approche rend abordable la vérification de nombreuses preuves d'indécidabilité qui procèdent par réduction à un autre problème dont l'indécidabilité a déjà été établie.

Nous proposons une présentation rapide des fondements synthétiques de la librairie, puis nous visiterons le graphe des réductions déjà présentes et qui concernent des problèmes liés à des modèles de calcul bas niveau (machines de Turing, à piles, à compteurs, fonctions µ-récursives, Fractran, lambda calcul), des problèmes sur les mots (problème de correspondance de Post, réécriture de mots, unification 2ième et 3ième ordre, semi-unification), les équations Diophantiennes (10ième problème de Hilbert), et des problèmes de validité, prouvabilité, satisfiabilité logique (1ier ordre, Peano et ZF, système F, logique linéaire, satisfiabilté finie, logique de séparation).

• Emmanuel Rauzy (Université de la Sarre)

Computable analysis on the space of marked groups

I will present some results that concern the study of Markovian computable analysis on the topological space of marked groups. This work was originally motivated by problems in group theory, but it turned out to be also very interesting from the point of view of computable analysis alone, providing the first naturally arising Polish space that is not effectively Polish. In the study of type 1 computable analysis on effective metric spaces, well known theorems of Kreisel-Lacombe-Schoenfield, Ceitin and Moschovakis show that in many cases, computable functions between effective metric spaces must be continuous, and even effectively continuous. We show that none of these results can be applied to the space of marked groups, leaving open the continuity problem for the space of marked groups.