Le problème de l'arrêt et l'indécidabilité

Le problème de l'arrêt, qui consiste à déterminer si un programme donné s'arrête pour une entrée donnée, est l'exemple canonique d'un problème algorithmiquement indécidable, et les réductions à partir de celui-ci démontrent l'indécidabilité de nombreux autres problèmes.

Definition

Un problème de décision est indécidable si aucune machine de Turing ne peut le résoudre correctement pour toutes les entrées ; le problème de l'arrêt demande si une machine arbitraire s'arrête pour une entrée arbitraire, et il constitue le problème indécidable prototypique à partir duquel d'autres sont démontrés indécidables par réduction.

Scope

Ce sujet aborde l'énoncé précis du problème de l'arrêt, sa preuve d'indécidabilité par diagonalisation, la technique de réduction de plusieurs à un (many-one reduction) pour transférer l'indécidabilité, le théorème de Rice sur les propriétés non triviales des programmes, et des problèmes indécidables classiques tels que l'Entscheidungsproblem et le problème du mot pour les groupes.

Core questions

• Pourquoi n'existe-t-il pas d'algorithme qui décide si les programmes s'arrêtent ?
• Comment les réductions sont-elles utilisées pour prouver l'indécidabilité d'un problème à partir d'un autre ?
• Que dit le théorème de Rice sur la décision des propriétés des programmes ?
• Quels problèmes mathématiques célèbres se sont avérés indécidables ?

Key theories

Insolvabilité du problème de l'arrêt

Un argument diagonal montre que supposer l'existence d'un décideur d'arrêt conduit à une contradiction, de sorte qu'aucun algorithme ne peut décider de l'arrêt pour tous les programmes et toutes les entrées.

Réduction et transfert d'indécidabilité

Si un problème indécidable connu se réduit à un problème cible, le problème cible est également indécidable, faisant de la réduction l'outil standard pour établir l'indécidabilité.

Théorème de Rice

Toute propriété non triviale de la fonction calculée par un programme est indécidable, de sorte qu'essentiellement aucune propriété comportementale intéressante des programmes ne peut être décidée algorithmiquement.

Clinical relevance

Les résultats d'indécidabilité établissent des limites strictes au raisonnement automatisé et à l'analyse de programmes : ils démontrent que des outils généraux parfaits pour vérifier la terminaison ou les propriétés des programmes ne peuvent exister, et ils expliquent pourquoi de nombreux problèmes en logique, en algèbre et en théorie des nombres n'ont pas de solution algorithmique.

History

Turing et Church ont démontré en 1936 que l'Entscheidungsproblem, la question d'un algorithme décidant de la validité du premier ordre, est insoluble, le problème de l'arrêt étant au cœur de l'argument de Turing. Rice a généralisé ce phénomène en 1953, et l'indécidabilité a ensuite été établie pour des problèmes concrets tels que le problème du mot pour les groupes par Novikov et le dixième problème de Hilbert par Matiyasevich.

Key figures

• Alan Turing
• Alonzo Church
• Henry Gordon Rice
• Pyotr Novikov

Seminal works

• sipser2013
• turing1936
• rogers1987

Frequently asked questions

Pourquoi un ordinateur plus rapide ne peut-il pas résoudre le problème de l'arrêt ?

L'indécidabilité est indépendante de la vitesse ou de la mémoire : l'argument diagonal exclut tout algorithme, quel que soit le temps qui lui est alloué. Le problème de l'arrêt est insoluble en principe, et non pas seulement impraticable.

Pouvons-nous jamais savoir si un programme s'arrête ?

Souvent oui pour des programmes particuliers, par analyse ou en les exécutant. Ce qui est impossible, c'est un algorithme unique qui répond correctement à la question pour chaque programme et chaque entrée. Les vérificateurs de terminaison pratiques ne réussissent donc que sur des classes restreintes ou peuvent ne pas donner de réponse.