АЛГОРИТМДЕР ТЕОРИЯСЫНА КІРІСПЕ - Математика - Қазақша рефераттар!!! - WwW.Sabakka.Ucoz.Kz - Қазақша рефераттар,курстық және дипломдық жұмыстар т.б

Басты бет » Қазақша рефераттар!!! » Математика

АЛГОРИТМДЕР ТЕОРИЯСЫНА КІРІСПЕ



АЛГОРИТМДЕР ТЕОРИЯСЫНА КІРІСПЕ

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

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

Жаттығулар

Келесі ережелерді алгоритм деп есептеуге болады ма?
1.    Бізге n саны берілсін. (n) мәнін есептеу үшін монетаны лақтырамыз. Егер елтаңба бар жағы жоғары қараса, онда (n) = 1; ал егер елтаңба бар жағы төмен қараса, онда (n) = 0.
2.    Егер  санының ондық бөлшек түрде жазуында қатар тұрған дәл 2n бірлік болса, онда (n) = 1; кері жағдайда (n) = 0.
3.    Егер  санының ондық бөлшек түрде жазуында қатар тұрған дәл 2n бірлік болса, онда (n) = 1; кері жағдайда (n) анықталмаған.
4.    Бізге n саны берілсін. Егер (n) мәнін бұрын есептелмеген болсақ, онда біз отырған бөлмеде адам саны тақ болса, (n) = 1 дейміз; кері жағдайда (n) = 1 және (n) мәнін бұрын есептелген деп санаймыз. Ал егер (n) бұрын есептелген болса, онда бұрынғы мәнін береміз.
5.    Егер  санының ондық бөлшек түрде жазуында қатар тұрған кем дегенде n бірлік болса, онда (n) = 0; кері жағдайда (n)=1.

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

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

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

Әрине, алгоритмнің кез келген формализациясын алгоритмнің дәл анықтамасы екенін дәлелдеу мүмкін емес. Оны не қабылдауға, не қабылдамауға болады. Тьюрингтен бөлек математиктер де есептеуге болатын функциялардың анықтамаларын берді. Дегенімен, олардың барлығы Тьюринг анықтамасымен эквивалент болып шықты. Есімізге Клини, Пост, Марковтардың анықтауларын алсақ та жеткілікті. Сондықтан, осы формализациялардың кез келгенін алгоритмнің дәл анықтамасы ретінде алуға болады деп есептелінеді. Бұл ойды Черч айтқан болатын. Сонымен, өзара эквивалент екі сөйлемді келтірейін.
Черч тезисі. Есептеуге болатын функциялар жиыны Тьюринг машинасында есептелінетін функциялар жиынына тең.
Черч тезисі. Алгоритмі бар функцияны есептейтін Тьюринг машинасы бар.
Бұл эквивалент екі тезистің ешқайсысын дәлелдеу мүмкін емес. Себебі, ол үшін алгоритмнің дәл анықтамасы карек. Бұл тезиске келіспеген математиктердің Тьюринг машинасы есептемейтін алгоритм табуға тырысқан еңбектерінен ештеңе шықпады. Сондықтан, қазіргі заманда Черч тезисімен келіспеген математиктер қалмады деуге болады.
Кейбір Тьюринг машиналары кейбір мәндерінде тоқтамауын байқау қиын емес. Сондықтан, Тьюринг машинасымен есептелетін функцияларды кейде жартылай рекурсивті функция деп атайды, кейде рекурсивті функция деп атайды.
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 айнымалысы бар рекурсивті функциялар жиынын белгілейік.

Жаттығулар.
  бұйрығының нөмірін табыңыздар.
12 - қандай бұйрықтың нөмірі?
Тьюринг машинасы { ,  } командалар арқылы берілсін. Oсы машинаның бұйрықтар саны екіге тең Тьюринг машиналарының жиынындағы нөмірін табыңыз.
Үшінші есептегі Тьюринг машинасының гедельдік нөмірі неге тең?

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

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

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

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

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

Берілген  х,у  сандары бойынша    есептелетіндігін анықтайтын алгоритм табылады ма деген сұраққа жауап іздейік. Чёрч тезисі пайдалансақ, онда бұл сұрақты келесі дәлірек түрде беруге болады.   есептелсе, 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.
Салдарға қарама-қайшылық.

Жаттығулар
1.    Кез келген х пен у  үшін   теңдігін тексеретін алгоритм бар ма?
2.    Кез келген х,у,z  үшін   теңдігін тексеретін алгоритм бар ма?
3.    Кез келген х  үшін   функциясының анықталу облысының бос жиын болатындығын не болмайтындығын анықтайтын алгоритм бар ма?
4.    Кез келген х  үшін   функциясының анықталу облысының ақырлылығын  анықтайтын алгоритм бар ма?
5.    Берілген тұрақты х  мен кез келген у үшін   теңдігін тексеретін алгоритм бар ма?


6.6 Рекурсивті және рекурсивті  есептелімді жиындар

Анықтама.      болғанда  ;
                           болғанда  
шартын қанағаттындыратын    функциясын А жиынының характеристикалық функциясы деп атаймыз.
Анықтама.  Характеристикалық функциясы жалпы рекурсивті болатын жиынды рекурсивті жиын деп атаймыз.
Былайша айтқанда, рекурсивті функциялар үшін кез келген элементтің осы жиынға тиістілігін анықтайтын алгоритм болу керек.
Мысалы,  жұп сандар жиыны – рекурсивті жиын. Бос жиын мен барлық натурал сандар жиынының рекурсивті екенін байқау қиын емес. Ал {х |   анықталған}  жиыны тоқтау мәселесі бойынша рекурсивті жиын емес.
Егер А жиыны рекурсивті болса, онда осы жиынның толықтауышы  N \ A да Черч тезисі бойынша рекурсивті. Шынында  да  .
Анықтама. Бос жиын немесе жалпы рекурсивті функцияның мәндер жиыны болатын А жиынын рекурсивті есептелімді жиын деп атаймыз.
Теорема 6.13 Кез келген рекурсивті жиын рекурсивті есептелімді болады.
Дәлелдеуі. ¶ш жағдай болуы мүмкін.
1)  А  - бос   жиын. Бұл жағдайда А жиыны анықтама бойынша рекурсивті есептелімді.
2) А  - бос емес ақырлы жиын. Мысалы, А  болсын. Онда
  болған кезде  =
  болған кезде  
шартын қанағаттындыратын   функциясын қарастырайық. Бұл функция Черч тезисі бойынша рекурсивті. Және кез келген мәнінде анықталғандықтан, жалпы рекурсивті функция. Оған қоса А жиыны   функциясының мәндер жиыны екені түсінікті.
    і) А ақырсыз жиын болсын, ал   А жиынының характеристикалық функциясы болсын.
  арқылы   шартын қанағаттандыратын ең кіші    -ті белгілейік,
  арқылы   шартын қанағаттандыратын      -тен үлкен ең кіші  -ті белгілейік.
Черч тезисі бойынша   функциясы рекурсивті. А жиыны ақырсыз болғандықтан, бұл функция кез келген аргументінде анықталған. Сонымен,   - жалпы рекурсивті функция. А жиыны   функциясының мәндер жиыны екенін байқау қиын емес. Теорема дәлелденді.
Теорема 6.14   жиыны рекурсивті болу үшін А мен N\А жиындары рекурсивті есептелімді болулары қажет және жеткілікті.
Қажеттілігі. А жиыны рекурсивті болғандықтан, N\А жиыны да рекурсивті. Теорема 17 бойынша жоғарыдағы жиындар рекурсивті есептелімді.
Жеткіліктілігі. Егер А мен N\А жиындарының біреуі бос болса, онда А жиынының рекурсивті екендігі түсінікті. Енді осы жиындардың екеуі де бос болмасын. Онда А мен N\А жиындары мәндерінің жиыны болатын сәйкес   пен   функциялары табылады. Біз кезекпен   мәндерін есептейміз. А жиынына тиісті сандар, А жиыны   функциясының мәндерінің жиыны болғандықтан, тақ қадамда шартты түрде кездесуі керек. Тура сол сияқты N\А жиынына тиісті х санына   шартын қанағаттындыратын   саны табылатындықтан, бұл сан жұп қадамда кездеседі. Сонымен, кез келген сан жоғарыдағы тізімде кездеседі. Тақ қадамда кездессе, онда ол А жиынына тиісті; жұп қадамда кездессе, онда оның толықтауышына тиісті.   функциялары жалпы рекурсивті болғандықтан, А жиынына тиістілігін анықтау алгоритм болады. Дәлелдеуіміз керегі де осы еді.

Жаттығулар
1)    Жәй сандар жиынының рекурсивті екенін дәлелдеңіздер.
2)      анықталған  жиынының рекурсивті есептелімді екенін көрсетіңіздер.
3)      анықталған  жиыны рекурсивті бола ма?
4)      жиыны рекурсивті бола ма?
5)    {х |   санының ақырсыз ондық бөлшек түріндегі жазуында қатар кем дегенде   алтылық бар} жиыны рекурсивті бола ма, рекурсивті есептелімді бола ма?

Санат: Математика | Салған: Maxo | Уақыты: 19-12-2010, 13:05
Көрулер: 6610 | Жүктелді: 450 | Рейтингі: 3.4/5
Барлық түсініктер: 0
Түсініктерді тек сайтқа тіркелгендер ғана қоса алады!
[ Тіркелу | Кіру ]
Жоғары