Complexit et Dcidabilit

Cet ouvrage prsente les bases de la thorie de la complexit des algorithmes et en derive les thormes fondamentaux de dcidabilit et d'indcidabilit pour la logique et l'arithmtique, dont le premier thorme d'incompltude de Gdel. En faisant reposer toutes les preuves sur le codage de l'arrt d'une machine de Turing, on a soulign l'homognit et l'unit profonde des rsultats presents. L'approche par les machines de Turing est trs accessible grce la familiarit donne aujourd'hui par l'informatique. Le livre n'est pas une encyclopdie exhaustive, mais parvient de faon rapide dmontrer un choix de rsultats rprsentatifs de l'ensemble de la thorie.