Formal diLLƏr və avtomatlar nəZƏRİYYƏSİ

2.2. Sadə funksiyalar anlayışı
Qiyməti hər hansı alqoritm vasitəsilə təyin edilən funksiyalar hesablanan funksiyalar adlanır.Rekursiv təyinlər vasitəsilə funksiyaları təsvir etmək üçün sadə funksiyalara baxaq:

1. 
   Z(x₁,x₂,...,x_n)=0 – arqumentin mənfi olmayan bütün qiymətləri üçün təyin olunan sıfır funksiya;
   
2. 
   S(x)=x+1 – öz arqumentinin mənfi olmayan tam qiymətləri üçün təyin olunan funksiya;
   
3. 
   Iⁿ_m(x₁,x₂,...,x_m ,...,x_n )= x_m – öz arqumentinin qiymətlərini təkrar edən seçim(bərabərlik) funksiyası.
   

Sadə funksiyaları ilkin funksiyalar kimi istifadə edərək bir neçə ümumi konstruktiv üsulların köməyi ilə mürəkkəb hesabi funksiyalar qurmaq olar.Rekursiv funksiyalar nəzəriyyəsində əsa yeri üç əməliyyat tutur:superpozisiya,primitiv rekursiya və minimallaşdırma
2.2.1.Superpozisiya operatoru
S superpozisiyasınım operatoru m dəyişənli m funksiyasını n dəyişənli ilə əvəz edilməsi adlandırılır.Bu zaman n dəyişənli yeni funksiya əmələ gəlir.Məsələn,

f1 (x_1, x_2, ...,x_n ), f2 (x_1, x_2, ...,x_n),..., fm (x_1, x_2, ...,x_n ) funksiyasından aşağıdakı yeni funksiyanı almaq olar:

S^m+1(f,f1,f2,...,fm)=g( x_1, x_2, ...,x_n)=f(f1(x_1, x_2, ...,x_n ), f2(x_1, x_2, ...,x_n),..., fm(x_1, x_2, ...,x_n )) (1)

S^m+1 superpozisiya əməliyyatı zamanı yuxarıdakı indeks funksiyanın sayını göstərir.Beləliklə,superpozisiya operatoru və seçmə funksiyası vasitəsilə funksiyanın funksiya ilə istənilən əvəzedilməsini göstərmək olar.Məs.f(x)=0 və g(x)=x+1 funksiyalarında superpozisiya əməliyyatı apararaq ,aşağıdakı funksiyanı alarıq:

h(x) = g(f(x))= 0+1=1.

Bu funksiya ilə g(x) funksiyasının superpozisiyası zamanı aşağıdakı funksiyanı alarıq:

h(x)=g(g(x))=x+2

Bərabərlik funksiyasından və əvəzetmədən istifadə edərək, arqumentləri funksiyada yerdəyişmək olar.

f(x₂, x₁, x₃, . . ., x_n) = f(I²₂(x₁, x₂), I¹₂(x₁, x₂), x₃, . . ., x_n);
f(x₁, x₁, x₃, . . ., x_n) = f(I¹₂(x₁, x₂), I¹₂(x₁, x₂), x₃, . . ., x_n).

Beləliklə,əgər bərabərlik funksiyası və superpozisiya operatoru verilibsə,onda hesab etmək olar ki,funksiyanın funksiya ilə əvəz edilməsinin bütün mümkün operatorları, həm də dəyişənlərin ad dəyişməsi, yerdəyişməsi və oxşarlığı verilmişdir.

2.2.2.Primitiv rekursiya operatoru
Rn primitiv rekursiya operatoru - (n+1)-i f funksiyasının iki verilmiş funksiyalar vasitəsilə təyin etməyə imkan verir:onlardan biri g funksiyasının n-i,digəri isə h funksiyasının (n+2)-i.

f (x_1, x_2, ...,x_n ,y ) funksiyası primitiv rekursiya operatoru ilə aşağıdakı funksiyadan alınır

g(x_1, x_2, ...,x_n) və h(x_1, x_2, ...,x_n,y,z) funksiyası,əgər: