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

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

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

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

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

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

Примери[уреди]

Својства[уреди]

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

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

Скуп је рекурзиван ако и само ако је на нивоу \Delta^0_1 аритметичке хијерархије.

Литература[уреди]