Hesablanan funksiyalar
Tyurinq maşını f(x1,x2,...,xn) funksiyasını aşağıdakı şərtlər daxilində hesablayır:
1)Funksiyanın təyinetmə oblastına daxil olan istənilən x1,x2,...,xn üçün Tyurinq maşını başlanğıc konfiqurasiyadan (lentdə arqumenti təsvir edilir), son konfiqurasiyaya keçir(lentdə nəticə təsvir olunur).
2)Funksiyanın təyinetmə oblastına daxil olmayan istənilən x1,x2,...,xn üçün Tyurinq maşını başlanğıc konfiqurasiyadan sonsuz olaraq işləyir.
Əgər Tyurinq maşınının başlanğıc və son konfiqurasiyası standartdırsa, onda Tyurinq maşını f funksiyasını düzgün hesablayır.
Funksiya o zaman Tyurinq maşınına görə hesablanan sayılır ki,onu hesablayan Tyurinq maşını olsun.
Tyurinq maşını funksiyanı bərpa etməklə və ya bərpa etməməklə hesablaya bilər.Bərpa edilməklə funksiyanın hesablanması zamanı Tyurinq maşını ilkin verilənləri yadda saxlamaqla işləyir.
p0 1X1* . . * 1Xn⇒* p z 1f(X1, X2, . . . , Xn) *1X1* . . * 1Xn.
Verilmiş tərifdən istifadə etməklə lentdə əvvəl nəticə,sonar isə ilkin verilənləri almaq olar.Ayrı-ayrı hallarda isə əksinə eləmək daha uyğun olar
p0 1X1* . . * 1Xn⇒*1X1* . . * 1Xn * p z 1f(X1, X2, . . . , Xn)
Bərpa edilməməklə funksiyanın hesablanması Tyurinq maşınının işində ilkin verilənlərin yadda saxlanılmamasını göstərir
p0 1X1* . . * 1Xn⇒* p z 1f(X1, X2, . . . , Xn)
Dostları ilə paylaş: |