Обчислюваність n-арних функцій на 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ю f(x1, ..., xm) = g(g1(x1, ..., xт), ..., gn(x1, ..., xm)).
Таку функцiю будемо позначати Sn+1 (g, g1,
..., gn), її
арність співпадає з арнiстю g1,
..., gn.
Операцiя примiтивної
рекурсiї R n-арнiй функцiї g та (n+2)-арнiй функцiї h зіставляє (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,
... ... ... ... ... ... ... ... ... ... ...
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 зіставляє n-арну функцiю f, яку позначають M(g), що задається спiввiдношенням f(x1,
..., xn) = my(g(x1, ..., xn, y)
= 0)
Для всiх
значень x1, ..., xn значення 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
, t)¯ ¹0.
Зрозуміло,
що функцiя g може бути тотальною, а
функцiя f = M(g) – навiть всюди
невизначеною. Наприклад, f(x) = my(x+y+1 = 0).
Базовими функцiями називаються
найпростiшi функцiї о(x) = 0, s(x) = x+1 та функцiї-селектори I
(x1,
..., xn) = xm,
де n ³ m ³ 1.
Всi базовi функцiї
тотальнi та алгоритмiчно обчислюванi.
Функцiю,
яку можна отримати iз базових функцiй за допомогою скiнченної кiлькостi
застосувань операцiй суперпозицiї та примiтивної рекурсiї, називають примiтивно рекурсивною функцiєю (ПРФ).
Функцiю,
яку можна отримати iз базових функцiй за допомогою скiнченної кiлькостi
застосувань операцiй суперпозицiї, примiтивної рекурсiї та мiнiмiзацiї,
називають частково рекурсивною
функцiєю (ЧРФ).
Тотальну
ЧРФ називають рекурсивною функцiєю
(РФ).
Iз
наведених визначень випливають наступні твердження:
1. Якщо функцiї g, g1, ..., gn тотальнi алгоритмiчно
обчислюванi, то функцiя Sn+1(g,
g1, ..., gn) тотальна алгоритмiчно обчислювана.
2. Якщо функцiї g та h тотальнi алгоритмiчно
обчислюванi, то функцiя R(g, h)
тотальна алгоритмiчно обчислювана.
3. Якщо функцiя g алгоритмiчно обчислювана,
то функцiя M(g) алгоритмiчно обчислювана.
4. Кожна ЧРФ – алгоритмiчно обчислювана функцiя.
5. Кожна РФ та кожна ПРФ – тотальна алгоритмiчно обчислювана функція.
6. Для класів функцій мають місце спiввiдношення ПРФ Í РФ Í ЧРФ.
Алгебра (Â; R,
M, S2, S3,
...), носiєм Â якої є клас всiх
ЧРФ, а операцiями – операцiї R, M
та Sn+1, де n³1, називається алгеброю ЧРФ, або алгеброю Чoрча.
Алгебра (Âpr ; R, S2,
S3, ...), носiєм Âpr якої є клас всiх
ПРФ, а операцiями – операцiї R та Sn+1,
де n³1, називається алгеброю ПРФ.
Введемо
поняття операторного терма алгебри ЧРФ
та операторного терма алгебри ПРФ.
Алфавiт складатиметься iз символiв базових функцiй о, s та I
, де n ³ m ³1, символiв
операцiй R, M та Sn+1, де n ³ 1, а також
допомiжних символiв "(", ")" та "," .
Дамо
iндуктивне визначення ОТ алгебри ЧРФ.
1) кожен
символ базової функцiї є ОТ; такі ОТ назвемо атомарними;
2) якщо t0, t1, ..., tn – ОТ, то Sn+1(t0, t1, ..., tn) – ОТ;
3) якщо t1 та t2 – ОТ, то R(t1, t2) – ОТ;
4) якщо t
– ОТ, то M(t) – ОТ.
Аналогiчно
дається індуктивне визначення ОТ алгебри ПРФ.
Кожна ЧРФ є
значенням деякого ОТ алгебри ЧРФ. Проте не кожен ОТ алгебри ЧРФ має певне
значення. Наприклад, операторнi терми R(о,
I
) та S3(I
, I
, I
) не мають значення. Завдання ЧРФ операторними
термами не є однозначним. Наприклад, операторні терми о, S2(о, s), S2(о, о) та S2(о, S2(о,
s))
задають одну i ту ж функцiю о(x).
Розглянемо приклади ПРФ, ЧРФ та РФ.
Приклад 1. Функцiї-константи – ПРФ.
n-арна нуль-функцiя
оn(x1, ..., xn) = 0 задається ОТ S2(о, I
);
n-арна
константа kn(x1, ..., xn) = k задається ОТ S2(s, S2(s,...,S2(о, I)...).
Приклад 2. Функцiя f(x1, x2) = x1+x2 – ПРФ. Справдi, маємо
f(x1, 0) = x1
= I
(x1);
f(x1, x2+1) = x1+(x2+1) = (x1+x2)+1 = s(x1+x2) = s(f(x1, x2)).
Таким
чином, функцiя f(x1, x2) = x1+x2 виникає примiтивною
рекурсiєю iз функцiй g(x1) = I(x1)
та h(x1, x2, x3) = x3+1
= s(x3) = S2(s, I
)(x1,
x2, x3).
Операторний
терм функцiї x1+x2 має вигляд R(I, S2(s,
I)).
Приклад 3. Функцiя f(x1, x2) = x1×x2 – ПРФ.
Справдi, маємо
f(x1, 0) = 0 = о(x1);
f(x1, x2+1) = x1×(x2+1) = x1×x2+x1
= f(x1, x2)+х1.
Отже, f(x1,
x2) = x1×x2 виникає
примiтивною рекурсiєю iз функцiй g(x1) = о(x1) та h(x1, x2, x3)
= x3+x1. За прикладом 2 функцiя h є ПРФ, тому f – ПРФ.
Операторний терм Ä функцiї x1×x2 має вигляд R(о, S3(Å, I, I
)), де Å – операторний терм
функцiї x1+x2 .
Приклад 4. Функцiя f(x1, x2) = 
– ПРФ. Справдi,
маємо
f(x1, 0) = (x1)0 = 1;
f(x1, x2+1) = 
= × x1 = f(x1,
x2)× х1 .
Таким
чином, функцiя f(x1, x2)
= виникає
примiтивною рекурсiєю iз функцiй g(x1) = 11(x1) та h(x1, x2, x3) = x3×x1. За
прикладом 3 функцiя h є ПРФ, тому f – ПРФ.
ОТ функцiї 
має вигляд R(S2(s,о), S3(Ä, I, I)), де Ä –ОТ функцiї x1×x2 .
Приклад 5. Функцiя sg(x1)
= 
– ПРФ.
Справдi,
маємо: sg(0) = 0 = о(x1); sg(x1+1)
= 1.
ОТ функцiї sg(x1)
має вигляд R(о, S2(s,
S2(о, I))).
Приклад 6. Функцiя пsg(x1)
= 
– ПРФ.
Справдi,
маємо: пsg(0) = 1 = s(о(x1)); пsg(x1+1) = 0.
ОТ функцiї пsg(x1)
має вигляд R(S2(s,о), S2(о, I)).
Приклад 7. Функцiя 
= 
є ПРФ
Спочатку
покажемо що функцiя 
– ПРФ. Справдi,
маємо
= 0 = о(x1);
= x1 = I(x1, x2).
Операторний
терм функцiї має вигляд R(о, I).
Тепер
покажемо що функцiя f(x1, x2) = 
– ПРФ. Маємо
f(x1, 0) = 
= I
(x1);
f(x1, x2+1) = 
= 
= 
.
Отже,
функцiя f(x1, x2)
= виникає
примiтивною рекурсiєю iз функцiй g(x1) = I(x1)
та h(x1, x2, x3) = 
. Звідси
операторний терм функцiї має вигляд R(I, S2(R(о, I), I)).
Приклад 8. Функцiя f(x1, x2)
= |x1–x2| = ()+(
) – ПРФ.
Приклад 9. Функцiя f(x1, x2)
= x1–x2 = 
(|x1–(x2+x3)| = 0) – ЧРФ.
Приклад 10. Всюди
невизначена функцiя fÆ – ЧРФ. ×
Cправді, fÆ(x1) = 
(x1+1
= 0), тому fÆ є значенням ОТ М(s).
Приклад 11. Функцiя f(x1, x2) = [x1/x2] – ЧРФ. ×
Cправді, [x1/x2] = (x2
×(x3+1)>x1) = (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 відповідно
Теорема 2.6.1. Нехай (n+1)-арна функцiя g є ПРФ.
Тодi ПРФ є (n+1)-арна функцiя f, задана умовою
f(x1,..., xn, у) = 
.
Домовимося
надалi вважати, що при z<y 
= 0.
Тeорeма 2.6.2. Нехай (n+1)-арна функцiя g є ПРФ.
Тодi ПРФ є (n+2)-арна функцiя f, задана умовою
f(x1, ..., xn, у, z)
= 
.
Тeорeма 2.6.3. Нехай (n+1)-арна функцiя g та n-арнi
функцiї a i b є ПРФ. Тодi ПРФ є n-арна
функцiя h, задана умовою
h(x1, ..., xn) = 
.
Теореми
2.6.1–2.6.3 називають теоремами підсумовування. Замiнивши в
цих теоремах символ суми S на символ добутку P, одержимо теореми
мультиплiкацiї.
(п+1)-арна функцiя f отримується iз (n+1)-арної
функцiї g за допомогою операцiї обмеженої мiнiмiзацiї, якщо вона
задається так:
f(x1,
..., xn, у) = 
Цей факт
позначаємо так: f(x1, ..., xn, у) = 
((g(x1, ..., xn, z) = 0).
Тeорeма 2.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, у) та a(x1, ..., xn) є ПРФ. Тодi ПРФ є функцiя
f(x1, ..., xn) = 
((g(x1, ..., xn, у) = 0).
Приклад 13. Довизначимо функцiю f(x1, x2) = [x1/x2] таким
чином: [x1/0] = x1. Тоді [x1/x2]
є ПРФ.
Справдi,
значення [a/b] рiвне кiлькостi нулiв
в послiдовностi 1×
, 2×
, ..., a×. Маємо
[x1/x2] = 
),
тому [x1/x2] є ПРФ за
теоремою 2.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) = [] є ПРФ
за теоремою 2.6.4.
Справдi, [
] = 
(nsg((x2+1)×(x2+1)) = 0).
Приклад 16. Функцiя пd(x)
– кількість дiльників числа x, – є
ПРФ при довизначенні пd(0) = 1.
Справдi, пd(x)
= 
.
Приклад 17. Функцiя p(x) – кількість простих чисел, які не
більші за число x, – є ПРФ.
Справдi, p(x) =
Приклад 18. Функцiя р(x) – х-ве просте число, – є ПРФ
За
визначенням р(0) = 2, р(1) = 3, р(2) = 5 і т.д.
В
загальному випадку р(x) = 
(|p(у) – (x+1)| = 0).
Доведення
того, що р(x)
, проведемо індукцією по х. Для х = 0 маємо р(0) = 2
. Нехай p(x)
для всіх х£k. Покажемо 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) = mz£y(nsg(mod(y, p(x)z+1))×sg(y) = 0).
Питання для
самоконтролю
1. Дайте
визначення операцій суперпозиції Sn+1, примітивної рекурсії R,
мінімізації M.
2. Укажіть
властивості операцій Sn+1, R
та M.
3. Дайте
визначення базових обчислюваних n-арних
функцій.
4. Дайте
визначення ПРФ, ЧРФ та РФ.
5. Укажіть
властивості ПРФ, ЧРФ та РФ.
6. Дайте
визначення алгебри ЧРФ та алгебри ПРФ.
7. Дайте
визначення операторного терма алгебри ЧРФ.
8. Дайте
визначення операторного терма алгебри ПРФ.
9.
Сформулюйте теореми про підсумовування.
10.
Сформулюйте теореми про мультиплікацію.
11.
Сформулюйте теорему про кускове задання.
12. Дайте
визначення операції обмеженої мінімізації.
13.
Сформулюйте теорему про обмежену мінімізацію.
Вправи
1. Чи може бути тотальною функція Sn+1(g, g1,
..., gn), якщо g
нетотальна ?
2. Чи може бути
тотальною функція Sn+1(g, g1,
..., gn), якщо одна з функцій g1, ..., gn нетотальна ?
3. Чи може бути
тотальною функція R(g, h), якщо g нетотальна ?
4. Чи може бути
тотальною функція R(g, h), якщо h нетотальна ?
5. Чи може бути
тотальною функція M(g), якщо g нетотальна ?
6. Промоделюйте операції Sn+1,
R, M за допомогою систем Поста.
7. Доведіть,
що функція НСК(х1, х2)
(найменше спільне кратне чисел х1
та х2 ) є ПРФ при
довизначенні НСК(n, 0) = НСК(0, n) = 0.
8.
Доведіть, що функція НСD(х1, х2) (найбільший спільний дільник чисел х1 та х2 ) є ПРФ при довизначенні НСD(n, 0) = НСD(0, n) = 0.
9.
Доведіть, що при належному довизначенні наступні функції є ПРФ:
1) s(х) – сума дільників числа х;
2) spd(хсума простих
дільників числа х;
3) kpd(х) – кількість простих дільників числа х.
10. Вкажіть ОТ алгебри п-арних ЧРФ
для функцій:
1) f(x1) = (x1)! ; 2)
f(x1, x2) = (x2 +2)! ;
3) f(x1, x2, x3) = (x2 + x3)! ; 4)
f(x1) = (2x1)!! ;
5) 
6)
7) f(x1, x2, x3) = 
8)
f(x1) = [log2(x1)];
9) f(x1, x2) = [log3(x1+x2)]; 10)
;
11) 
; 12) 
.
