Théorie de calcul : problèmes de comptage et de décision

Cette séance de cours couvre la théorie du calcul, en se concentrant sur le comptage des ensembles infinis et les problèmes de décision. Il examine le concept de la comptabilité, montrant comment compter des ensembles infinis comme des entiers positifs et des paires d'entiers positifs. La séance de cours explore également la notion de décidabilité, en distinguant les problèmes décidables et les problèmes indécis. Il présente des exemples de problèmes décidables, comme la vérification si un nombre est un multiple d'un autre, et introduit le problème d'arrêt indécis. À travers des démonstrations d'auto-référence et de paradoxes, la séance de cours illustre les limites du calcul dans la résolution de certains problèmes. Il conclut en soulignant l'importance de reconnaître les problèmes indécis et le pouvoir de l'auto-référence dans la théorie computationnelle.