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.