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

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

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

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

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

Подскуп S скупа природних бројева се назива рекурзивним ако постоји тотална израчунљива функција   таква да је   ако   а   ако  . Другим речима, скуп S је рекурзиван ако и само ако је функција индикатор   израчунљива.

ПримериУреди

СвојстваУреди

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

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

Скуп је рекурзиван ако и само ако је на нивоу   аритметичке хијерархије.

ЛитератураУреди