Лекция Черч тезисінің салдарлары
жүктеу/скачать 41,23 Kb.
|
14 - Лекция
ЛекцияЧерч тезисінің салдарларыЕнді Черч тезисінен шығатын бірнеше теоремаларға тоқтай кетейік. Теорема 8.5. Жартылай рекурсивті функциялар жиыны саналымды. Дәлелдеуі. Черч тезисі бойынша (х) = k функциясы кез келген k үшін рекурсивті. Сондықтан, жартылай рекурсивті функциялар кем дегенде саналымды. Екінші жағынан, төртінші салдар бойынша олар саналымдыдан артық емес. Анықтама. Кез келген мәнінде анықталған жартылай рекурсивті функция жалпы рекурсивті функция деп аталады. Салдар 8.6. Жалпы рекурсивті функциялар саналымды. Дәлелдеуі. (х) = k функциясы кез келген k үшін анықталған. Сондықтан, олар кем дегенде саналымды. Екінші жағынан, жалпы рекурсивті фундциялар жиыны жартылай рекурсивті функциялар жиынының ішкі жиыны болғандықтан саналымдыдан артық емес. Біз төртінші салдарда жартылай рекурсивті функциялар жиынын нөмірлеп шыққанбыз. Ең қызығы, олардың ішкі жиыны жалпы рекурсивті функцияларды нөмірлеуге болмайды екен. Теорема 8.7. Жалпы рекурсивті функцияларды нөмірлеп шығу мүмкін емес. Дәлелдеуі. Кері жориық. Қандай да бір алгоритмді пайдаланып, жалпы рекурсивті функцияларды нөмірледік дейік, яғни оларды түріндегі тізбек арқылы тізімдеуге болады деп есептейміз. Онда біз келесі нұсқауларды пайдаланып, функциясын құрастырайық. Ізделініп отырған функциясының х нүктесіндегі мәнін есептеу үшін функциясының нұсқаулар жиынын табу керек. Осы нұсқаулар жиынын х санына пайдаланамыз. Берілген функциясы жалпы рекурсивті функция болғандықтан, қандай да бір мезетте жауап табылады. Берілген жауапқа бірді қосып жауап ретінде береміз. Черч тезисі бойынша - рекурсивті функция. Кез келген х үшін - жалпы рекурсивті функция болғандықтан, - жалпы рекурсивті функция. Олай болса, берілген тізімде болу керек. Яғни, қандай да бір үшін = . Енді ( ) неге тең екенін байқасақ, онда ол ( )+1 -ге тең болады. Онда ( )= ( )+1. Қарама - қайшылық. Теорема дәлелденді. Кейде осы көрсетілген әдісті неге жартылай рекурсивті функцияларға қолдануға болмайды деген сұрақ туады. Ізделініп отырған функциясының нөмірі болсын. Бұл жерде нөмірлі алгоритм санында есептелініп болмауы мүмкін. Онда біз функция мәніне бірді қоса алмаймыз. Теорема 8.8. Рекурсивті емес функциялар бар. Дәлелдеуі. Кантор теоремасы бойынша континиум функция бар. Яғни, рекурсивті емес функция табылады. Теорема 8.9. Кез келген рекурсивті функцияның саналымды нөмірі бар. Дәлелдеуі. Нөмірлер саны саналымды болғандықтан, функция нөмірлері кем дегенде саналымды екенін көрсетсек жеткілікті. Берілген рекурсивті функцияның нұсқауларындағы ішкі жағдайлардың ең үлкені m-нен кіші болсын. Біз берілген нұсқауларға , ,…, нұсқауларын қандай да бір k үшін қосып көрейік. Есептеу -ден басталады және есептеу кезінде , ,…, ішкі жағдайлары пайда болуы мүмкін емес. Сондықтан, алғашқы нұсқаулар жиыны қандай конфигурацияда тоқтаса, соңғы нұсқаулар жиыны да сол конфигурацияда тоқтайды. Яғни, соңғы нұсқаулар жиыны да сол рекурсивті функцияны есептейді. Бірақ, олардың нөмірлері әртүрлі. Және бұл мүмкіндік кез келген k үшін бар. Теорема дәлелденді. Теорема 8.10. Кез келген х пен у үшін: егер анықталған болса, онда = ; егер анықталмаған болса, онда -де анықталмаған z саны табылады. Дәлелдеуі. Бізге < х, у > берілсін. Нөмірі х болатын Тьюринг машинасын табамыз. Осы машинаны у-ке пайдаланамыз. Егер есептеу аяқталып, жауап берілсе, онда сол жауапты біз де жауап ретінде береміз. Сонымен, тапқан функция = анықталмаған, егер анықталмаған функциясы рекурсивті. Бұл функцияның нөмірі бар. Ол нөмірді z дейік. Яғни (х,у)= Теорема 8.11. Кез келген m,n1 үшін теңдігі орындалатын функциясы табылады. Дәлелдеуі: Черч тезисі бойынша. Бұл теореманы болашақта s-m-n теорема деп атаймыз. жүктеу/скачать 41,23 Kb. Достарыңызбен бөлісу:
|