Institut de Recherche sur l'Enseignement des Mathématiques de Paris

Serge GRIGORIEFF IRIF, Universite Paris 7 - Denis Diderot (Mercredi 18 janvier 2017 -14 heures) « Compléments sur l'émergence des modèles du concept de calculabilité » Cet exposé complète l'exposé fait par l'auteur sur le même thème en mars 2015. Seront traités : - Le raffinement des modèles de calcul (de Turing à Kolmogorov et Schonhage) comme approche d'une modélisation de la notion d'algorithme (et pas seulement de celle de fonction calculable), laquelle aboutit à la solution donnée par Yuri Gurevich avec les « Evolving Algebras » (aussi appelées “Abstract State Machines“) - Le théorème de raccourcissement des preuves de Gödel comme précurseur du théorème d'accélération des algorithmes - Fonctions calculables “prouvablement totales“ dans une théorie - L'idée de Kolmogorov d'une “sémantique des preuves'“ et l'isomorphisme de Curry-Howard.