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 - 241.8 ko
Description de l’activité
PDF - 99.2 ko
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