Théorie de calcul: Countabilité & Halting Problème

Cette séance de cours couvre les questions fondamentales de la théorie du calcul: ce qui peut être résolu avec un algorithme et ce qui peut être résolu efficacement. Il explore la comptabilité, le problème d'arrêt, les problèmes de décision et le concept de dnumérabilité. À travers des exemples, il illustre comment compter des ensembles infinis, la dnumérabilité des paires d'entiers positifs, et l'indécidabilité du problème d'arrêt en utilisant l'auto-référence. La séance de cours traite également de la comptabilité des programmes et de l'indécidabilité de certains problèmes de décision, en mettant l'accent sur les limites des solutions algorithmiques.