Machines de Turing: Basics

Cette séance de cours présente les machines de Turing comme de simples automates avec un nombre fini d'états et une bande pour la lecture. Contrairement aux automates finis ou aux automates pushdown, les machines de Turing ont la capacité de manipuler la bande en se déplaçant à gauche ou à droite, en lisant et en écrivant des symboles. La séance de cours couvre la fonction de transition, le concept d'états, l'alphabet de bande, et l'importance des configurations dans l'exécution d'une machine de Turing. Il aborde également le déterminisme, le non-déterminisme et la relation entre les problèmes résolubles par les machines de Turing déterministes et non déterministes.