Focusing on braid groups and their algorithmic aspects, this introductory book minimizes prerequisites and includes detailed appendices for advanced concepts. It features a variety of exercises designed to reinforce learning, with solutions provided for self-assessment. This approach makes it accessible for students while encouraging deeper engagement with the material.
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, algebraic combinatorics, quantum groups and the Yang-Baxter equation, etc. LD-systems have also been considered for several decades: early examples are mentioned in the beginning of the 20th century, and the first general results can be traced back to Belousov in the 1960s. The existence of a connection between braids and left self-distributivity has been observed and used in low dimensional topology for more than twenty years, in particular in work by Joyce, Brieskorn, Kauffman and their students. Brieskorn mentions that the connection is already implicit in (Hurwitz 1891). The results we shall concentrate on here rely on a new approach developed in the late 1980s and originating from set theory.
Cet ouvrage explore la théorie de la complexité des algorithmes et établit les théorèmes de décidabilité et d'indécidabilité, incluant le premier théorème d'incomplétude de Gödel. Grâce à l'approche des machines de Turing, il offre une démonstration rapide et accessible des résultats clés de la théorie.