Théorie de la calculabilité et problème d'arrêt

Cette séance de cours présente la théorie de la calculabilité, en se concentrant sur les problèmes de décision qui nécessitent une réponse «oui» ou «non» pour chaque valeur. L'instructeur explique le problème d'arrêt, qui se demande si un algorithme se terminera dans un temps fini. La démonstration de Turing en 1936 montre qu'un algorithme prédisant cela n'existe pas.