Numérique et sciences informatiques (spécialité) · Terminale · Langages et programmation

Calculabilité et décidabilité

• Une fonction est calculable s'il existe un programme qui s'arrête pour toute entrée et renvoie la bonne valeur ; un problème de décision est décidable si le prédicat associé est calculable.
• Le résultat ne dépend pas du langage choisi : tous les modèles de calcul connus ont les mêmes possibilités (thèse de Church).
• Le problème de l'arrêt est indécidable : aucun programme ne peut dire, pour tout programme et toute entrée, si l'exécution s'arrête (Turing, 1936).
• Décidable ne veut pas dire rapide : la calculabilité ne s'occupe que de l'existence d'un algorithme, la complexité étudie son coût.