Алгоритмдер теориясы
86%7E1/AppData/Local/Temp/msohtml1/01/clip_image104.gif" width="55" /> төрттіктеріне <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Кез келген рекурсивті функцияның саналымды нөмірі бар.
Дәлелдеу<
| |  скачать работу |
Алгоритмдер теориясы | 
