Un sottoinsieme A dell’insieme N dei numeri naturali si dice decidibile o 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 caratteristica è una funzione ricorsiva.
Linguaggio decidibili
Dire che un linguaggio è decidibile significa dire che è possibile creare una macchina di Turing annessa.