À retenir
- Réponse binaire garantie (Oui/Non).
- L'algorithme s'arrête obligatoirement après un certain temps.
- C'est la frontière entre ce qui est automatisable et ce qui ne l'est pas.
En informatique, un problème est dit décidable si l'on peut concevoir un algorithme capable de donner une réponse par « Oui » ou par « Non » de façon certaine en un temps fini. C'est l'équivalent d'une question à laquelle on est sûr de pouvoir répondre après avoir suivi une procédure logique, sans jamais rester bloqué dans une réflexion infinie.
Étymologie
Dérivé du verbe « décider » (du latin decidere, signifiant « trancher ») avec le suffixe « -able » indiquant la possibilité. Ce concept s'est formalisé dans les années 1930 avec les travaux de mathématiciens comme Alan Turing, cherchant à définir les limites de ce qu'une machine peut réellement calculer.
Exemples d'usage
- Vérifier si un nombre est premier : il existe une méthode qui finit toujours par donner la réponse.
- Déterminer si un texte est correctement orthographié selon un dictionnaire donné.
- Savoir si un utilisateur possède les droits d'accès à un dossier spécifique.
Cas d'usage
La notion de décidabilité est fondamentale en théorie de la calculabilité. Elle permet de savoir si un problème peut être confié à un ordinateur. On l'utilise aussi en compilation pour s'assurer que le traducteur de code pourra toujours terminer l'analyse d'un programme, ou en logique mathématique.
Bonnes pratiques
Il ne faut pas confondre décidable et rapide. Un problème peut être décidable mais demander des milliers d'années de calcul. En tant que développeur, l'objectif est de s'assurer que vos fonctions (boucles, récursivité) sont décidables en pratique, c'est-à-dire qu'elles possèdent toujours une condition de sortie garantie.
Synonymes
Antonymes
Conseil
Pour bien appréhender ce concept, imaginez un labyrinthe : s'il est décidable, cela signifie qu'il existe une méthode systématique pour dire s'il y a une sortie ou non, même si cela prend du temps. Si c'est indécidable, vous pourriez errer éternellement sans jamais savoir si la sortie existe.
Questions fréquentes
Est-ce que tout est décidable en informatique ?
Non. Le 'problème de l'arrêt' prouve qu'il est impossible de créer un programme capable de prédire si n'importe quel autre programme s'arrêtera ou tournera en boucle à l'infini.
Quelle est la différence entre décidable et calculable ?
La décidabilité concerne les questions par oui ou non, tandis que la calculabilité concerne le calcul de n'importe quelle valeur (comme le résultat d'une multiplication).