Cet ouvrage présente les bases de la théorie de la complexité des algorithmes et en derive les
théorèmes fondamentaux de décidabilité et d'indécidabilité pour la logique et l'arithmétique
dont le premier théorème d'incomplétude de Gödel. En faisant reposer toutes les preuves sur le
codage de l'arrêt d'une machine de Turing on a souligné l'homogénéité et l'unité profonde des
résultats presentés. L'approche par les machines de Turing est très accessible grâce à la
familiarité donnée aujourd'hui par l'informatique. Le livre n'est pas une encyclopédie
exhaustive mais parvient de façon rapide à démontrer un choix de résultats réprésentatifs de
l'ensemble de la théorie.
