Calculabilité
Lang 14
Résumé du cours
À retenir
Une fonction est calculable, ou un problème est décidable s’il existe un programme qui renvoie le résultat attendu pour toutes les instances du problème (toute entrée de la fonction).
À retenir
La thèse de Church-Turing postule l’équivalence des fonctions λ-calculables de Church et des machines de Turing.
Certains problèmes sont indécidables: il n’existe pas d’algorithme qui permette de déterminer s’ils terminent pour toutes les entrées. Le problème de l’arrêt est un exemple de problème indécidable.
Crédits
Les illustrations et les exemples du problème de l’arrêt sont issus du cours de Gilles Lassus