Cours sur les modèles de calcul

Modèles de CalculYassine LakhnechYassine.Lakhnech@imag.fr2007/08Université Joseph FourierLab.: VERIMAGModèles de Calcul Start – p.1/81Équipe pédagogique•Cours : Saddek Bensalem et Yassine Lakhnech•Travux dirigés : Ph. Bidinger et Ph. Bizardweb: www-verimag.imag.fr/~lakhnech/MCALModèles de Calcul Start – p.2/81Bibliographie•J. Hopcroft, R. Motwani, J. Ullman, Introduction to AutomataTheory, Languages and Computation, 2nd edition,Addison-Wesley, 2001•P. Wolper. Introduction à la calculabilité - 2ième édition,Dunod, 2001.•Cl.Benzaken, Systèmes Formels, Masson, 1991.•Transparents d’INF232http://www-verimag.imag.fr/~lakhnechModèles de Calcul Start – p.3/81MotivationComprendre les limites de l’informatique.•Que veut dire qu’une fonction soit calculable ou qu’unproblème soit soluble par des algorithmes.•Existe-il des problèmes insolubles par des algorithmes.•Peut-on avoir des réponses à ces questionsindépendantes :◦du langage de programmation◦de l’ordinateur sur lequel les programmes sont exécutésModèles de Calcul Start – p.4/81Plusieurs modèles de calcul•Mémoire finie : Automates d’états finis, expressionsrègulière.•Mémoire finie + pile : Automates à pile•Mémoire infinie :◦Machines de Turing (Alan Turing)◦Systèmes de Post (Emil Post)◦Fonctions-récursives (Kurt Gödel, Jacques Herbrand)◦λ-Calcul (Alonzo Church, Stephen C. Kleene)◦Logique des combinateurs (Moses Schönfinkel, HaskellB. Curry)Modèles de Calcul Start – p.5 ...