Dans la théorie de la calculabilité, un ensemble de nombres naturels est appelé récursif, calculable ou déidable s'il y a un algorithme qui se termine après un temps fini et qui décide correctement si un nombre donné appartient ou non à l'ensemble.
Un ensemble est appelé semidecidable -LRB- ou recursivement énumérable -RRB-, si l'algorithme décrit ci-dessus ne peut décider que si un élément est dans le jeu ou n'est pas dans le jeu dans le temps fini, mais pas les deux.