Indécidabilité / Indécidable

Une propriété mathématique est dite indécidable s'il n'existe aucun algorithme permettant de la résoudre en toute généralité. Des cas particuliers peuvent être résolus, mais pas tous.
Suivant cette définition, « déterminer si l'exécution d'un programme, lancée sur une donnée particulière, se termine » est un problème indécidable. Remarquons que lancer l'exécution ne répond pas à la question, car on ne sait pas faire la différence entre une exécution qui ne se termine pas et une exécution qui dure excessivement longtemps.
L'indécidabilité n'est pas le simple constat que personne n'a trouvé d'algorithme pour résoudre tel ou tel problème, il s'agit d'une propriété qui est prouvée formellement.