Journées GT Calculabilités 2015

Les premières rencontres du GT Calculabilités auront lieu les 27 et 28 avril à l'IUT de Fontainebleau. Les principaux thèmes de ces rencontres sont les suivants:

Calculabilité classique (réductions, degrés, méthodes de priorité, etc.)
Autres modèles de calculs: modèles géométriques (pavages, machines à signaux), modèles algébriques (Abstract State Machines), modèles dynamiques et distribués (automates cellulaires, protocoles de population, tas de sable, etc), calcul à temps continu, calcul à temps ordinal, calcul sur les structures infinies (réels, ordres)
Applications et interactions de la calculabilité avec les domaines suivants: mathématiques constructives/calculables, cryptologie, virologie, théorie de l'information et de l'aléatoire (complexité de Kolmogorov), complexité algorithmique, théorie des modèles, théorie de la preuve et mathématiques à rebours, théorie des ensembles (modèles intérieurs, forcing, théorie descriptive, détermination), théorie des domaines

Program

The program is now available here.

Invited Tutorials

Andy Lewis-Pye

Degree spectra of $\Pi^0_1$ classes

$\Pi^0_1$ classes are a central concept in computability and the study of the degree theoretic complexity of their members, dating back as far as Kleene, has resulted in a rich and well developed theory. In this tutorial we’ll consider what forms the degree spectrum of a $\Pi^0_1$ class may take. The framework for this analysis will be provided by consideration of a natural structure: we consider the degree spectra of $\Pi^0_1$ classes, ordered by inclusion. In looking to establish basic properties of this structure, a number of phenomena come to light which are of independent interest. Along the way we’ll have the opportunity to cover some of the important proof techniques in this area.
Boban Velickovic

Introduction to forcing

The method of forcing was invented by Cohen in 1963 in order to prove the independence of the Continuum Hypothesis and the Axiom of Choice from the usual axioms ZF of set theory. This method has turned out to be extremely powerful and versatile and has been used to show a multitude of independence results in set theory. It is still a topic of active research and plays a key role in the search for new axioms of set theory. On the other hand ideas inspired by forcing have been used in other areas such as complexity theory, model theory, proof theory, etc. There also exist deep algebraic connections between forcing, Kripke semantics, and Grothendieck’s notion of a topos of sheaves. In this tutorial we will present an outline of Cohen’s construction and its main applications. If time permits, we will discuss some related results in other areas, such as complexity theory.

Talks

The talks should be in english if possible.

Comment s'inscrire ?

Envoyez un mail à gtc-2015@lacl.fr spécifiant

si vous souhaitez présenter des travaux
si vous venez les deux jours et participez au repas de conférence (lundi soir)

Un financement est possible pour des doctorants, faites-en la demande si vous en avez besoin, dans la limite de 3 doctorants.

Where is it ?

Both days will take place at IUT de Fontainebleau (How to come in english). The conference dinner will also be in Fontainebleau.
We encourage you to book a hotel in Fontaibleau and not in Paris.