damnvoid (./12258) :
et si tu enseignes l'algorithme de la division euclidienne sans prouver qu'il s'arrete, ben... c'est juste absurde
C'est pourtant bien ce qu'on fait lorsque l'on enseigne la division euclidienne (i.e l'algo "à la main", mais c'est strictement le même ) en classe de primaire. Et la preuve est tellement triviale ( genre: le truc divisé décroit strictement à chaque étape et c'est fini dès qu'il est < diviseur ) que des gamins de 8 ans le pressentent bien.
Même situation qu'en maths ou en physique
On peut objecter des remarques du type "la vraie matière [sous-entendu: informatique théorique] est trop compliquée pour être enseignée au lycée" mais c'est par exemple également vrai pour la physique où par faute d'outils mathématiques on ne fait presque rien jusqu'en terminale.
Comme Hippo le sous-entend, c'est également vrai en maths. ( et c'est pour cela qu'on ne fait pas vraiment des maths - définitions précises, axiomes, démonstrations, et non juste appliquer un résultat )
Bref en approche "puriste", on ne peut rien enseigner rigoureusement tant que les élèves n'ont pas déjà un certain niveau... hors il faut bien bootstrapper. C'est en version "humaine" le même problème que celui du fondement des mathématiques....
Il me semble tout de même que dès la seconde on peut initier à la programmation avec un peu d'algo "théorique" et de complexité. Mais l'arrêt et la décidabilité ça me semble douteux...