Ce qu’il faut savoir

• 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

Ce qu’il faut savoir faire

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