Révision

en 1937 Alonzo Church et Alan Turing ont démontré que certains problèmes ne pouvaient pas être résolus avec un algorithme
s’il n’existe pas d’algorithme capable de résoudre un problème et que la réponse attendue à ce problème est “oui” ou “non”, on dira que ce problème est indécidable. Quand ce genre de problème peut être résolu à l’aide d’un algorithme, on dit que ce problème est décidable.
s’il n’existe pas d’algorithme capable de résoudre un problème et que la réponse attendue à ce problème est une valeur (issue d’un calcul), on dira que ce problème est non-calculable. Quand ce genre de problème peut être résolu à l’aide d’un algorithme, on dit que ce problème est calculable
si un problème est indécidable (ou non-calculable) cela ne veut pas dire que l’on n’est pas capable de résoudre ce problème, cela veut juste dire qu’il n’existe pas d’algorithme capable de résoudre ce problème.
le problème dit de l’arrêt est indécidable

vous devez être capable de montrer que le problème dit de l’arrêt est indécidable