Ensemble récursif et problème décidable
En théorie de la calculabilité (une branche de l'informatique théorique), on dit qu'un ensemble est décidable s'il existe un algorithme qui, étant donné un élément x, détermine en un nombre fini d'étapes si x appartient ou non à l'ensemble. Un ensemble est récursivement énumérable s'il existe un algorithme qui, étant donné un élément, répond oui en un nombre fini d'étapes si l'élément appartient à l'ensemble. Si l'élément n'appartient pas à l'ensemble, l'algorithme peut répondre non, ou bien tourner sans s'arrêter. De façon équivalente, un ensemble est récursivement énumérable s'il existe un algorithme qui liste tous les éléments de l'ensemble. Un sens précis au mot "algorithme" peut être donné dans les définitions précédentes. Cela peut être par exemple les machines de Türing. On montre qu'il existe des ensembles qui sont récursivement énumérables, mais qui ne sont pas récursifs, un ensemble étant récursif si lui, ainsi que son complémentaire, sont récursivement énumérables. Un problème est décidable si l'ensemble de ses solutions est récursif. Il est dit semi-décidable si l'ensemble de ses solutions est récursivement énumérable. Les problèmes décidables sont donc ceux que l'on sait résoudre à l'aide d'un algorithme en un temps fini.Consulter aussi
Recherche alphabétique
Recherche thématique