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

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

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

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

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

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

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

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

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.