Théorie de la calculabilité — claire, concise et tournée vers la pratique.
Ce livre vous guide pas à pas à travers les fondements des langages formels et de la calculabilité : des automates finis aux automates à pile et aux grammaires sans contexte, jusqu'à la puissante machine de Turing. Vous découvrirez non seulement les modèles formels, mais aussi les techniques de preuve permettant d'établir des propriétés de langages — et, surtout, de situer les limites de ce qui est calculable.

Riche en exemples, illustrations explicatives, démonstrations limpides et exercices accompagnés de corrigés, cet ouvrage s'adresse aux étudiantes et étudiants, aux enseignant·e·s et à tous ceux qui souhaitent aborder le sujet de manière structurée. Des résultats-clés tels que le lemme de pompage, Myhill–Nerode, le théorème de Kleene, la diagonalisation ou encore le théorème de Rice sont présentés de façon accessible et leurs conséquences sont discutées en détail.

Un soin particulier a été apporté à la pédagogie et à l'applicabilité : les chapitres sont modulaires, les preuves sont entièrement développées et, lorsque des détails techniques risqueraient d'obscurcir l'essentiel, l'intuition est mise en avant. De nombreux exercices favorisent l'apprentissage actif — idéal comme support de cours ou pour l'auto-apprentissage.

Que vous cherchiez des bases solides pour des cours avancés (par ex. théorie de la complexité) ou que vous souhaitiez acquérir des compétences mathématiques robustes en théorie de la calculabilité, ce livre offre une introduction fondée et lisible à l'un des domaines centraux de l'informatique théorique.