Set ricorsivamente enumerabile
Nella teoria della computabilità, tradizionalmente chiamata teoria della ricorsione, un insieme S dei numeri naturali viene chiamato ricorsivamente enumerabile, computabilmente enumerabile, semidecidabile, provabile o riconoscibile da Turing se: ▪ Esiste un algoritmo tale che l'insieme dei numeri di input per cui l'algoritmo si ferma Esattamente S. O, equivalentemente, ▪ Esiste un algoritmo che enumera i membri di S. Ciò significa che la sua uscita è semplicemente un elenco dei membri di S: s1, s2, s3, .... Se necessario, questo algoritmo può Correre per sempre. La prima condizione suggerisce perché il termine semidecidable è talvolta usato; Il secondo suggerisce perché è computabilmente enumerabile. Le abbreviazioni r.e. E c.e. Sono spesso utilizzati, anche in stampa, anziché la frase completa. Nella teoria della complessità computazionale, la classe di complessità contenente tutti gli insiemi ricorsivamente enumerabili è RE. Nella teoria della ricorsione, il reticolo di r.e. È indicato nell'ambito dell'inserimento.