Алгоритмдер теориясы
ht="25" src="file:///C:/Users/E786%7E1/AppData/Local/Temp/msohtml1/01/clip_image184.gif" width="24" />(х,у)= болатын 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
| 
