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 definicijaUredi

Podskup S skupa prirodnih brojeva se naziva rekurzivnim ako postoji totalna izračunljiva funkcija   takva da je   ako   a   ako  . Drugim rečima, skup S je rekurzivan ako i samo ako je funkcija indikator   izračunljiva.

PrimeriUredi

SvojstvaUredi

Ako je A rekurzivan skup, onda je i njegov komplement rekurzivan skup. Ako su A i B rekurzivni skupovi, onda su i AB, AB 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   aritmetičke hijerarhije.

LiteraturaUredi