##  [Indécidabilité](/fr/node/59958) 

 Définition

Propriété d'un problème de décision indiquant qu'il n'existe aucun algorithme, dans le modèle de calcul choisi, qui s'arrête toujours et décide correctement l'appartenance pour chaque instance d'entrée.

 

 

 

 

 

 





## Principe

Principe

L'indécidabilité se démontre en montrant que tout prétendu décideur permettrait de résoudre un problème déjà indécidable ou conduirait à une contradiction, par réduction, diagonalisation ou arguments d'invariance.

 

 

 

 

 





## Démonstration

Démonstration

Le problème de l'arrêt pour les machines de Turing est indécidable : aucune machine de Turing ne peut dire, pour tout couple programme/entrée codé, si le programme s'arrêtera sur cette entrée.

 

 

 

 

## Mauvaise application

Mauvaise application

Qualifier une question ouverte de 'indécidable' quand on entend seulement 'non résolue à l'état actuel des connaissances', ou confondre indécidabilité au sens calculable avec indépendance par rapport à un système axiomatique donné.

 

 

 

 

 





## Conséquence

Conséquence

Si un problème est indécidable, aucun algorithme général et terminant n'existe ; il faut recourir à des procédures de semi-décision, à des cas restreints, à des heuristiques ou à des hypothèses additionnelles.

 

 

 

 

## Inversion

Inversion

Décidabilité : existence d'un algorithme qui s'arrête toujours et décide correctement l'appartenance pour toutes les instances.

 

 

 

 

 





## Limite

Limite

Concernant des problèmes de décision dans un modèle formel de calcul fixé ; n'implique pas que des instances individuelles ne puissent être résolues ni que des méthodes partielles utiles soient impossibles.

 

 

 

 

 





## Tension sémantique

Tension sémantique

Proche de la notion d'indépendance logique (une assertion ni démontrable ni réfutable à partir d'axiomes) mais distincte : l'indécidabilité porte sur l'impossibilité algorithmique, l'indépendance sur la portée déductive d'une théorie.

 

 

 

 

 





## Synthèse

Synthèse

L'indécidabilité marque les limites de la résolubilité algorithmique : elle survient quand aucun procédé uniforme haltant ne peut décider l'appartenance, imposant le recours à des méthodes plus faibles ou à la reformulation du problème.