Клинидің формалдау жолы. Жай функциялар. Суперпозиция және примитивті рекурсия функциялар класы. Қосу, шекті минимальдау, мажорлы қайталау операторлары.
Алгоритм ұғымын тұрпаттандыру мәселесіне барар тағы бір жол, ол-рекурсивті функциялар. Тарихи бұл жол ең бірінші пайда болды, сондықтан да алгоритмдерге арналған математикалық зертеулерде ол кең таралған.
Рекурсия дегеніміз, аргументердің белгілі бір мәнінде функцияның мәні функцияның бұған дейін аргументердің өзге мәндерінде берілген мәндері арқылы өрнектелетін функцияның берілу тәсілі. Алгоритмдер теориясында рекурсивті функцияларды қолдану кез келген әріппедегі сөздерді натурал сандар тізбегі арқылы нөмірлеу идеясына негізделген. Осылайша, кез келген алгоритмді аргументтерінің бүтінсандық мәндеріндегі кейбір бүтінсандық функцияның мәндерін есептеуге келтіруге болады.
Бірнеше негізгі ұғымдарды енгізейік. Х,У-екі жиын болсын. Х-тан У-ке ішінара функция (бейнелеуі) деп, 
-тің (анықталу облысы аталатын) іш жиынынан және 
бейнелеуінен тұратын
Егер D(f) бос болса, онда f ешжерде анықталмаған. Ешжерде анықталмаған бір ғана ішінара функция бар деп есептейік.
N арқылы натурал сандар жиынын белгілейміз.( N)n (n >1) арқылы N-нің өзіне n-еселі декарттық көбейтіндісін, яғни реттелген n-діктердің 
жиынын белгілейміз. Алдағы құрастырулардың негізгі нысаны, әртүрлі m, n үшін (N)m- нен (N)n-ге ішінара функциялары болады.
Егер 
кіріс жиынтығы үшін
болғанда шығыста f (х) –ты, ал 
болғанда нөл беретін алгоритмді (программаны) көрсетуге болатын болса, онда (N)m - нен (N)n-ге ішінара функциясы f есептелгіш деп аталады. Бұл анықтамада алгоритмнің (программаның) бейтұрпат ұғымы функцияның есептелгіштік ұғымымен байланысқан (теңдестірілген) болып шығады. Бұдан әрі алгоритмдер орнына есептелгіш функциялардың қасиеттері зерттелетін болады. Есептелгіш функциялар орнына одан әлдеқайда кең функциялар класын (әлдеқайда әлсіз анықтама)- жартылай есептелгіш функциялар класын пайдалану қажет екен.
Егер кіріс 
жиынтығы үшін шығыста 
беретін немесе болғанда алгоритм белгісіз ұзақ жұмыс істейтін алгоритмді (прорамманы) көрсетуге болатын болса (N)m - нен (N)n-ге ішінара функциясы жартылай есептелгіш болады. Есептелгіш функциялардың жартылай есептелгіш, ал барлық жерде анықталған жартылай есептелгіш функциялардың есептелгіш екендігін анық.
f ішінара функциясы бейесептелгіш аталады, егер ол есептелгіш те жартылай есептелгіш те болмаса.
Жаңадан енгізілген ұғымдар ішінде негізгісі жартылай есептелгіштік болып табылады, себебі есептелгіштік соған келтіріледі. Бейесептелгіш функциялар да жартылай есептелгіш, бірақ есептелгіш емес функциялар да бар. Ондай функцияға мысал:
теңдеуінің шешімі болса,
q(t) –бейесептелгіш болатындай бүтін коэфицентті Р(t,х1,...,х n) көпмүшесінің табылатындығын көрсетуге болады. Дегенмен, q(t) - жартылай есептелгіш екендігін тез-ақ аңғаруға болады. Есептелгіштік теориясының іргелі жаңалығының бірі -Черч тезисі. Оның ең әлсіз түрі мынандай: а) ең қарапайым жартесептегіш функциялар жиынтығын; б) кез келген жартесептегіш функция, әр қадамы элементар амалдардың бірін бұрын құрылған немесе өте қарапайым функцияларға қолданыстан тұратын қадамдардың шектеулі санынан кейін алынатындай қасиеті бар, бір жартесептегіш функциялар бойынша екінші жартесептегіш функцияларды құруға мүмкіндік беретін элементар амалдар жиынтығын-көрсетуге болады.
Ең қарапайым функциялар:
Suc: 
; suc(х)=x+1 х-тан кейінгі санды анықтау;
; 
(х1,...,хn)=1, 
функцияның анықтау облысының “өлшемдігін” анықтау;
; 
(х1,...,хn)=х1 ; 
анықталу облысының айнымалылардың біріне “проекциясы”.
Ішінара функцияларға элементар амалдар:
а) композиция (немесе алмастыру) (N)m –нен (N)n-ге f және (N)n-нен (N)p-ға g функциялар жұбына (N)m – нен (N)p – ға h = g ° f функциясын сәйкес қояды. Ол былай болатындай анықталады:
D (g°f)=f-1(D(g))={x(N)m x D (f), f(x)D(g)} (g°f)(x)=g(f(x));
б) біріктіру fі(N)nі-ден, і=1,…,k, ішінара функцияларына (N)m –нен (N)n1 x...x(N)nk-ға (f1,.., fk)функциясын сәйкестіндіреді, ал ол функция
D((f1,…,fk))=D(f1)Ç... ÇD(fk),
(f1,…,fk)(x1,...,xm)=
в) рекурсия (N)n®N- ге f және (N)n+2®N-ге g функциялар жұбына(N)n+2®N-ге h функциясын сәйкестендіреді,ал ол соңғы аргумент бойынша
h(x1,…,xn,1)=f(x1,…,xn) (бастапқы шарт),
h(x1,…,xn,k+1)=g(x1,…,xn,k,h(x1,…,xn,k)),k³1 жағдайда (рекурсиялық қадам) рекурсиясымен анықталады.
D(h) анықталу облысы да рекурсивті өрнектеледі:
г) m амалы (N)n+1®N-ге f ішінара функциясына (N)n®N –ге h ішінара функциясын сәйкестендіреді, ал ол былай анықталады:
D (h)={
xn+1³1,
f(x1,…,xn,,xn+1)=1 және 
,
h(x1,…,xn)=mіn{xn+1f(x1,…,xn+1)=1}.
m амалы есептеулерге ақырсыз жиынтықтан қажеттіні іздеу үшін нысандарды іріктеуді енгізуге мүмкіндік береді.
Енді, ең қарапайым функциялар мен элементар амалдар енгізілген соң мынадай негізгі анықтамаларды беруге болады:
а) f1,…, fN ішінара функцияларының тізбегін fN=f функциясының ішінара рекурсивті (сәйкес анайы рекурсивті) сипаттамасы деп атайды, егер f1-ең қарапайым функциялардың бірі болса; fі"і ³ 2 не ең қарапайым функция, не f1,..., fі-1 функцияларының кейбіріне (сәйкес m-нен басқа элементар амалдардың біріне) элементар амалдардың бірін қолдану арқылы алынатын болса;
б) f функциясы ішінара рекурсивті (сәйкес анайы рекурсивті) деп аталады, егер оны ішінара рекурсивті (сәйкес анайы рекурсивті) сипаттауға болатын болса.
Енді Черч тезисін кәдімгі түрде келтіруге болады:
а) f функциясы жартесептегіш, егер және тек қана егер ол ішінара рекурсивті болса;
б) f функциясы есептегіш, егер және тек қана егер f пен c D(f) - сипаттамалық функциялары рекурсивті болса.
ХÌУ ішжинының сипаттамалық функциясы болай болады:
Черч тезисін алгоритмдік шешілмеудің анықтамасы ретінде пайдалануға болады. “Ия”, “жоқ” деген жауабы бар P1,P2,...”есептерінің” санақты тізбегі бар болсын. Мұндай тізбек “жаппай мәселе” деп аталады. Онымен N®N-ге f функциясын байланыстырайық:
D(f)-{і| Pі “ия” жауабы бар };
f (і)=1, егер іÎD(f) болса.
Р жаппай мәселесі алгоритмдік шешіледі дейміз, егер f пен ZD(f) функциялары ішінара рекурсивті болса. Керісінше жағдайда Р алгоритмдік шешімсіз дейміз.