insieme ricorsivamente enumerabile

insieme ricorsivamente enumerabile

insieme ricorsivamente enumerabile insieme tale che, dato un elemento a, è possibile stabilire, in un numero finito di passi, se esso gli appartenga. Se tuttavia l’elemento non appartiene all’insieme, allora non è assicurata la possibilità di verificare la non appartenenza in un numero finito di passi; in questo senso la condizione di insieme ricorsivamente enumerabile corrisponde alla semidecidibilità (→ insieme decidibile). In termini più rigorosi, un insieme è ricorsivamente enumerabile se e solo se è vuoto oppure è il codominio di una funzione ricorsiva totale; ciò equivale a dire, se si accetta la tesi di → Church, che esiste una qualche procedura algoritmica che genera tutti e soli gli elementi dell’insieme. Bisogna distinguere la nozione di insieme ricorsivamente enumerabile dalla nozione di insieme numerabile: un insieme è numerabile se può essere posto in corrispondenza biunivoca con l’insieme dei numeri naturali, ma la condizione di ricorsiva enumerabilità per un insieme infinito richiede in più di poter produrre un elenco in cui ogni elemento dell’insieme sia effettivamente “raggiungibile”.