Indécidabilité du problème de l’arrêt

jeudi 9 janvier 2020
par  Webmestre IREM

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é.

PDF - 242.5 ko
Activité
PDF - 341.6 ko
Matériel à imprimer
Zip - 513.6 ko
Fichiers source latex pour le matériel à imprimer

Contact

IREM de Clermont-Ferrand

Directrice :
Malika More
Tél. : +33 (0)4 73 40 76 95

Directeur adjoint :
Nicolas Billerey
Tél. : +33 (0)4 73 40 71 12

Secrétariat :
Françoise Toledo
Tél. : +33 (0)4 73 40 70 98

Chargée de mission :
Aurélie Roux

Webmestre :
Benoît Coly