Linguaggio ricorsivamente enumerabile

Questa voce o sezione sull'argomento programmazione non cita le fonti necessarie o quelle presenti sono insufficienti.

---

Puoi migliorare questa voce aggiungendo citazioni da fonti attendibili secondo le linee guida sull'uso delle fonti.

Questa voce o sezione sugli argomenti informatica e matematica è ritenuta da controllare.

Motivo: Non è presente una definizione chiara di linguaggio ricorsivamente enumerabile e la definizione di insieme ricorsivamente enumerabile è diversa da quella della data nella sua voce. Inoltre la definizione che si è tentato di dare sembra essere diversa da quella della pagina in lingua inglese

---

Partecipa alla discussione e/o correggi la voce. Segui i suggerimenti dei progetti di riferimento 1, 2.

Un insieme A è detto ricorsivamente enumerabile quando esiste una funzione di enumerazione f di cui A è il codominio.

Essendoci una corrispondenza biunivoca tra l'insieme delle funzioni calcolabili e l'insieme dei programmi in un qualsiasi linguaggio di programmazione, un insieme è quindi ricorsivamente enumerabile se è possibile generare i suoi elementi attraverso un programma per calcolatore (per la tesi di Church-Turing è indifferente il linguaggio di programmazione scelto). Un insieme ricorsivamente enumerabile è anche detto semidecidibile in quanto è possibile stabilire (in un tempo non quantificabile) se un elemento generico appartiene ad A, ma non è possibile stabilire la non appartenenza di un elemento.