• Votre sélection est vide.

    Enregistrez les diplômes, parcours ou enseignements de votre choix.

Théorie de la calculabilité

  • Composante

    UFR de philosophie (UFR10)

  • Volume horaire

    26h

  • Période de l'année

    Automne

Description

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

Alberto Naibo 

    Mardi 8h-10h    

  Salle E628 /Sorbonne

 

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

Lire plus