L’objectif de cette activité est de faire démontrer par des élèves à partir de la troisième qu’il existe des problèmes informatiques qui sont indécidables, c’est-à-dire pour lesquels il n’existe pas d’algorithme pour les résoudre. Pour montrer qu’il existe de tels problèmes, l’activité en exhibe un, le problème de l’arrêt : étant donnée une paire constituée de l’encodage d’une machine de Turing M et d’un paramètre d’entrée w, l’exécution de M sur w s’arrête-t-elle ? L’activité suit la preuve proposée par Turing, mettant ainsi en avant le principe du raisonnement par l’absurde et la notion de disjonction des cas. Tout au long de l’activité, les élèves se servent d’une version papier d’un modèle simplifié d’ordinateur pour exécuter à la main des programmes (écrits en Scratch). Ceci permet d’abord de leur faire découvrir des programmes Scratch simples, mais aussi de se familiariser avec un modèle de calcul proche de celui d’une machine à registre. Certains de ces programmes simples sont ensuite composés ensemble pour obtenir le résultat d’indécidabilité.

Voir aussi la vidéo dont nous nous sommes inspirés :

Documents

• Description de l’activité :
• Matériel à imprimer :
• Fichiers sources LaTeX :