Théorie de la calculabilité

3- Théorie de la calculabilité (3 ECTS)   K4041515

Dans ce cours on se propose d’étudier, d’un point de vue formel, des notions comme celles de calcul et d’algorithme. Plus précisément, il s’agira de fournir une analyse logico-mathématique de notions qui concernent l’exécution d’une action de manière purement mécanique, c’est-à-dire sans faire appel à des formes d’intuition ou d’ingéniosité quelconques. Les instruments privilégiés pour poursuivre cette étude seront les fonctions récursives, suivant la tradition de K. Gödel et S.C. Kleene. Après avoir défini la classe de ces fonctions, on démontrera des théorèmes qui les concernent. D’une part, on établira des résultats positifs, comme la possibilité de ramener chacune de ces fonctions à une certaine forme normale, en donnant ainsi la possibilité d’avoir un modèle abstrait et universel de représentation des processus mécaniques de calcul. De l’autre, on établira des résultats négatifs – ou mieux limitatifs –, comme l’impossibilité de décider à l’avance si chaque processus mécanique s’arrêtera ou pas.

Bibliographie : 

• Polycopié distribué en cours, couvrant l’ensemble du programme et contenant une sélection d’exercices.
• Boolos, G., Burgess, J. & Jeffrey, R. (2007). Computability and Logic (5ème édition). Cambridge: Cambridge University Press.
• van Dalen, D. (2001). Algorithms and decision problems: A crash course in recursion theory. Dans D.M. Gabbay et F. Guenthner (dir.), Handbook of Philosophical Logic (2ème édition), Vol. 1, p. 245-311. Dordrecht: Kluwer. 
• van Dalen, D. (2004). Logic and Structure (5ème édition). Berlin: Springer (chap. 8).
• Epstein, R.L. & Carnielli, W.A. (2008). Computability: Computable functions, logic and the foundations of mathematics (3ème édition). Socorro (New Mexico): Advanced Reasoning Forum.
• Odifreddi, P. & Cooper, B. (2012). “Recursive functions”. Dans E.N. Zalta (dir.), The Stanford Encyclopedia of Philosophy, <http://plato.stanford.edu/entries/recursive-functions/>.
• Odifreddi, P. (1989). Classical Recursion Theory. Amsterdam: Elsevier.
• Rogers, H. (1987). Theory of Recursive Functions and Effective Computability. Cambridge (Mass.): MIT Press.

       Terwijn, S. (2008). Éléments de théorie de la calculabilité, trad. fr. M. Cadilhac, manuscrit, <http://www.math.ru.nl/~terwijn/publications/syllabus_fr.pdf>.