WWW.REFERATCENTRAL.ORG.UA - Я ТУТ НАВЧАЮСЬ

... відкритий, безкоштовний архів рефератів, курсових, дипломних робіт

ГоловнаМатематика, Геометрія, Статистика → Формальні моделі алгоритмів та алгоритмічно обчислюваних функцій - Реферат

Формальні моделі алгоритмів та алгоритмічно обчислюваних функцій - Реферат

таке, що g(d уaa)=0 і для всiх k<а значення g(d уak) визначене та 0. Якщо таке a N не iснує, то f(d) .
Це означає, що кожного d VN значення f(d) обчислюється так. Послiдовно обчислюємо значення g(d уak) для k=0, 1, 2, ... Перше таке а N, що g(d уaa)=0, буде шуканим значенням f(d). При цьому для всiх k<а значення g(d уak) визначені та 0.
Процес обчислення значення My(g)(d) нiколи не закiнчиться в таких випадках:
значення g(d уa0) невизначене;
для кожного k N значення g(d уak) визначене та 0;
для всiх kx). Тому ОТ функцiї [x/у] має вигляд Mz (Su,v( , sx, Sv( yv, sz)).
Приклад 10. Функцiя [ ] є V-КЧРФ.
Маємо [ ] = z(y (z+1)>x). Тому ОТ функцiї [ ] має вигляд My (Su,v( , sx, Su,v( uv, sy, sy)).
6. ОБЧИСЛЮВАНІСТЬ п-АРНИХ ФУНКЦІЙ НА N.
Основними обчислюваними операцiями для п-арних функцiй на множині N є наступні операції: операція суперпозицiї Sn+1, операція примiтивної рекурсiї R, операція мiнiмiзацiї M.
Операцiя Sn+1 n-арнiй функцiї g(x1,...,xn) та n функцiям g1(x1,...,xт), ..., gn(x1,...,xm) одної i тої ж арностi ставить у вiдповiднiсть функцiю f(x1,...,xm) = g(g1(x1,...,xт), ..., gn(x1,...,xm)).
Таку функцiю позначають Sn+1 (g, g1, ..., gn), її арність співпадає з арнiстю функцiй g1, ..., gn.
Операцiя примiтивної рекурсiї R n-арнiй функцiї g та (n+2)-арнiй функцiї h ставить у вiдповiднiсть (n+1)-арну функцiю f, яку позначають R(g,h), що задається рекурсивним визначенням
f(x1,...,xn,0) = g(x1,...,xn)
f(x1,...,xn,y+1) = h(x1,...,xn,y, f(x1,...,xn,y))
Це означає, що для всiх значень a1,..., an, b значення f(a1,...,bn ,b) обчислюється так:
f(a1,...,an,0) = g(a1,...,an)
f(a1,...,an,1) = h(a1,...,an,0, f(a1,...,an,0))
... ... ... ... ... ... ... ... ... ... ...
f(a1,...,an ,b) = h(a1,...,an ,b-1, f(a1,...,an ,b-1))
При n=0 вважаємо, що функцiя g 1-арна константа.
Операцiя мiнiмiзацiї M кожній (n+1)-арнiй функцiї g ставить у вiдповiднiсть n-арну функцiю f, яку позначають M(g), що задається спiввiдношенням
f(x1,...,xn) = y(g(x1,...,xn,y)=0)
Це означає, що для всiх значень x1, ..., xn значення функцiї f(x1,...,xn) обчислюється так. Послiдовно обчислюємо значення g(x1,...,xn,y) для y=0, 1, 2, ... Перше таке значення y, що g(x1,...,xn,y)=0, буде шуканим значенням f(x1,...,xn). При цьому для всiх tІз визначення випливає, що процес обчислення значення y(g(x1,...,xn,y)=0) нiколи не закiнчиться в таких випадках:
значення g(x1,...,xn,0) невизначене;
для всiх значень у значення g(x1,...,xn,y) визначене та 0;
для всiх tx1) = (nsg(x2 (x3+1) )=0).
Функцiя [x1/x2] невизначена при x2=0, тому вона не РФ і не ПРФ.
Приклад 12. Функцiя f(x1) = [ ] РФ. Справді, [ ] тотальна та [ ]= ((x2+1) (x2+1)>x1)= (nsg((x2+1) (x2+1) )=0).
Розглянемо деякi елементарнi властивостi ПРФ i РФ. Для спро-щення звичайно позначатимемо xn+1 та xn+2 як у та z відповідно
Теорема 6.1. Нехай (n+1)-арна функцiя g ПРФ. Тодi (n+1)-арна функцiя f, задана умовою f(x1,...,xn, у) = , теж ПРФ.
Домовимося надалi вважати, що при zТeорeма 6.2. Нехай (n+1)-арна функцiя g ПРФ. Тодi (n+2)-арна функцiя f, задана умовою f(x1,...,xn,у,z) = , теж ПРФ.
Тeорeма 6.3. Нехай (n+1)-арна функцiя g та n-арнi функцiї i ПРФ. Тодi n-арна функцiя h, задана умовою
h(x1,...,xn)= теж ПРФ.
Теореми 6.6.1-6.6.3 називають теоремами сумування. Замiнивши в цих теоремах символ суми на символ добутку , одержимо теореми мультиплiкацiї.
Кажуть, що (п+1)-арна функцiя f отримується iз (n+1)-арної функцiї g за допомогою операцiї обмеженої мiнiмiзацiї, якщо вона задається таким спiввiдношенням:
f(x1,...,xn,у)=
Цей факт позначаємо так: f(x1, ..., xn, у) = ((g(x1, ..., xn, z)=0).
Тeорeма 6.4 (про обмeжeну мiнiмiзацiю). Нехай (n+1)-арна функцiя g є ПРФ. Тодi (n+1)-арна функцiя f, задана умовою
f(x1,...,xn, у) = ((g(x1, ..., xn, z)=0) теж ПРФ .
Наслідок. Нехай функцiї g(x1, ..., xn, у) та (x1, ..., xn) є ПРФ. Тодi функцiя f(x1, ..., xn) = ((g(x1,..., xn, у)=0) теж є ПРФ .
Приклад 13. Довизначимо функцiю f(x1, x2) = [x1/x2] таким чином: [x1/0]=x1. Тоді функцiя [x1/x2] є ПРФ. Справдi, значення [a/b] рiвне кiлькостi нулiв в послiдовностi 1 , 2 , ..., a . Тому [x1/x2] = ), звідки [x1/x2] є ПРФ за теоремою 6.6.3.
Приклад 14. Функцiя mod(x1, x2) остача вiд дiлення x1 на x2 , є ЧРФ. Справдi, mod(x1, x2) = [x1/x2]).
Зауважимо, що беручи тут довизначену функцію [x1/x2], дістане-мо довизначену функцію mod(x1, x2): mod(x1,0)=0. Така довизначена функція mod(x1, x2) є ПРФ.
Приклад 15. Функцiя f(x1) = [ ] є ПРФ.
Справдi, маємо [ ]= (nsg((x2+1) (x2+1) )=0), тому за теоремою 6.6.4 [ ] є ПРФ.
Приклад 16. Функцiя пd(x) кількість дiльників числа x , є ПРФ при довизначенні пd(0)=1. Справдi, пd(x) = .
Приклад 17. Функцiя (x) кількість простих чисел, які не більші за число x, є ПРФ. Справдi, (x) =
Приклад 18. Функцiя р(x) х-ве просте число, є ПРФ (тут р(0)=2, р(1)=3, р(2)=5 і т.д.)
Справдi, р(x)= (| (у) (x+1)|=0). Доведення того факту, що р(x) , проведемо індукцією по х. Для х=0 маємо р(0)=2 . Нехай для всіх х k маємо p(x) . Покажемо p(k+1) . Розглянемо число b=p(0) p(1) p(k)+1. За припущенням індукції р(0) , , p(k) . Тому b . Але кожний простий дільник числа b більший за p(k), тому p(k+1) b .
Приклад 19. Функцiя ex(x, y) степінь числа р(x) в числі у, є ПРФ при довизначенні ех(x, 0)=0.
Справдi, ex(x, y)= z y(nsg(mod(y, p(x)z+1)) sg(y)=0).
7. ПРОГРАМОВАНI ФУНКЦIЇ НА N
Програмна алгебра (P, K) задається парою (B, K), де множина функцій P основа алгебри, K множина композицiй (операцiй) над функцiями із P, B P множина базових функцiй [22]. Примiтивні програмні алгебри (ППА) - це програмнi алгебри функцiй з простими типами даних. До таких функцiй належать, зокрема, квазиарні, Х-арні та п-арні функцiї, завданi на неструктурованих множинах (напри-клад, на множині N, на множинi R). Kомпозицiями ППА є операцiї суперпозицiї, циклу та розгалуження.
Операцiї суперпозицiї це описані вище операцiї S .
Кожну V-квазиарну функцiю на N можна трактувати як предикат, інтерпретуючи значення 0 як істиннісне значення "F", а довільне значення а 0 як істинісне значення "Т". Тому для випадку V-квазиарних функцiй на N дамо наступні визначення операцій розгалуження та циклу.
Операцiя розгалуження N V-квазиарним функцiям g, h та ставить у вiдповiднiсть V-квазиарну функцiю f, значення f(d) якої для кожного d VA визначається так:
f(d) =
Операцiя циклу N?v V-квазиарним функціям g та
Loading...

 
 

Цікаве