insieme ricorsivo

Nella teoria della calcolabilità un insieme ricorsivo (o insieme decidibile) è intuitivamente un insieme di numeri naturali, per cui è possibile costruire un algoritmo che in un tempo finito (ma a priori non predeterminato) sia in grado, dato un qualunque numero naturale, di stabilire se esso appartiene o no all'insieme. Più formalmente si dice che un insieme è ricorsivo se la sua funzione caratteristica è ricorsiva.