Théorie de la calculabilité

Théorie de la calculabilité ? claire, concise et pratique. Ce livre introduit pas à pas les langages formels et la calculabilité : des automates finis aux automates à pile, jusqu'à la machine de Turing. Il présente les modèles, les techniques de preuve et les limites du calculable. Avec de nombreux exemples, schémas, démonstrations et exercices corrigés, il s'adresse aux étudiantes, enseignants et autodidactes. Les résultats essentiels (lemme de pompage, Myhill?Nerode, Kleene, diagonalisation, Rice) sont exposés de façon accessible. Idéal pour cours ou auto-apprentissage, il offre des bases solides pour aller vers la théorie de la complexité.