Рекурзиван скуп

У теорији израчунљивости, скуп природних бројева се назива рекурзивним, израчунљивим или одлучивим ако постоји алгоритам кјои се зауставља након коначног броја корака и тачно одређује да ли дати број припада скупу или не. Скуп који није израчунљив се назива неизрачунљивим или неодлучивим.

Дијаграм затворења проблема одлучивања у теорији израчунљивости

Општија класа скупова се састоји од рекурзивно пребројивих скупова. За ове скупове се захтева само да постоји алгоритам који тачно одређује да број јесте у скупу; алгоритам може да не да одговор (али не сме да да нетачан одговор) за бројеве који нису у скупу.

Формална дефиниција

Подскуп S скупа природних бројева се назива рекурзивним ако постоји тотална израчунљива функција $f\,$ таква да је $f(x)=1\,$ ако $x\in S$ а $f(x)=0\,$ ако $x\notin S$. Другим речима, скуп S је рекурзиван ако и само ако је функција индикатор $1_{S}\,$ израчунљива.

Примери

• Празан скуп је израчунљив.
• Цео скуп природних бројева је израчунљив.
• Сваки коначни или кофинитни подскуп скупа природних бројева је израчунљив.
• Скуп простих бројева је израчунљив.
• Рекурзиван језик је рекурзиван подскуп формалног језика.

Својства

Ако је A рекурзиван скуп, онда је и његов комплемент рекурзиван скуп. Ако су A и B рекурзивни скупови, онда су и A ∩ B, A ∪ B и слика од A × B по Канторовом упаривању, рекурзивни скупови.

Скуп A је рекурзиван скуп ако и само ако су и A и његов комплемент рекурзивно пребројиви скупови. Оригинал рекурзивног скупа у односу на тоталну израчунљиву функцију је рекурзиван скуп. Слика израчунљивог скупа у односу на тоталну израчунљиву бијекцију је израчунљива.

Скуп је рекурзиван ако и само ако је на нивоу $\Delta _{1}^{0}$ аритметичке хијерархије.

Литература

• 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.