Séance de cours
Cette séance de cours revisite la définition théorique de la « computation » et des algorithmes, explorant ce qui peut être résolu et efficacement résolu avec un algorithme. Il introduit les machines Turing comme automates mathématiques abstraits avec une bande infinie divisée en cellules stockant des caractères d'un alphabet fini. Les machines ont une tête de lecture/écriture qui peut modifier les caractères, se déplacer à gauche ou à droite, et un ensemble d'états internes. La séance de cours explique le fonctionnement des machines Turing à travers des exemples, détaillant la table de transition et le processus de détermination si un nombre est pair. Il couvre l'initialisation de la bande, le positionnement de la tête, les mises à jour de l'état et les conditions d'arrêt. Le contenu de la bande à la fin représente le résultat du traitement.