L’objectif de cet article consiste à esquisser le rôle des machines de Turing en théorie de la complexité (des algorithmes et des problèmes), dans le domaine de l’optimisation combinatoire. Après avoir rapidement rappelé le contexte historique dans lequel sont nées et ont évolué les machines de Turing, l’auteur détaille le fonctionnement de celles-ci en distinguant entre machines de Turing déterministes et machines de Turing non déterministes. Il montre ensuite comment les utiliser pour définir la complexité (en temps de calcul) des algorithmes. Enfin, il décrit grâce à elles plusieurs classes fondamentales en théorie de la complexité : la classe P, la classe NP, la classe des problèmes NP-complets et la classe co-NP.