Алгоритимге кириспе

                                           Алгоритм ұғымы

Алгоритм ұғымы - математикада вектор, жиын секілді негізгі ұғымдардың бірі. Негізгі ұғымдардың дәл анықтамасы болмайды. Оларды тек интуициямен қабылдаймыз. Дегенімен, осы параграфта алгоритм ұғымын мағыналық тұрғыдан анықтауға тырысамыз.  
Көбінесе алгоритм ұғымын берілген элементке сәйкес элементті берілген нұсқаулар арқылы табу деп түсінеміз.  
Бірақ бұл анықтама - математикалық тұрғыдан алғанда дәл анықтама емес. Себебі, есептеу, нұсқау ұғымдарының да анықтамасы берілмеген.  
Алгоритм ұғымын анықтаудың алдында бірнеше мысалдар келтірейік.  
(х) = х-ші жай сан. Бұл функцияны есептеуге алгоритм ретінде Эратосфен елегін пайдалануға болады.¦1.   
(х,у) = х пен у-тің ең үлкен ортақ бөлгіші. Бұл жерде Евклид алгоритмі жұмыс істейді.¦2.   
- көпмүше. Көпмүшелердің туындысы алу алгоритмі мектептен белгілі.¦) = , бұл жерде ¦(m3.   
Біз көбінесе тек қана натурал сандарға қолданылатын алгоритмтерді қарастырамыз.  
Алгоритмдер төмендегі ортақ қасиеттерімен сипатталады:  
1. Алгоритм ақыpлы өлшемді нұсқаулар жиыны ретінде беріледі.  
2. Нұсқауларды түсініп, есептеулерді жүргізетін есептегіш (көбінесе адам) болады.  
3. Есептеулердің кез келген бөлігін бөліп алуға, жаттауға және кейбір қадамдарын қайталауға мүмкіндіктер бар.  
4. Есптегіш нұсқаулар бойынша әр берілген санға сәйкес есептеу кезінде қадамдары дискретті түрде кездейсоқ әдістерсіз жұмыс істейді.  
Бұл қасиеттер электронды есептеу машиналарға ұқсастықты көрсетеді. Шынында да  
1) машинаның программасы,  
2) есептеу құрылысы,  
3) жаттау қабілеті,  
4) табиғи құрлысы.  
Әрине көрсетілген төрт қасиет алгоритмді дәл анықтайды деп айта алмаймыз. Бұл жерде көптеген сұрақтар пайда болады. Солардың бірнешесін қарастырайық.  
1) Берілген санның өлшемін шектеу қажет пе?  
Егер (х) = функциясын есептеудің¦біз "иә" деп жауап берсек, онда, мысалы,  алгоритмі жоқ болады. Себебі, берілетін сан кез келген ақырлы сан болуы мүмкін. Сондықтан, біз "жоқ" деп жауап береміз және олар тек ақырлы болуы керек дейміз.  
2) Нұсқаулардың өлшемін шектеу қажет пе?  
Күрделі есептерді шығару үшін біздің нұсқауларымызды шекті деп аламыз, бірақ нұсқаулардың да ақырлы болу керектігін ұмытпаймыз.  
3) Жаттау қабілетін шектеу қажет пе?  
Алдыңғы екі сұраққа жоқ деп жауап берген соң, бұл сұраққа да "жоқ" деуіміз қажет. Бірақ бір қызығы, кез келген машинаның жаттау қабілеті шектеулі. Дегенмен ол қазіргі керекті есептеулерге жеткілікті.

                                    Тьюринг машинасы

Алан Мэтисон  Тьюринг –  ағылшын математигі,логик,криптографы 1912 жылы 23 маусымында дүниеге келіп 1954 жылдың 7 маусымынды қайтыс болған. Ол информатика ғылымына үлкен үлес қосқан. Британ империясы орденінің ковалері. Оның 1936 жылы ұсынған абстрактілі есептеуіш «Тьюринг машинасы» алгоритм түсінігін қалыптастыруға мүмкіндік берді және көптеген практикалық және теориялық зерттеулерде қолданылып келеді. Ол Францияда, Англияда содан кейін АҚШ-та оқыған.Тьюринг АҚШ-тан оралғанда екінші дүние жүзілік соғыс басталған еді.1945 жылы «ТУЗ» компьютерін құраудың жобасын өз қолына алған, ал 1948 жылы «МАДАМ» компьютерімен жұмыс істеуін басталы, бұл сол уақыттағы ең көп жадты компьютер болатын. Тьюрингтің жұмыстары ЭЕМ дамуына үлкен үлесін қосқан. 1952 жылы Тьюринг тірі организмдер формасының дамуы туралы теориялық зерттеуінің бірінші бөлімін жарыққа шығарды. Бірақ бұл жұмыс аяқталмай қалды.

1936 жылы Тюринг кез  келген есептеуді орындай алады  деген жорамалмен теориялық машиналар  класын енгізді. Олардың сипаттамасын берейік.  
Көз алдымызға квадратттарға бөлінген ақырлы лентаны елестетейік. Машинаның алфавиті болып аталатын символдары беріледі. Әр кезде әр квадратқа бір символ жазылады. Әр кезде квадратта бір символдан артық болмайды. Машинаның іùкі жағдайлары болып табылатын жиыны болады. Әр кезде машина сол ішкі жағдайлардың біреуінде ғана болады. Сонымен бірге кез келген уақытта квадраттардың біреуін ғана қарастыратын оқу тетігі бар. Машина бір мезетте бір ғана қимыл істейді. Егер машинаның оқу тетігі қарастырылып тұрған квадратта символы тұрса, ал машинаның ішкі жағдайы болса, онда ол келесі қимылдардың біреуін істейді:  
1. Осы квадраттағы символын өшіріп, символын осы квадратқа жазады;  
2. Оң жақтағы көрші квадратқа көшеді;  
3. Сол жақтағы көрші квадратқа көшеді;  
4. Тоқтайды.  
Алдыңғы үш жағдайда машина басқа ішкі жағдайға көшіп, келесі қимылға дайын. Екінші немесе үшінші қимыл кезінде көрші квадрат жоқ болса, онда керек квадрат пайда болады деп есептейміз.  
Бос клеткада символы бар деп есептейік. Онда кез келген уақытта кез келген клеткада символ бар. Алдыңғы үш қимылды болашақта бұйрық деп атайтын келесі реттелген төрттіктермен белгілеуге болады:  
(1) , (2) , (3) .  
Бұл жерде алдыңғы екі символ - машинаның ішкі жағдайы мен қарастырылып отырған квадраттағы символ, үшіншісі - қандай символ жазылатындығының немесе оқу тетігінің не солға не оңға жылжуының белгісі, ал төртіншісі қандай ішкі жағдайға көшетінін көрсетеді.  
Сонымен енді біз кез келген Тьюринг машинасы мен осы машинаның алфавитінде құрылған алгоритмді байланыстыра аламыз. Осы алфавиттегі кез келген сөзді солдан оңға қарай жазамыз. Оқу тетігі ең сол шеткі квадратты қарастырып тұрған кезде машина ішкі жағдайында жұмысты бастайды. Әр қадамда не символ өшіріп, басқа символ жазады, не көрші квадраттардың біріне көшеді. Егер машина жұмысын тоқтатса, онда лентадағы сөз алгоритмнің нәтижесі болып есептеледі. Енді Тьюpинг машинасының дәл анықтамасын берейік. Келесі екі шартты қанағаттандыратын ақырлы төрттіктер жиынын Тьюринг машинасы деп атаймыз:  
1. Төрттіктердің кез келгені не , не не түрінде болады.  
2. Алдыңғы екі символдары бірдей болатын төрттіктер жоқ.  
Әр төрттік бұйрық деп аталады. Бұйрықтарға енетін символдары сытрқы жағдайлар деп аталады. Бұйрықтардағы символдары ішкі жағдайлар деп аталады. кез келген машинаның ішкі жағдайы болып табылады.  
Егер Р - бос болуы мүмкін, ал Q бос емес сөз болса және - машинаның ішкі жағдайы болса, онда машинаның конфигурациясы деп аталады. Егер келесі b конфигурациясын aшарттардың біреуі орындалса, онда машина  конфигурациясына көшіреді дейміз:  
конфигурациясы түрінде, ал - машинаның бұйрықтарының біреуі;b конфигурациясы түрінде, a1)   
- түрінде, ал - машинаның бұйрықтарының біреуі;b - түрінде, a2)   
- түрінде және - машинаның бұйрықтарының біреуі;b - түрінде, a3)   
- түрінде және - машинаның бұйрықтарының біреуі;b - түрінде, a4)   
- түрінде және - машинаның бұйрықтарының біреуі.b - түрінде, a5)   
Егер -ден басталатын бұйрық болмаса, онда машина конфигурациясында тоқтайды деп атаймыз.  
m-1£ і £Егер конфигурациясына енетін ішкі жағдай болса, кез келген 0  шартын қанағаттандыратын і үшін машина конфигурациясын конфигурациясына көшірсе, ал конфигурациясында тоқтаса, онда ақырлы конфигурациялар тізбегі машинаның есептеуі деп аталады. Және есептеуі -ден басталып, -мен аяқталады дейміз. Т машинаның алгоритмін келесі түрде анықтаймыз:  
(Р) = Q орындалуы үшін конфигурациясынан басталып, =Q теңдігі орындалатын конфигурациясымен аяқталуы керек.  
Ескерту. сөздеріндегі символдарын ескермейміз. Себебі барлық уақытта бұл символ бос квадратты білдіреді.  
Енді натурал сандарға қолданылатын алгоритмдерге көшейік. Кез келген натурал m санына m+1 - бірліктен тұратын тізбекті сәйкес қоямыз және оны деп белгілейміз. Мысалы, 2-ге 111, 5-ке 111111. Егер кез келген сандары үшін = теңдігі орындалса, онда Тьюринг машинасы жартылай анықталған ( ) функциясын есептейді дейміз.¦арифметикалық   
Берілген функцияны есептейтін Тьюринг машинасы табылса, ол функция Тьюринг бойынша есептеледі деп аталады.  
Кез келген Тьюринг машинасын кез келген n саннан тұратын тізбекке (х) функциясын есептейтін Тьюринг¦пайдалануға болады. Берілген  машинасына екі сан берсек, ол машина басқа функцияны есептейді.  

                                        Черч тезисі, геделдік нөмірлеу

Алгоритмнің кез келген формализациясын алгоритмнің дәл анықтамасы екенін дәлелдеу мүмкін емес. Оны не қабылдауға, не қабылдамауға болады. Тьюрингтен бөлек математиктер де есептеуге болатын функциялардың анықтамаларын берді. Дегенімен, олардың барлығы Тьюринг анықтамасымен эквивалент болып шықты. Есімізге Клини, Пост, Марковтардың анықтауларын алсақ та жеткілікті. Сондықтан, осы формализациялардың кез келгенін алгоритмнің дәл анықтамасы ретінде алуға болады деп есептелінеді. Бұл ойды Черч айтқан болатын. Сонымен, өзара эквивалент екі сөйлемді келтірейін.  
Черч тезисі. Есептеуге болатын функциялар жиыны Тьюринг машинасында есептелінетін функциялар жиынына тең.  
Черч тезисі. Алгоритмі бар функцияны есептейтін Тьюринг машинасы бар.  
Бұл эквивалент екі тезистің ешқайсысын дәлелдеу мүмкін емес. Себебі, ол үшін алгоритмнің дәл анықтамасы карек. Бұл тезиске келіспеген математиктердің Тьюринг машинасы есептемейтін алгоритм табуға тырысқан еңбектерінен ештеңе шықпады. Сондықтан, қазіргі заманда Черч тезисімен келіспеген математиктер қалмады деуге болады.  
Кейбір Тьюринг машиналары кейбір мәндерінде тоқтамауын байқау қиын емес. Сондықтан, Тьюринг машинасымен есептелетін функцияларды кейде жартылай рекурсивті функция деп атайды, кейде рекурсивті функция деп атайды.  
Eнді біз рекурсивті функцияларды қалай нөмірлейтінімізді көрсетейік.  
Лемма 6.1. Тьюринг машинасының бұйрықтар жиынын нөмірлеп шығуға болады.  
Дәлелдеуі. Біз , , төрттіктеріне <j, і, r+2,z>, <j, і, o, z> және <j, і, 1, z> төрттіктерін сәйкес қояйық. Бұл сәйкестік өзара бір мәнді және кері сәйкестік табылатынын көру қиын емес. Сонымен, біз <j, і, k, r> төрттіктерін нөмірлеп шығайық. Координаталарының қосындысы 0-ге тең бір-ақ <0, 0, 0, 0> төрттігі бар. Оған 0 cанын сәйкес қоямыз. Координаталардың қосындысы бірге тең төрт төрттік бар. Оларға қандай да тәртіппен 1-ден 4-ке дейінгі сандарды береміз. Тура осылай, координаталарының қосындысы e-ге тең төрттіктер саны ақырлы екенін еске түсірсек, онда осы әдіспен барлық төрттіктерді нөмірлеп шығуға болады. Лемма дәлелденді.  
Лемма 6.2. Бұйрықтар саны берілген e-ге тең Тьюринг машиналарын нөмірлеп шығуға болады.  
Дәлелдеуі. Бірінші лемма бойынша бұйрықтың орнына оның нөмірін алуға болады. Сонымен, біз e координатасы бар сандар жиынының ішкі жиынын нөмірлеуіміз керек. Біз тағы да координаталарының қосындысы k-ға тең e-ліктердің ақырлы екенін пайдаланамыз және k-ны өсіре отырып барлық e бұйрығы бар жиындарды нөмірлейміз. Берілген k үшін жұмыс алгоритмін көрсетейік. Координаталарының қосындысы k-ға тең барлық e-ліктер жиыны {< >, < >,…, < >} болсын. Осы уақытқа дейінгі ең үлкен нөмір t болсын. Егер қандай да екі үшін болса, онда бірінші e-лік нөмір алмайды. Егер мен -лерге сәйкес бұйрықтар бірдей екі символдан басталса, онда да нөмір берілмейді. Бұл екі шарт орындалмаған жағдайда бірінші e-ліктің нөмірі ретінде t+1 санын аламыз. Келесі e-лікке көшеміз. Лемма дәлелденді.  
Теорема 6.1. Ақырлы бұйрықтар жиындарының жиынын нөмірлеуге болады.  
Дәлелдеуі. Бұйрықтар саны мен сол санға сәйкес екінші лемма бойынша алынған нөмірдің қосындысы берілген санға тең болатын бұйрықтар жиындарының ақырлы екені түсінікті. Леммалардың дәлелдеуіндегі идеямен теореманың дәлелдеуін аяқтауға болады.  
Салдар 6.1. Тьюринг машиналарын нөмірлеп шығуға болады.  
Дәлелдеуі. Кез келген машина өзінің бұйрықтар жиынымен бір мәнді анықталады.  
Бірінші рет рекурсивті функциялар жиынын нөмірлеп шыққан Гедель болатын. Сондықтан, біз жоғарыда көрсеткен нөмірлеуімізді гедельдік нөмірлеу деп атаймыз.  
Сонымен арқылы k айнымалысы бар рекурсивті функциялар жиынын белгілейік.

                                             Черч тезисінің салдарлары

Енді Черч тезисінен шығатын  бірнеше теоремаларға тоқтай кетейік.  
Теорема 6.2 Жартылай рекурсивті функциялар жиыны саналымды.  
(х) = k функциясы кез келген k үшін¦Дәлелдеуі. Черч тезисі бойынша  рекурсивті. Сондықтан, жартылай рекурсивті функциялар кем дегенде саналымды. Екінші жағынан төртінші салдар бойынша олар саналымдыдан артық емес.  
Анықтама. Кез келген мәнінде анықталған жартылай рекурсивті функция жалпы рекурсивті функция деп аталады.  
Салдар 6.2 Жалпы рекурсивті функциялар саналымды.  
(х) = k функциясы кез келген k үшін анықталған. Сондықтан,¦Дәлелдеуі.  олар кем дегенде саналымды. Екінші жағынан, жалпы рекурсивті фундциялар жиыны жартылай рекурсивті функциялар жиынының ішкі жиыны болғандықтан саналымдыдан артық емес. Біз төртінші салдарда жартылай рекурсивті функциялар жиынын нөмірлеп шыққанбыз. Ең қызығы, олардың ішкі жиыны жалпы рекурсивті функцияларды нөмірлеуге болмайды екен.  
Теорема 6.3. Жалпы рекурсивті функцияларды нөмірлеп шығу мүмкін емес.  
Дәлелдеуі. Кері жориық. Қандай да бір алгоритмді пайдаланып, жалпы рекурсивті функцияларды нөмірледік дейік, яғни оларды түріндегі тізбек арқылы тізімдеуге болады деп есептейміз. Онда біз келесі нұсқауларды пайдаланып, функциясын құрастырайық. Ізделініп отырған функциясының х нүктесіндегі мәнін есептеу үшін функциясының нұсқаулар жиынын табу керек. Осы нұсқаулар жиынын х санына пайдаланамыз. Берілген функциясы жалпы рекурсивті функция болғандықтан, қандай да бір мезетте жауап табылады. Берілген жауапқа бірді қосып жауап ретінде береміз. Черч тезисі бойынша - рекурсивті функция. Кез келген х үшін - жалпы рекурсивті функция болғандықтан, - жалпы рекурсивті функция. Олай болса, берілген тізімде болу керек. Яғни, қандай да бір үшін = .  
Енді ( ) неге тең екенін байқасақ, онда ол ( )+1 -ге тең болады. Онда ( )= ( )+1. қарама - қайшылық. Теорема дәлелденді.  
Кейде осы көрсетілген әдісті неге жартылай рекурсивті функцияларға қолдануға болмайды деген сұрақ туады. Ізделініп отырған функциясының нөмірі болсын. Бұл жерде нөмірлі алгоритм санында есептелініп болмауы мүмкін. Онда біз функция мәніне бірді қоса алмаймыз.  
Теорема 6.4 Рекурсивті емес функциялар бар.  
Дәлелдеуі. Кантор теоремасы бойынша континиум функция бар. Яғни, рекурсивті емес функция табылады.  
Теорема 6.5 Кез келген рекурсивті функцияның саналымды нөмірі бар.  
Дәлелдеуі. Нөмірлер саны саналымды болғандықтан, функция нөмірлері кем дегенде саналымды екенін көрсетсек жеткілікті. Берілген рекурсивті функцияның нұсқауларындағы ішкі жағдайлардың ең үлкені m-нен кіші болсын. Біз берілген нұсқауларға , ,…, нұсқауларын қандай да бір k үшін қосып көрейік. Есептеу -ден басталады және есептеу кезінде , ,…, ішкі жағдайлары пайда болуы мүмкін емес. Сондықтан, алғашқы нұсқаулар жиыны қандай конфигурацияда тоқтаса, соңғы нұсқаулар жиыны да сол конфигурацияда тоқтайды. Яғни, соңғы нұсқаулар жиыны да сол рекурсивті функцияны есептейді. Бірақ, олардың нөмірлері әртүрлі. Және бұл мүмкіндік кез келген k үшін бар. Теорема дәлелденді.  
Теорема 6.6 Кез келген х пен у үшін: егер анықталған болса, онда = ; егер анықталмаған болса, онда де анықталмаған z саны табылады.  
Дәлелдеуі. Бізге < х, у > берілсін. Нөмірі х болатын Тьюринг машинасын табамыз. Осы машинаны у-ке пайдаланамыз. Егер есептеу аяқталып, жауап берілсе, онда сол жауапты біз де жауап ретінде береміз. Сонымен, тапқан функция

=  
анықталмаған, егер анықталмаған

- функциясы рекурсивті. Бұл  функцияның нөмірі бар. Ол нөмірді z дейік. Яғни (х,у)=  
1 үшін³Теорема 6.7 Кез келген m,n   
теңдігі орындалатын функциясы табылады.  
Дәлелдеуі: Черч тезисі бойынша.  
Бұл теореманы болашақта s-m-n теорема деп атаймыз.

                                           Шешілмейтін мәселелер

Берілген х,у сандары  бойынша есептелетіндігін анықтайтын алгоритм табылады ма деген сұраққа  жауап іздейік. Чёрч тезисі пайдалансақ, онда бұл сұрақты келесі дәлірек түрде беруге болады. есептелсе, g(х,у) =1, ал егер есептелмесе, онда g(х,у) функциясы да есептелмейтіндей g рекурсивті функциясы табыла ма? Бұл сұраққа келесі теоремамен жауап берейік.  
Теорема 6.8 есептелсе, g(х,у) =1, ал егер есептелмесе, онда g(х,у)=0 болатындай g рекурсивті функциясы табылмайды.  
Дәлелдеуі. Кері жориық. Іздеген g рекурсивті функциясы табылсын. Кез келген мәнінде анықталғандықтан бұл функция жалпы рекурсивті. Енді біз осы функцияның көмегімен g(х,х)=0 болса, онда 1-ге тең, ал егер g(х,х)=1 болса, онда анықталмаған функциясын табайық. g функциясы рекурсивті болғандықтан, функциясы да рекурсивті. Сондықтан бұл функцияның нөмірі бар. Яғни, қандай да бір үшін (у)= . Енді мәнін есептейік. Екі мүмкіндік бар.  
Бірінші мүмкіндік анықталмаған. Онда z санының анықтамасы бойынша (z) функциясы да анықталмаған. Яғни g(z,z) =1. g функциясының анықтамасын қарасақ, онда есептелетін болып шығады. Демек, анықталған. Қарама-қайшылық.  
Екінші мүмкіндікте анықталған. Тағы да z санының анықтамасын қарасақ, онда (z) те анықталған. Яғни g(z,z) = 0. Енді g функциясының анықтамасы бойынша есептелмейтін болып шығады. Демек, анықталмаған. Тағы да қарама-қайшылық. Теорема дәлелденді.  
Салдар 6.3 есептелсе, g(х) =1, ал егер есептелмесе, онда g(х)=0 болатындай g рекурсивті функциясы табылмайды.  
Дәлелдеуі. Кері жорысақ, бұл кезде де теоремада кездескен функциясы рекурсивті болып шығады. ф  
Жоғарыда қойылған сұрақты тоқтау мәселесі деп атаймыз. Бұл мәселе математиктерге кездескен бірінші алгоритмдік шешімі жоқ табиғи мәселе болды. Әрине кейінірек алгоритмдік шешімі жоқ мәселелер көбірек кездесті. Солардың мысалдарын келтірейік.  
Теорема 6.9 Берілген х саны бойынша функциясының тұрақты болатындығын не болмайтындығын анықтайтын алгоритм жоқ.  
Дәлелдеуі. х пен у сандары берілсін. функциясының нұсқаулар жүйесін тауып, оны х-ке қолданайық. Егер есептеу процесі аяқталса, онда жауап ретінде 0 санын берейік. Черч тезисі бойынша, бұл - қандай да бір рекурсивті f(х,у) рекурсивті функцияның нұсқаулар жиыны. z осы функцияның нөмірі болсын, Яғни, f(х,у) = (х,у). s-m-n теорема бойынша f(х,у)= = (х,у)= болатын h(z ,х) функциясы табылады. z тұрақты сан болғандықтан, h(z ,х) =h (х) теңдігі орындалатын h (х) функциясын қарастыруымызға болады. Сонымен, (у) тұрақты мәні нөлге тең функция болуы үшін (х) анықталған болуы қажет және жеткілікті.  
Енді кері жорып, алгоритм бар дейік. Яғни,  
егер тұрақты функция болса, онда g(х)= 1,  
кері жағдайда g(х)=0  
болатын g рекурсивті функциясы табылсын. Онда  
(х) анықталса, онда g(h (х)) =1,  
(х) анықталмаса, онда g(h (х)) =0.  
Салдарға қарама-қайшылық. Себебі, салдар бойынша табылмайтын функция -gh .  
Теорема 6.10 Берілген х саны бойынша функциясының мәндер жиынының ақырлылығын анықтайтын алгоритм жоқ.  
Дәлелдеуі. х пен у сандары берілсін. функциясының нұсқаулар жүйесін тауып, оны х-ке қолданайық. Егер есептеу процесі аяқталса, онда жауап ретінде 0 санын берейік. Черч тезисі бойынша, бұл - қандай да бір рекурсивті f(х,у) рекурсивті функциясының нұсқаулар жиыны. z осы функцияның нөмірі болсын. Яғни, f(х,у) = (х,у). s-m-n теорема бойынша f(х,у)= (х,у)= болатын f(z ,х) функция табылады. z тұрақты сан болғандықтан, f(z ,х) =f (х) теңдігі орындалатын f (х) функциясын қарастыруымызға болады. Сонымен, (у) тұрақты мәні нөлге тең функция болуы үшін (х) анықталған болуы қажет және жеткілікті.  
Енді кері жорып, алгоритм бар дейік. Яғни,  
егер -тің мәндер жиыны ақырлы болса, онда g(х)= 1,  
кері жағдайда g(х)=0  
болатын g рекурсивті функциясы табылсын. Онда  
(х) анықталса, онда g(f (х)) =1,  
(х) анықталмаса, онда g(f (х)) =0.  
Салдарға қарама-қайшылық. Себебі, салдар бойынша табылмайтын функция -gf .  
Теорема 6.11 Берілген тұрақты у саны мен кез келген х саны бойынша у саны функциясының мәндер жиынында жататынын немесе жатпайтынын анықтайтын алгоритм жоқ.  
Дәлелдеуі. у саны берілсін және  
егер у саны -тің мәндер жиынында жатса, онда f(х)=1,  
кері жағдайда f(х)=0  
болсын. Егер f рекурсивті функция болса, онда f деп теорема 14-те анықталған функцияны алып,  
(х) анықталса, онда f(f (х)) =1,  
(х) анықталмаса, онда g(f (х)) =0  
болатынын көру қиын емес.  
Теорема 6.12 Берілген тұрақты х саны мен кез келген у саны бойынша у саны функциясының мәндер жиынында жататынын немесе жатпайтынын анықтайтын алгоритмнің бар болуы х санына байланысты.  
Дәлелдеуі. х санын (у) = у болатындай етіп таңдап алайық. функциясы у-тің кез келген мәнінде анықталатындықтан, іздеп отырған функциямызды f(х)=1 деп алуымызға болады. Бұл - алгоритмнің табылатын жағдайы.  
Енді алгоритм табылмайтын жағдайды көрсетейік. (х) мәнін анықтау үшін функциясының нұсқаулар жиынын тауып, оны х-ке пайдаланайық. Егер мәні анықталса, онда (х)= х дейік. -дің рекурсивті екендігі түсінікті. Және  
(х) анықталса, онда (х)=х  
(х) анықталмаса, онда (х) те анықталмайды.  
х - осы функцияның нөмірі, яғни, болсын. Кез келген у саны бойынша у саны функциясының мәндер жиынында жататынын немесе жатпайтынын анықтайтын алгоритмнің жоқ екенін көрсетейік. Дәлелдеу үшін кері жориық.  
у саны -тің мәндер жиынында жатса, онда f(у)=1,  
у саны -тің мәндер жиынында жатпаса, онда f(у)=0  
болатын f функциясы табылсын. Осы жерден  
(х) анықталса, онда (х)= (х) =х, Яғни, х саны функциясының мәндер жиынында жатады, сондықтан f(х)=1;  
(х) анықталмаса, онда (х)= (х) те анықталмайды, ал функциясы басқа аргументте х-ке тең болмайтынын ескерсек, онда х саны функциясының мәндер жиынында жатпайтынын көреміз, сондықтан f(х)=0.  
(х) анықталса, онда f(х)=1;  
(х) анықталмаса, онда f(х)=0.  
Салдарға қарама-қайшылық.