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

Le problème de l'arrêt consiste à déterminer si un programme donné finit par s'arrêter pour une entrée donnée, et la preuve de Turing, selon laquelle aucun algorithme ne peut y répondre dans tous les cas, est l'exemple fondateur d'un problème indécidable.

Definition

Un problème de décision est indécidable lorsqu'aucun algorithme ne peut y répondre correctement pour chaque entrée ; le problème de l'arrêt, qui consiste à décider si un programme arbitraire s'arrête pour une entrée arbitraire, est le problème indécidable canonique, prouvé tel par un argument diagonal autoréférentiel.

Scope

Ce sujet aborde l'argument de la diagonalisation qui établit l'indécidabilité du problème de l'arrêt, la distinction entre les problèmes décidables, reconnaissables et co-reconnaissables, le théorème de Rice qui montre que toutes les propriétés sémantiques non triviales des programmes sont indécidables, et le catalogue des problèmes indécidables naturels en logique, en mathématiques et en informatique.

Core questions

• Pourquoi aucun algorithme unique ne peut-il décider si chaque programme s'arrête ?
• Quelle est la différence entre un problème décidable et un problème simplement reconnaissable ?
• Pourquoi pratiquement toutes les propriétés intéressantes du comportement des programmes sont-elles indécidables ?
• Comment l'indécidabilité se propage-t-elle du problème de l'arrêt à d'autres problèmes ?

Key theories

Indécidabilité du problème de l'arrêt

Supposer l'existence d'un algorithme qui décide de l'arrêt mène à une contradiction via un programme qui s'arrête précisément quand il est prédit qu'il ne s'arrêtera pas, donc un tel algorithme ne peut exister.

Théorème de Rice

Toute propriété non triviale de la fonction calculée par un programme — c'est-à-dire toute propriété qui est vraie pour certains programmes et fausse pour d'autres en fonction de leur comportement — est indécidable, généralisant le résultat de l'arrêt à toutes les propriétés sémantiques.

Clinical relevance

Étant donné que l'arrêt et, selon le théorème de Rice, toutes les propriétés comportementales non triviales des programmes sont indécidables, aucun outil ne peut détecter parfaitement les boucles infinies, vérifier une correction arbitraire ou analyser entièrement chaque programme ; les analyseurs statiques et les vérificateurs doivent donc approximer, accepter de fausses alertes ou restreindre leur portée.

History

Turing a établi l'indécidabilité du problème de l'arrêt et du problème de décision pour la logique en 1936 en utilisant un argument diagonal inspiré par Cantor et Gödel. Rice a prouvé sa généralisation étendue en 1953, et au cours des décennies suivantes, de nombreux problèmes naturels, y compris le dixième problème de Hilbert sur les équations diophantiennes, se sont avérés indécidables.

Key figures

• Alan Turing
• Henry Gordon Rice
• Emil Post
• Alonzo Church

Seminal works

• turing1937
• sipser2013

Frequently asked questions

Pourquoi ne pouvons-nous pas simplement exécuter un programme pour voir s'il s'arrête ?

L'exécuter ne vous indique qu'il s'est arrêté que s'il le fait réellement ; s'il doit s'exécuter indéfiniment, aucune attente finie ne le révélera. Le problème de l'arrêt exige une méthode qui donne toujours la bonne réponse en un temps fini pour chaque programme et chaque entrée, et Turing a prouvé qu'une telle méthode n'existe pas.

L'indécidabilité rend-elle l'analyse de programme désespérée ?

Non, mais elle explique pourquoi une analyse parfaite est impossible. Les outils y font face en étant conservateurs, en signalant tout ce qu'ils ne peuvent prouver sûr, en traitant exactement des classes restreintes de programmes, ou en résolvant de nombreux cas pratiques tout en admettant qu'ils peuvent échouer sur des cas adverses ou pathologiques.