La thèse de Church : hier, aujourd’hui, demain

Vendredi 11 avril 2008
Sorbonne, amphithéâtre Descartes, Université Panthéon-Sorbonne

Tel qu’appréhendé par l’informatique théorique contemporaine, le calcul n’a plus guère de traits communs avec l’artefact qu’avaient proposé, au début du XXe siècle, les premières théories de la calculabilité (machines de Turing etc) et dans le contexte desquelles la fameuse « Thèse de Church » fut énoncée. Sous le regard contemporain, le calcul diffère de son ancêtre à la fois par ses propriétés (parallélisme, non déterminisme, concurrence), par la multiplicité de ses échelles (calcul sur les réels, fonctionnalité d’ordre supérieur, complexités intermédiaires) et par ses liens avec les sciences de la nature (calcul quantique, bio-calcul). Quel impact ces métamorphoses du calcul ont-elles sur l’horizon fermé, il y a soixante-dix ans, par la thèse de Church ? Qu’impliquent-elles quant à la question ouverte par la « version physique » de la thèse de Church : la nature calcule-t-elle ?

---

Orateurs :
Pablo ARRIGHI. Université Joseph Fourier à Grenoble, Equipe « Calculs, Algorithmes, Programmes, Preuves »

Gilles DOWEK. Professeur au Département d’informatique de l’École polytechnique; INRIA,

Jean-Louis GIAVITTO. Equipe « Informatique, Biologie Intégrative et Systèmes Complexes » (CNRS-Université d’Evry),

Jean-Baptiste JOINET. Université Paris 1, UFR de Philosophie et EXeCO (membre associé); équipe « Preuves-Programmes-Systèmes » (PPS, CNRS-Paris 7); collectif Histoire, Philosophie, Sciences (CHPS ENS)

Giuseppe LONGO. École Normale Supérieure, Laboratoire d’Informatique (LIENS); équipe Complexité et Information morphologique; collectif Histoire, Philosophie, Sciences (CHPS).

Jean MOSCONI. Professeur émérite à l’UFR de Philosophie de l’Université Paris 1; Institut d’Histoire et de Philosophie des Sciences et des Techniques.

Thierry PAUL. École Normale Supérieure, Collectif Histoire, Philosophie, Sciences (CHPS) et Département de Mathématiques et Applications (DMA).

Programmation des exposés.

9h30-10h30: Jean-Baptiste Joinet

10h30-11h30: Jean Mosconi

Pause

11h45-12h45: Gilles Dowek

Pause déjeuner

14h30-15h30: Jean-Louis Giavitto

15h30-16h30: Giuseppe Longo

Pause

16h45-17h45: Thierry Paul

17h45-18h45: Pablo Arrighi

Cocktail de clôture

Titre et résumé des exposés :

Pablo ARRIGHI, Une extension quantique du théorème de Gandy – La thèse de Church-Turing est-elle une conséquence des postulats de la physique ?

Gilles DOWEK, Le calcul non-déterministe sur les nombres réels.
Résumé: Deux chapitres de la théorie de la calculabilité concernent l’un les algorithmes non déterministes (par exemple, au sens de Cook) et l’autre les algorithmes opérant sur les nombres réels (par exemple, au sens de Lacombe et Grzegorczyk). Cet exposé tentera d’esquisser ce que pourrait être une notion d’algorithme qui serait à la fois non déterministe et opérant sur les nombres réels. Une telle notion serait un candidat naturel pour une description calculatoire de certains phénomènes physiques.

Jean-Louis GIAVITTO, Ça se calcule, c’est un calcul, parce que ça calcule.

Jean-Baptiste JOINET, La thèse de Church et les métamorphoses de la logique et du calcul

Giuseppe LONGO, Les calculs et l’arithmétique versus les enjeux du mobile et de la mesure.

Jean MOSCONI, Thèse de Church, Thèse de Turing: formulation, variantes, statut.

Thierry PAUL, Calcul et images, invariants et aléatoire

Remerciements. Ce colloque n’aurait pu être organisé sans le soutien :
de la composante « Expérience et Connaissance » (EXeCO) de l’équipe « Philosophies contemporaines » (UFR de Philosophie de Paris 1)
du « Collectif Histoire et Philosophie des Sciences » de l’École Normale Supérieure (CHPS)
du Conseil Scientifique de l’université Paris 1