ensemble récursif

En théorie de la calculabilité, un ensemble récursif ou ensemble décidable est un ensemble d'entiers (ou d'éléments facilement codables dans les entiers) dont la fonction caractéristique est une fonction récursive au sens de la logique mathématique. En d'autres termes, un ensemble est récursif si, et seulement si, il existe une machine de Turing (un programme informatique) permettant de déterminer en un temps fini si un entier quelconque est dans ou pas. Ce type d'ensemble correspond à un concept effectif de John R. Myhill, qui sont les concepts qui peuvent être définis extensivement et sans ambiguïté. La notion d'ensemble récursivement énumérable (non récursif) est plutôt un concept constructif, dont le contenu se précise et se comprend de mieux en mieux avec le temps, sans qu'il soit jamais possible de le cerner complètement.