Turing et ses machines II (Le Problème d’Arrêt et l’Incalculabilité du Castor Affairé )

Je vais vous présenter la notion de l’incalculabilité à travers le problème d’arrêt et le castor affairé. Le problème d’arrêt, un problème de décision fondamental en informatique théorique, questionne la possibilité de déterminer à l’avance si un programme donné s’arrêtera ou continuera indéfiniment. Nous discuterons de la preuve d’Alan Turing selon laquelle il n’existe pas d’algorithme général pour résoudre ce problème.

Le castor affairé, une illustration ludique mais profonde de l’incalculabilité. Le “castor affairé” est une machine de Turing qui, bien que simple, produit un comportement incroyablement complexe. Nous expliquerons pourquoi il est impossible de prédire le nombre maximal de pas qu’une telle machine peut effectuer avant de s’arrêter.