Problème D'arrêt

Le problème d’arrêt est un problème important dans la théorie de la calculabilité en logique et en mathématiques. Elle a été proposée par le mathématicien britannique Alan Turing en 1936. L'article pertinent est le célèbre article de Turing «Sur les nombres calculables, avec une application au problème de la résolution", dans lequel le problème de l'arrêt et le concept de machine de Turing ont été proposés pour la première fois. L'article, publié dans les Actes de la London Mathematical Society, a jeté les bases de l'informatique moderne. Bien que l'article original de Turing n'aborde pas directement ce qui est devenu le problème de l'arrêt, ses travaux ont jeté les bases de la compréhension des limites du calcul. L'insolvabilité du problème de l'arrêt est un concept fondamental de la théorie computationnelle qui suggère que certains problèmes sont intrinsèquement insolubles par les algorithmes.

Le problème de l'arrêt traite du problème de déterminer si un programme peut terminer son exécution dans un temps limité. Autrement dit, étant donné un programme et une entrée, est-il possible de déterminer si le programme finira par s'arrêter pendant son exécution, plutôt que de toujours s'exécuter ? Turing a prouvé par son argument diagonal que le problème de l'arrêt est insoluble, c'est-à-dire qu'il n'existe pas d'algorithme universel capable de déterminer pour tous les programmes et entrées si un programme va s'arrêter de fonctionner ou boucler à l'infini. La preuve de ce problème est l’une des pierres angulaires de la théorie informatique, révélant les limites de l’informatique.