Pierre Valarcher (LIFAR, Université de Rouen)

Dans ce travail on s’intéresse aux questions suivantes:

  • Soient F un ensemble de fonctions (calculables) et P1 et P2 des langages de programmation qui permettent d’écrire des programmes calculant uniquement les fonctions de F. Y a t’il des programmes meilleurs (au sens de la complexité en temps par exemple) dans P1 que dans P2 ?
  • Soient A une ensemble d’algorithmes, existe-t-il un langage de programmation P qui les implémente tous ?
  • Nous essaierons de répondre à ces questions dans le cas simple de la récursion primitive en rappelant les résultats de Colson sur les systèmes fonctionnels et en énonçant les résultats récents sur des langages impératifs.