Abstract FR:

On etudie la programmabilite de l'algorithme naturel calculant le minimum de deux entiers par leur decrementation alternative dans divers systemes fonctionnels : la recursion primitive usuelle, la recursion primitive avec parametres fonctionnels (egalement appelee systeme t de godel), le lambda-calcul polymorphe du second ordre et la recursion primitive sur les listes. Le resultat principal montre que cet algorithme n'est pas programmable avec la complexite attendue dans le langage de la recursion primitive, alors qu'il l'est dans le systeme t. La methode de preuve est basee sur la semantique denotationelle et sur la notion d'index de sequentialite.