Limbaj recursiv enumerabil
Această intrare sau secțiune despre programare nu citează sursele necesare sau cei prezenți sunt insuficienți . |
Acest articol sau secțiune despre subiecte de informatică și matematică este considerat a fi verificat . |
Un set A se numește recursiv enumerabil atunci când există o funcție de enumerare f în care A este codomain .
Deoarece există o corespondență unu-la-unu între setul de funcții calculabile și setul de programe în orice limbaj de programare , un set este deci recursiv enumerabil dacă este posibil să-și genereze elementele printr-un program de computer (pentru Church-Turing teza limbajul de programare ales nu contează). Un set recursiv enumerabil este, de asemenea, numit semidecidabil , deoarece este posibil să se stabilească (într-un timp necuantificabil) dacă un element generic aparține lui A, dar nu este posibil să se stabilească non-apartenența unui element.
Exemplu
Fără pierderea generalității, să considerăm setul de funcții calculabile unare și pentru care domeniul și codomain setul de numere naturale . Să luăm în considerare limbajul de programare Pascal .
Întregul
A = {x | x este un număr par}
Este recursiv enumerabil, deoarece este posibil să se definească următorul program (și funcția corespunzătoare).
var a: întreg;
începe
Citeste o);
dacă un mod 2 = 0 atunci
scrie o)
altceva
scrie („2”);
Sfârșit.
Precedent Programul dat ca intrare o mai mare valoare întreagă decât sau egal cu 0 returnează întotdeauna un element al A (se presupune că nu există limite fizice pentru reprezentarea întregi variabile , în acest caz, adică, întreg corespunde setului de numere naturale, de la 0 la plus infinit ).
