Алгоритмдер теориясы

ы болатын А жиынын рекурсивті есептелімді жиын деп атаймыз.

Теорема6.13Кез келген рекурсивті жиын рекурсивті есептелімді болады.

Дәлелдеуі. ¶ш жағдай болуы мүмкін.

1) А - бос жиын. Бұл жағдайда А жиыны анықтама бойынша рекурсивті есептелімді.

2) А - бос емес ақырлы жиын. Мысалы, А болсын. Онда

болған кезде =

болған кезде

шартын қанағаттындыратын функциясын қарастырайық. Бұл функция Черч тезисі бойынша рекурсивті. Және кез келген мәнінде анықталғандықтан, жалпы рекурсивті функция. Оған қоса А жиыны функциясының мәндер жиыны екені түсінікті.

і) А ақырсыз жиын болсын, ал А жиынының характеристикалық функциясы болсын.

арқылы шартын қанағаттандыратын ең кіші -ті белгілейік,

арқылы шартын қанағаттандыратын -тен үлкен ең кіші -ті белгілейік.

Черч тезисі бойынша функциясы рекурсивті. А жиыны ақырсыз болғандықтан, бұл функция кез келген аргументінде анықталған. Сонымен, - жалпы рекурсивті функция. А жиыны функциясының мәндер жиыны екенін байқау қиын емес. Теорема дәлелденді.

Теорема6.14 жиыны рекурсивті болу үшін А мен NА жиындары рекурсивті есептелімді болулары қажет және жеткілікті.

Қажеттілігі.А жиыны рекурсивті болғандықтан, NА жиыны да рекурсивті. Теорема 17 бойынша жоғарыдағы жиындар рекурсивті есептелімді.

Жеткіліктілігі.Егер А мен NА жиындарының біреуі бос болса, онда А жиынының рекурсивті екендігі түсінікті. Енді осы жиындардың екеуі де бос болмасын. Онда А мен NА жиындары мәндерінің жиыны болатын сәйкес пен функциялары табылады. Біз кезекпен мәндерін есептейміз. А жиынына тиісті сандар, А жиыны функциясының мәндерінің жиыны болғандықтан, тақ қадамда шартты түрде кездесуі керек. Тура сол сияқты NА жиынына тиісті х санына шартын қанағаттындыратын саны табылатындықтан, бұл сан жұп қадамда кездеседі. Сонымен, кез келген сан жоғарыдағы тізімде кездеседі. Тақ қадамда кездессе, онда ол А жиынына тиісті; жұп қадамда кездессе, онда оның толықтауышына тиісті. функциялары жалпы рекурсивті болғандықтан, А жиынына тиістілігін анықтау алгоритм болады. Дәлелдеуіміз керегі де осы еді.