Calculabilité, décidabilité et mise au point

La calculabilité étudie les limites théoriques de ce qu'un ordinateur peut résoudre. Un problème est décidable s'il existe un algorithme qui termine toujours et donne la bonne réponse (oui ou non). Par exemple, tester si un nombre est premier est décidable. Le problème de l'arrêt est le plus célèbre problème indécidable : il n'existe pas d'algorithme capable de déterminer, pour tout programme et toute entrée, si le programme terminera ou bouclera indéfiniment. Alan Turing l'a démontré en 1936 par un raisonnement par l'absurde. La mise au point (debugging) repose sur les assertions (assert condition), les tests unitaires, les préconditions et postconditions. Par exemple, assert n >= 0 vérifie une précondition. Le jeu de tests doit couvrir les cas normaux, les cas limites (0, liste vide) et les cas d'erreur.