Théorie du calcul : la décision, l'arrêt du problème

Cette séance de cours explore les concepts de calculabilité, de décidabilité et de problème d'arrêt. Il explore les questions auxquelles la théorie computationnelle cherche à répondre, telles que ce qui peut être résolu avec un algorithme et la nature des problèmes de décision. La séance de cours traite de la dénombrabilité des paires d'entiers positifs, de l'énumération des programmes et de l'uncountability des fonctions. Il explique également la distinction entre les problèmes décidables et indécidables, en utilisant des exemples pour illustrer ces concepts. La démonstration de l'auto-référence comme un outil pour mettre en valeur l'indécidabilité du problème de l'arrêt est un point culminant de la séance de cours.