Decidibilità: differenze tra le versioni

Nella teoria della computabilità un sottoinsieme ''A'' dell'insieme '''N''' dei [[numeri naturali]] si dice '''decidibile''' o [[insieme ricorsivo|ricorsivo]] se esiste un [[algoritmo]] che ricevuto in input un qualsiasi numero naturale termina restituendo in output 0 o 1 a seconda che il numero appartenga o no all'insieme ''A''. Equivalentemente ''A'' è decidibile se la sua [[funzione indicatrice|funzione caratteristica]] è una [[funzione ricorsiva]].