Lire un programme ou l'exécuter : quelle différence ?
Time: 14:30 -- Location: LIX
Que peut-on savoir d'une fonction si elle nous est présentée : - sous forme d'un programme calculant cette fonction, - sous forme d'une boîte noire permettant de connaître les valeurs de cette fonction sur toutes les entrées.
Disposer d'un programme donne au moins autant d'information qu'avoir accès à la boîte noire. Cela donne-t-il plus d'information ? Dans ce cas, quel type d'information ?
Cette question est un des problèmes les plus fondamentaux de l'informatique théorique et a donné lieu à de nombreux travaux, à commencer par ceux de Turing. Je présenterai les résultats historiques ainsi que les développements récents. Le domaine de recherche est la théorie de la calculabilité.