List of Talks

Amaury Pouly: Computational Complexity of the GPAC [slides]

 In 1941, Claude Shannon introduced a model for the Differential Analyzer, called the General Purpose Analog Computer (GPAC). Originally it was presented as a model based on circuits, where several units performing basic operations (e.g.~sums, integration) are interconnected. However, Shannon itself realized that functions computed by a GPAC are nothing more than solutions of a special class of differential equations of the form y'=p(y) where p is a (vector of) polynomial. Analog computer have since been replace by digital counterpart. Nevertheless, once can wonder whether the GPAC could in theory have super-Turing computable power.

A few years ago, it was shown that Turing-based paradigm and the GPAC have the same computational power. So, switching to analog computers would not enable us to solve the Halting problem, or any uncomputable exotic thing, but we can nonetheless compute everything a Turing machine does (given enough resources), and a return to analog technology would at least not mean a loss of computational power. However, this result did not shed any light on what happens at a computational complexity level: can an analog computer (GPAC) solve a problem faster (modulo polynomial reductions) than a digital computer (Turing machine)?

I will provide some elements which show that some reasonable restrictions of the GPAC are actually equivalent to P (polynomial time) and going even further, that we can show an equivalence with the polynomial of computable analysis. This gives an elegant, analog definition for polynomial time computable functions over real numbers.

Chris Porter: The invariant degrees, randomness, and semi-measures [slides]

In computability theory, there are a number of degree structures for comparing the computational strength of a sequence or collection of sequences with respect to deterministic computation, such as the Turing degrees, the Medvedev degrees, and the Muchnik degrees. What if we considered instead the computational strength of a sequence or collection of sequences with respect to probabilistic computation?

The goal of this talk is to introduce one such degree structure, namely the invariant degrees, which were introduced by Levin and V'yugin. Roughly, an invariant degree is an equivalence class of Turing invariant collections of sequences, where two Turing invariant collections of sequences A and B are equivalent if any probabilistic algorithm that produces a member of A with positive probability p produces a member of B with probability greater than or equal to p, and vice versa.

In addition to introducing the invariant degrees, I will (1) explain the connection between the invariant degrees and algorithmic randomness, (2) discuss a technique developed by V'yugin for constructing semi-measures, which in turn can be used to define invariant degrees, and (3) highlight a new application of V'yugin's technique obtained in joint work with Rupert Hölzl. 

Olivier Finkel: The determinacy of infinite games specified by automata [slides]

We prove that the determinacy of Gale-Stewart games whose winning sets are accepted by real-time 1-counter Büchi automata (or by 2-tape Büchi automata) is equivalent to the determinacy of (effective) analytic Gale-Stewart games which is known to be a large cardinal assumption. Using some results of set theory we prove that one can effectively construct a 1-counter Büchi automaton (respectively, a  2-tape Büchi automaton)    A such that: (1) There exists a model of ZFC in which Player 1 has a winning strategy in the Gale-Stewart game G(L(A)); but the winning strategies cannot be recursive and not even hyperarithmetical. (2) There exists a model of ZFC in which the Gale-Stewart game is not determined.

Luca San Mauro: Classifying c.e. graphs

Ludovic Patey: On universal instances of principles in reverse mathematics [slides]

Alex Borello: Turing degrees of limit sets of cellular automata

Cellular automata are discrete dynamical systems and a model of computation. The limit set of a cellular automaton consists of the configurations having an infinite sequence of preimages. It is well known that these always contain a computable point and that any non-trivial property on them is undecidable. We go one step further by giving a full characterisation of the sets of Turing degrees of cellular automata: they are the same as the sets of Turing degrees of effectively closed sets containing a computable point.

Simon Martiel: Generalized Cayley Graphs and Causal Graph Dynamics

Cellular Automata can be characterized as the translation-invariant continuous functions, where continuity is with respect to a certain distance over the set of configurations. This distance, and its properties, easily extend from grids to Cayley graphs. As a consequence, Cellular Automata also extend from grids to Cayley graphs. Cayley graphs have a number of useful features: the ability to graphically represent finitely generated group elements and their equality; to name all vertices relative to a point; the fact that they have a well-defined notion of translation, and that they can be endowed with such a compact metric. But they are very regular. We propose a notion of graph associated to a language, which conserves or generalizes these features. These associated
graphs can be arbitrary, although of a bounded degree. We extend Cellular Automata to these Generalized Cayley graphs, so that they define a local dynamics over time-varying graphs.

Charles Harris: The complexity of maximal  block functions of  \eta-like computable linear orderings [slides] [paper]

An order type  is \eta-like if it has the form \sum { F(q) | q \in Q  } for some F :  Q -> N - {0},
in other words if it can be obtained from the order type \eta of Q by replacing each point by some
finite linear order type (which we call a  'maximal block').  The class of \eta-like order types has
attracted considerable interest due to the simplicity of the latter and because they crop up in various
different situations. My talk will concern the subclass C of \eta-like order types  that are 'computable',
in other words that have some computable presentation L = (N,<_L). In this context it is well known

1. that every such L has order type  \sum { F(q) | q \in Q  } with F---which we call a 'maximal block
   function'---of arithmetical complexity \Delta_3,
2. that   every \eta-like order type possessing a   
   \Pi_2 maximal block function  has a computable presentation, and
3. that  there exists a \Delta_3 function G such that \sum { G(q) | q \in Q  } is not computably presentable.

This raises the question (first mentioned in 1976) of whether C is 'precisely' the class of \eta-like computable order types possessing a \Pi_2 maximal block function. I will show how we  answer this question in the negative by constructing an \eta-like computable linear ordering L for which there is no \Pi_2 function F such that L has order type \sum { F(q) | q \in Q  }. I will also describe a quite general subclass of C  whose members have order type \sum { F(q)  |  q \in Q  } for some 0'-limitwise monotonic F---i.e. such that  F is  ``almost'' \Pi_2. I  will also  briefly show, via a specific example, the usefulness of this latter characterisation for the application of infinite injury type arguments in this context.

Andrei Romashchenko: Constraint information inequalities: geometric, combinatorial and algorithmic views [slides]

Constraint information inequalities is one of the queerest phenomena discovered in information theory in 1990-s. These inequalities — linear inequalities for Shannon’s entropy — are valid for all distributions that satisfy some simple constraints (constraints are linear equalities for entropies). In the talk we discuss the geometric interpretation of these inequalities and suggest some applications of constraint information inequalities to Kolmogorov complexity and communication complexity.

Marc Raynaud : Machine d'Alan TURING

1) Présentation d'un prototype de machine d'Alan Turing, réalisé selon sa publication de 1936 intitulée "ON COMPUTABLE NUMBERS, WITH AN APPLICATION TO THE ENTSCHEIDUNGSPROBLEM"
Ce prototype a été réalisé avec les technologies à sa disposition à cette époque, et il est totalement programmable.
2) Mise en fonctionnement de la machine avec le programme décrit par Alan Turing lui-même dans sa publication et utilisation d'autres programmes selon les souhaits des participants.
Questionnement sur les possibilités du prototype réalisé et des ses applications... selon le temps disponible.