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

The aim of this book is to present recently discovered connections between Artin's braid groups En and left self-distributive systems (also called LD- systems), which are sets equipped with a binary operation satisfying the left self-distributivity identity x(yz) = (xy)(xz). (LD) Such connections appeared in set theory in the 1980s and led to the discovery in 1991 of a left invariant linear order on the braid groups. Braids and self-distributivity have been studied for a long time. Braid groups were introduced in the 1930s by E. Artin, and they have played an increas- ing role in mathematics in view of their connection with many fields, such as knot theory, alge ..

The aim of this book is to present recently discovered connections between Artin's braid groups En and left self-distributive systems (also called LD- systems), which are sets equipped with a binary operation satisfying the left self-distributivity identity x(yz) = (xy)(xz). (LD) Such connections appeared in set theory in the 1980s and led to the discovery in 1991 of a left invariant linear order on the braid groups. Braids and self-distributivity have been studied for a long time. Braid groups were introduced in the 1930s by E. Artin, and they have played an increas- ing role in mathematics in view of their connection with many fields, such as knot theory, alge ..