Lire un programme ou l’exécuter : quelle différence ?

11 janvier 2016

Mathieu Hoyrup (LORIA)

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é.