Алгоритмдер теориясы
lip_image188.gif" width="8" />(х)) =0
болатынын көру қиын емес.
Теорема6.12Берілген тұрақты х саны мен кез келген усаны бойынша усаны   функциясының мәндер жиынында жататынын немесе жатпайтынын анықтайтын алгоритмнің бар болуы х санына байланысты.
Дәлелдеуі. х санын  (у) = у болатындай етіп таңдап алайық. функциясы у-тің кез келген мәнінде анықталатындықтан, іздеп отырған функциямызды f(х)=1 деп алуымызға болады. Бұл - алгоритмнің табылатын жағдайы.
Енді алгоритм табылмайтын жағдайды көрсетейік.  (х) мәнін анықтау үшін  функциясының нұсқаулар жиынын тауып, оны х-ке пайдаланайық. Егер мәні анықталса, онда (х)= х дейік. -дің рекурсивті екендігі түсінікті. Және
(х) анықталса, онда (х)=х
(х) анықталмаса, онда (х)те анықталмайды.
х - осы функцияның нөмірі, яғни,  болсын.Кез келген усаны бойынша усаны функциясының мәндер жиынында жататынын немесе жатпайтынын анықтайтын алгоритмнің жоқ екенін көрсетейік. Дәлелдеу үшін кері жориық.
усаны -тің мәндер жиынында жатса, онда f(у)=1,
усаны -тің мәндер жиынында жатпаса, онда f(у)=0
болатын f функциясы табылсын. Осы жерден
(х) анықталса, онда (х)= (х) =х, Яғни, хсаны функциясының мәндер жиынында жатады, сондықтан f(х)=1;
(х) анықталмаса, онда (х)= (х) те анықталмайды, ал функциясы басқа аргументте х-ке тең болмайтынын ескерсек, онда хсаны функциясының мәндер жиынында жатпайтынын көреміз, сондықтан f(х)=0.
(х) анықталса, онда f(х)=1;
(х) анықталмаса, онда f(х)=0.
Салдарға қарама-қайшылық.
Жаттығулар
1. Кез келген хпен у үшін  теңдігін тексеретін алгоритм бар ма?
2. Кез келген х,у,z үшін  теңдігін тексеретін алгоритм бар ма?
3. Кез келген х үшін функциясының анықталу облысының бос жиын болатындығын не болмайтындығын анықтайтын алгоритм бар ма?
4. Кез келген х үшін функциясының анықталу облысының ақырлылығын анықтайтын алгоритм бар ма?
5. Берілген тұрақты х мен кез келген у үшін  теңдігін тексеретін алгоритм бар ма?
6.6 Рекурсивті және рекурсивті есептелімді жиындар
Анықтама.  болғанда  ;
 болғанда 
шартын қанағаттындыратын  функциясын А жиынының характеристикалық функциясы деп атаймыз.
Анықтама. Характеристикалық функциясы жалпы рекурсивті болатын жиынды рекурсивті жиын деп атаймыз.
Былайша айтқанда, рекурсивті функциялар үшін кез келген элементтің осы жиынға тиістілігін анықтайтын алгоритм болу керек.
Мысалы, жұп сандар жиыны – рекурсивті жиын. Бос жиын мен барлық натурал сандар жиынының рекурсивті екенін байқау қиын емес. Ал {х |  анықталған} жиыны тоқтау мәселесі бойынша рекурсивті жиын емес.
Егер А жиыны рекурсивті болса, онда осы жиынның толықтауышы N Aда Черч тезисі бойынша рекурсивті. Шынында да  .
Анықтама. Бос жиын немесе жалпы рекурсивті функцияның мәндер жиын
| |  скачать работу |
Алгоритмдер теориясы | 
