damnvoid (./12255) :
l'arret, ca me parait autrement plus fondamental comme notion.

Oui mais bon on peut enseigner les preuves de correction et l'arrêt (donc la décidabilité...) plus tard, si tu commences un petit cours réel "algorithmie et programmation" (où l'on fait tourner les progs sur des problèmes où l'arrêt n'est pas un problème en général puisque ce sont des algos simples... ) c'est raisonnable de se limiter à la complexité au début...