À retenir
- Un problème est décidable si une solution existe et est trouvable en un temps limité.
- La réponse doit être binaire : Oui ou Non.
- L'indécidabilité prouve que certaines questions mathématiques ne pourront jamais être résolues par un ordinateur, peu importe sa puissance.
La décidabilité est la capacité d'un problème à être résolu par un ordinateur (ou un algorithme) de manière certaine et dans un temps fini. Pour qu'un problème soit dit « décidable », il faut qu'un programme puisse répondre par « oui » ou par « non » à n'importe quelle question posée, sans risquer de tourner en boucle indéfiniment.
Étymologie
Le terme provient du latin decidere (« trancher », « décider »), auquel on a ajouté le suffixe -ité pour exprimer une propriété. Bien que le mot existe depuis le XIXe siècle, son usage moderne a explosé dans les années 1930 grâce aux travaux d'Alan Turing et d'Alonso Church sur les limites logiques des machines à calculer.
Exemples d'usage
- La parité : Savoir si un nombre entier est pair ou impair est un problème décidable. L'algorithme se termine toujours avec une réponse claire.
- La recherche de mots : Vérifier si un mot précis existe dans un dictionnaire électronique est un problème décidable.
- Le problème de l'arrêt : À l'inverse, savoir si n'importe quel programme informatique va finir par s'arrêter ou rester bloqué pour toujours est un problème indécidable.
Cas d'usage
Ce concept est fondamental en informatique théorique et en logique mathématique. On l'utilise pour définir les limites de ce qu'un logiciel peut accomplir. En cybersécurité ou en compilation, on s'en sert pour savoir s'il est possible de vérifier automatiquement qu'un code ne contient aucune erreur ou faille de sécurité.
Bonnes pratiques
Lors de la conception d'algorithmes complexes, il est crucial de s'assurer que le problème posé est bien décidable. Le piège classique est de tenter de créer un outil de vérification universel (comme un antivirus parfait) qui, par définition mathématique, se heurtera à des problèmes d'indécidabilité.
Synonymes
Antonymes
Conseil
Pour bien comprendre la décidabilité, ne la confondez pas avec la vitesse de calcul. Un problème peut être décidable mais prendre 1000 ans à être résolu. L'important est la garantie théorique que le calcul s'arrêtera un jour.
Questions fréquentes
Un problème difficile est-il forcément indécidable ?
Non. Un problème peut être très long à résoudre (problème complexe) mais rester décidable s'il finit toujours par donner une réponse.
Qui a prouvé l'existence de problèmes indécidables ?
C'est principalement Alan Turing, en 1936, avec sa démonstration sur le problème de l'arrêt.