Rekurzivan skup

Dijagram zatvorenja problema odlučivanja u teoriji izračunljivosti

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.

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.