Алгоритмдер теориясы
strong>і. Нөмірлер саны саналымды болғандықтан, функция нөмірлері кем дегенде саналымды екенін көрсетсек жеткілікті. Берілген рекурсивті функцияның нұсқауларындағы ішкі жағдайлардың ең үлкені 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(х,у)= =![]()
|
