Есептелінетін функция ұғымы. Бөлікті функциялардың суперпозициясы

1. 
   Есептелінетін функция ұғымы.
   
2. 
   Бөлікті функциялардың суперпозициясы.
   
3. 
   Примитивті рекурсиялы функциялар. Негізгі қасиеттері.
   
4. 
   Ауыстыру амалының негізгі қасиеттері.
   

1. 
   Есептелінетін функция ұғымы.
   

Рекурсивті функия ұғымына сүйеніп алгоритм ұғымын нақты анықтамасын құрудың бастапқы идеясы мынада жатыр: кез-келген берілгендерді (әрине дискретті) қандай-да бір санау жүйесінде натурал сандармен кодтауға болады, және сонда оларды кез-келген жолмен түрлендіру - есептеу операцияларының тізбегіне келтіріледі, ал өңдеу нәтижесі де сол сияқты бүтін санды

Бұл жағдайда осы сандық функцияға бірдей кез-келген алгоритм оның мәнін есептейді, ал оның элементар қадамдары кәдімгі арифметикалық және логикалық амалдар болып табылады. Мұндай функциялар есептелінетін функциялар деп аталады.

Айталық Пусть y(x1, x2, …, xn), типті функциялар класы берілсін, олардың ерекшеліктері функцияның барлық аргументтерінің x1,…, xn бүтінсандылығы және функция мәні у-те бүтін сан арқылы өрнектеледі. Басқаша айтқанда аргументтері мен мәндері дискретті болып табылатын функциялар қарастырылады.

y(x1, x2, …, xn) функциясы тиімді есептелінетін деп аталады, егер оның мәнін аргументтердің белгілі мәндері бойынша есептеуге мүмкіндік беретін алгоритм бар болса.

Бұл анықтамада алгоритм ұғымы интуитивті түрде алынғандықтан, тиімді есептелінетін функция ұғымы да интуитвті болып табылады. Сонда да алгоритмдерден есептелінетін функцияларға өту барысында да бір мағызды жағдай туындайды. Алдыңғы тақырыптарда қарастырған алгоритмнің интуитивті ұғымына сәйкес келетін, 1-5 шарттарды қанағаттандыратын процесстер жиынтығы барынша кең және анық көрінбейді. Керісінше, келтірілген шарттарды қанағакттандыратын, процесстердің әртүрлі түсініктері үшін есептелінетін функциялар бірдей болып табылды және әдеттегі математикалық терминдермен оңай сипатталады. Барлық есептелінетін функциялар жиынтығымен беттесетін, дәл сипатталған сандық функциялар жиынтығы осы кезге дейін белгілі алгоритмнің кең ұғымында рекурсивті функциялар жиынтығы деп аталады.

Кез-келген алгоритмдік модель, оның ішінде рекурсивті функциялар, алгоритмнің қарапайым қадамдарын анықтауды және олардан мәліметтерді өңдеудің қажетті тізбегін қамтамасыз ететін қандай-да бір түрлендірулер тізбегін құру тәсілдерін қарастыруы керек. Рекурсивті модельде мұндай «элементар қадамдар» болып S1, 0n және Imn қарапайым функциялар деп аталатын функциялар табылады. Олардың комбинацияларының көмегімен олардан да күрделірек функциялар құрылады және олар келесідей анықталады:

• S1(x) = x+1 – тікелей ілесудің бірорынды (яғни, бір аргументі бар) функциясы.

  
  

• 0n(x1,x2,…,xn) = 0 – бұл нольге теңдікке ұқсастық n-орынды функциясы.

  
  

• Imn(x1,…,xn) = xm (1 m n; n=1,2,…) – өзінің аргументтерінің бірінің мәнін ұқсас (тождественного повторения) қайталайтын n-орынды функция.

  
  

Аталған қарапайым функциялар барлық жерде анықталған және интуитвті есептелінеді. Олардың үстінен амалдар анықталған (ары қарай оларды операторлар деп атаймыз). Бұл амалдарды интуитвті есептелінетін функцияларға қолданатын болсақ, итуитивті есептелінетін жаңа функцияларды туындататын қасиеттерге ие. Осы операторлардың көмегімен қарапайым функциялардан алынатын бөлікті функцияларды бөлікті рекурсивті функциялар деп атаймыз. Черч гипотезасының мағынасы мынадай: осылайша құрылған бөлікті рекурсивті функциялар класы алгоримтдік есептелінуі мүмкін функциялар класымен беттеседі.

Қарапайым функциялардың түрленуін қамтамасыз ететін операторларды қарастырамыз: Бөлікті функциялардың суперпозициясы

Айталық, m-орынды функциялар

f1(x1,…, xm), f2 (x1,…, xm),…, fn(x1,…, xm)

n-орынды g(x1,…, xn) функциялардың астына қойылсын. Нәтижесінде n-орынды функция алынады

h(x1,…, xn)=g(f1(x1, …, xm),…, fn(x1,…, xm))

Осы жерде h функциясы g, f1, …, fn функцияларынан суперпозициямен (немесеастына қоюмен) алынды деп айтылады. Символды түрде мұндай астына қою келесідей белгіленеді: Sn+1(g,f1,…,fn), мұндағы жоғарғы индекс аргумент ретінде қойылатын функция санын бейнелейді.

Егер біз g, f1, …, fn функциясын есептей алсақ, онда h функциясы да есептелінеді. Осылайша g, f1, …, fn функциялары барлық жерде анықталған болса, онда h функциясы да барлық жерде анықталған. Осылайша егер g, f1, …, fn функциясы итуитивті есептелінетін болса, онда h функциясы да интуитивті есептелінеді.

2. 
   Бөлікті функциялардың суперпозициясы.
   

Қарапайым функциялардың түрленуін қамтамасыз ететін операторларды қарастырамыз: Бөлікті функциялардың суперпозициясы

Айталық, m-орынды функциялар

f1(x1,…, xm), f2 (x1,…, xm),…, fn(x1,…, xm)

n-орынды g(x1,…, xn) функциялардың астына қойылсын. Нәтижесінде n-орынды функция алынады

h(x1,…, xn)=g(f1(x1, …, xm),…, fn(x1,…, xm))

Осы жерде h функциясы g, f1, …, fn функцияларынан суперпозициямен (немесеастына қоюмен) алынды деп айтылады. Символды түрде мұндай астына қою келесідей белгіленеді: Sn+1(g,f1,…,fn), мұндағы жоғарғы индекс аргумент ретінде қойылатын функция санын бейнелейді.

Егер біз g, f1, …, fn функциясын есептей алсақ, онда h функциясы да есептелінеді. Осылайша g, f1, …, fn функциялары барлық жерде анықталған болса, онда h функциясы да барлық жерде анықталған. Осылайша егер g, f1, …, fn функциясы итуитивті есептелінетін болса, онда h функциясы да интуитивті есептелінеді

3. 
   Примитивті рекурсиялы функциялар. Негізгі қасиеттері