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

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

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

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

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

Подскуп 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.