MühaziRƏ 1 Verilənlər. Alqoritmlər və verilənlərin strukturu

Minimallaşdırma operatoru

P(x_1, x_2, ...,x_n) münasibəti o vaxt primitiv-rekursiv adlanır ki,əgər onun xarakterik funksiyası primitiv-rekursivdir:

0 əgər P(x_1, x_2, ...,x_n) - “səhv”

Χ(x_1, x_2, ...,x_n)=

1 əgər P(x_1, x_2, ...,x_n) -“doğru”

Predikat o vaxt primitiv rekursiv olur ki,əgər onun xarakterik funksiyası primitiv-rekursivdir. f (x_1, x_2, ...,x_n) funksiyası P(x_1, x_2, ...,x_n,z) ,predikatından minimallaşdırma operatorunun köməyilə alınır,əgər f (x_1, x_2, ...,x_n) funksiyasının istənilən qiymətində z minimal qiyməti olursa,onda P(x_1, x_2, ...,x_n,z) predikatı “doğruya” çevrilir:
f (x_1, x_2, ...,x_n) = μ_z (P(x_1, x_2, ...,x_n,z)),
haradaki, μ_z-minimallaşdırma operatorudur.

Minimallaşmanın məhdudiyyət operatoru

P(x_1, x_2, ...,x_n,z) predikatından və U (x_1, x_2, ...,x_n) funksiyasından minimallaşmanın məhdudiyyət operatoru o zaman alınır ki,istənilən nöqtədə bu funksiyanın qiyməti aşağıdakı kimi təyin olunsun:

1) ixtiyari z< U (x_1, x_2, ...,x_n) üçün P(x_1, x_2, ...,x_n,z) = “doğru”dur və funksiyanın qiyməti

2)qeyri-ixtiyari z< U (x_1, x_2, ...,x_n) üçün P(x_1, x_2, ...,x_n,z) = “doğru”dursa,funksiyanın qiyməti f (x_1, x_2, ...,x_n) = U (x_1, x_2, ...,x_n).

Bu aşağıdakı kimi yazılır:

f (x_1, x_2, ...,x_n) = μ_z(P(x_1, x_2, ...,x_n,z))

z məhdudiyyəti minimallaşmanın məhdudiyyət operatorunda hesablamaların sona çatması üçün zəmanət verir və P predikatların sayını göstərir.Hesablamaların sayının göstərilməsi imkanı primitiv- rekursiv funksiyanın əsas xüsusiyyətidir.

Primitiv- rekursiv funksiyalar

Hesablanan funksiyaların çoxu primitiv- rekursiv funksiyalar sinfinə aiddir.

Funksiya o vaxt primitiv- rekursiv adlanır ki,superpozisiya və primitiv-rekursiya operatorlarının son qiymətinin köməyilə sadə funksiyalardan alınsın.Əgər bəzi funksiyalar primitiv-rekursivdirsə,onda onlara superpozisiya və ya primitiv -rekursiv operatorlarını tətbiq etməklə yeni primitiv- rekursiv funksiyalar almaq olar.

Funksiyanın primitiv- rekursiv olmasını 3 cür isbat etmək olar:

1) Verilmiş funksiyanın sadə olduğunu sübut etməklə;

2) Verilmiş funksiyanın superpozisiya operatoru köməyilə qurulduğunu sübut etməklə;

3) Verilmiş funksiyanın primitiv- rekursiya operatoru köməyilə qurulduğunu sübut etməklə;

Bununla belə primitiv- rekursiv funksiyalar bütün hesablanan funksiyaları (hansılar ki,konstruktiv təyin oluna bilər) əhatə etmir.