Théorie de calcul : problèmes indécis

Cette séance de cours explore le concept selon lequel il y a plus de fonctions booléennes que d'algorithmes, conduisant à l'existence de fonctions qui ne peuvent pas être calculées. Par exemple, les paradoxes d'Epidenides et de Berry illustrent le problème d'arrêt. La séance de cours se penche sur l'incomputabilité de la complexité de Kolmogorov, démontrant l'impossibilité de déterminer l'algorithme le plus court pour une sortie donnée. Il touche également au Théorème de Rice et à l'indécidabilité de divers problèmes informatiques, mettant l'accent sur la futilité de rechercher des solutions à des problèmes indécis. Malgré les défis posés par les problèmes indécis, la séance de cours souligne que les algorithmes peuvent encore résoudre des cas concrets de tels problèmes.