Complexit et Dcidabilit [Paperback]

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.DE