Rekurzivan skup

U teoriji izračunljivosti, skup prirodnih brojeva se naziva rekurzivnim, izračunljivim ili odlučivim ako postoji algoritam kjoi se zaustavlja nakon konačnog broja koraka i tačno određuje da li dati broj pripada skupu ili ne. Skup koji nije izračunljiv se naziva neizračunljivim ili neodlučivim.

Dijagram zatvorenja problema odlučivanja u teoriji izračunljivosti

Opštija klasa skupova se sastoji od rekurzivno prebrojivih skupova. Za ove skupove se zahteva samo da postoji algoritam koji tačno određuje da broj jeste u skupu; algoritam može da ne da odgovor (ali ne sme da da netačan odgovor) za brojeve koji nisu u skupu.

Formalna definicija

Podskup S skupa prirodnih brojeva se naziva rekurzivnim ako postoji totalna izračunljiva funkcija $f\,$ takva da je $f(x)=1\,$ ako $x\in S$ a $f(x)=0\,$ ako $x\notin S$. Drugim rečima, skup S je rekurzivan ako i samo ako je funkcija indikator $1_{S}\,$ izračunljiva.

Primeri

• Prazan skup je izračunljiv.
• Ceo skup prirodnih brojeva je izračunljiv.
• Svaki konačni ili kofinitni podskup skupa prirodnih brojeva je izračunljiv.
• Skup prostih brojeva je izračunljiv.
• Rekurzivan jezik je rekurzivan podskup formalnog jezika.

Svojstva

Ako je A rekurzivan skup, onda je i njegov komplement rekurzivan skup. Ako su A i B rekurzivni skupovi, onda su i A ∩ B, A ∪ B i slika od A × B po Kantorovom uparivanju, rekurzivni skupovi.

Skup A je rekurzivan skup ako i samo ako su i A i njegov komplement rekurzivno prebrojivi skupovi. Original rekurzivnog skupa u odnosu na totalnu izračunljivu funkciju je rekurzivan skup. Slika izračunljivog skupa u odnosu na totalnu izračunljivu bijekciju je izračunljiva.

Skup je rekurzivan ako i samo ako je na nivou $\Delta _{1}^{0}$ aritmetičke hijerarhije.

Literatura

• Cutland, N. Computability. Cambridge University Press, Cambridge-New York. 1980. ISBN 978-0-521-22384-3.. ISBN 978-0-521-29465-2.
• Rogers, H. The Theory of Recursive Functions and Effective Computability, MIT Press. ISBN 978-0-262-68052-3. ISBN 978-0-07-053522-0
• Soare, R. Recursively enumerable sets and degrees. Perspectives in Mathematical Logic. Springer-Verlag, Berlin. 1987. ISBN 978-3-540-15299-6.