Attention : activité en travaux

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 no- tion 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 familia- riser 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é.