Нумерації
Різні формальні моделі алгоритмів діють на різних множинах даних. Наприклад машина Тьюрінга реалізує вербальні алгоритми, а МНР-програми визначають функції натуральних аргументів і значень. Для порівняння різних формальних моделей, і переходів між ними треба кодувати елементи однієї множини елементами іншої.
Кодування ред.
Кодування множини A на множині B — це ін'єктивне та сюр'єктивне відображення φ: А→В таке, що існують алгоритми ℵ та ℜ:
- для кожного а∈А ℵ(а)∈φ (а);
- для кожного b∈B ℜ(b) = φ-1(b).
Нумерації ред.
Нумерацією множини А назвемо сюр'єктивне функціональне відображення ξ : N →А. Однозначною нумерацією множини А назвемо бієктивне відображення ξ : N →А.
Нумерація ξ : N→А ефективна, якщо існують алгоритми ℵ та ℜ:
- для кожного а∈А ℵ(а)∈ξ–1(а);
- для кожного n∈N ℜ(n) = ξ(n).
Таким чином, ξ : N→А – ефективна нумерація ⇔ ξ–1: А→N – кодування А на N.
Канторові нумерації ред.
Введемо однозначні ефективні нумерації пар та n-ок натуральних чисел, які називаються канторовими нумераціями.
Номер пари (x,y) в такій послідовності позначають C(x,y) та називають канторовим номером пари(x,y). Неважко переконатись, що C(x,y)=[(x+y+1)⋅(x+y)/2]+x
Ось її табулювання:
0 1 3 6 10 15 21 28 36 45 2 4 7 11 16 22 29 37 46 56 5 8 12 17 23 30 38 47 57 68 9 13 18 24 31 39 48 58 69 81 14 19 25 32 40 49 59 70 82 95 20 26 33 41 50 60 71 83 96 110 27 34 42 51 61 72 84 97 111 126 35 43 52 62 73 85 98 112 127 143 44 53 63 74 86 99 113 128 144 161 54 64 75 87 100 114 129 145 162 180
Ліву та праву компоненти пари з номером n позначають відповідно l(n) та r(n). Функції l(n) та r(n) називають відповідно лівою та правою координатними функціями. Подібна нумерація застосовувалась при доведенні зліченності множини раціональних чисел.
Функції C, l та r зв'язані тотожностями:
C(l(n), r(n)) = n;
l(C(x, y)) = x;
r(C(x, y)) = y.
Маючи нумерацію пар натуральних чисел, можна ввести нумерацію n-ок натуральних чисел для довільного n>2:
Cn(x1,x2,...,xn)=Cn-1(C(x1, x2),x3,...,xn)=C(...С(C(x1, x2), x3),...),xn).
Всі пари натуральних чисел розташуємо в послідовність так: пара (x, y) передує парі (u, v)↔x+y<u+v або (x+y = u+v та x<y).
Номер пари (x, y) в такій послідовності позначають C(x, y) та називають канторовим номером пари (x, y).
Неважко переконатись, що C(x, y) = [(x+y+1)*(x+y)/2]+x
Ліву та праву компоненти пари з номером n позначають відповідно l(n) та r(n). Функції l(n) та r(n) називають відповідно лівою та правою координатними функціями.
Функція C(x, y) задає бієкцію N×N→N, пара функцій (l(n), r(n)) задає бієкцію N→N×N.
При цьому функції C,l та r зв’язані такими тотожностями: C(l(n), r(n)=n; l(C(x, y))=x; r(C(x, y))=y. Маючи нумерацію пар натуральних чисел, можна ввести нумерацію n-ок натуральних чисел для довільного n>2:
Cn(x1, x2,..., xn)=C^n-1(C(x1, x2), x3,..., xn)=C(...С(C(x1, x2), x3),...), xn).
Координатні функції Cn1 , ..., Cnn вводимо так:
Нехай Cn(x1, x2,..., xn)=m; тоді Cn1(m)=x1; Cn2(m)=x2; ... , Cnn(m)=xn.
Для функцій Cn, Cn1 , ..., Cnn справджуються такі тотожності:
Сп(Cn1(x), ..., Cnn(x))=x; Cnk(Сп(x1, x2,..., xn))=xk, 1≤k≤n.
Теорема 1.1. 1) Функції C(x, y), l(n) та r(n) є ПРФ. 2) Функції Cn, Cn1 , ..., Cnn є ПРФ.
Приклад 1. Знайдемо l(100) та r(100). Для х=l(100) та у=r(100) маємо рівняння С(х, у)=100. Нехай х+у=р. Тоді р є найбільшим натуральним числом, для якого р*(р+1)≤2*100. Звідси р=13. Маємо х+у=13, х=100-[(1314)/2]=9, y=13-9=4. Отже, l(100)=9 та r(100)=4.
Приклад 2. Розв'яжемо рівняння C4(x,y,z,v)=207. За визначенням маємо С(С(С(x,y),z),v)=207. Нехай С(С(x,y),z)=а, маємо C(а,v)=207. Нехай a+v=р. Тоді р є найбільшим натуральним числом, для якого р*(р+1)≤2*207. Звідси р=19, звідки а=17 та v=2. Тепер маємо С(С(x,y),z)=17. Нехай С(x,y)=b, тоді C(b,z)=17. Нехай b+z=q. Тоді q є найбільшим натуральним числом, для якого q*(q+1)≤2*17. Звідси q=5, звідки b=2 та z=3. Маємо C(x,y)=2, звідки x=1 та y=0.
Приклад 3. Задамо однозначну ефективну нумерацію всіх скінченних послідовностей натуральних чисел на основі наступного кодування k:Ų,k≥0,N^k→N таких послідовностей: k(Ø)=0; k(а1, ..., ап)= C(C^n(а1, ..., аn), n-1)+1. Зрозуміло, що таке відображення бієктивне. Тепер обернене відображення η=k^-1 - шукана однозначна нумерація.
Приклад 4. Однозначну ефективну нумерацію всіх скінченних послідовностей натуральних чисел можна задати на основі такого кодування ò:Ų,k≥0,N^k→N всіх скінченних послідовностей: k(Ø)=0; k(а1, ..., аn)=2^a1+2^A1+a2+...+2^a1+a2+...+an+n-1. Бієктивність відображення ò випливає із однозначності подання кожного натурального числа в двійковій системі числення. Обернене відображення α=ò^-1 -шукана однозначна нумерація.
Приклад 5. Однозначну ефективну нумерацію всіх непорожніх скінченних послідовностей натуральних чисел задамо на основі кодування ʋ:Ų,k≥0,N^k→N, що є модифікацією кодування ò: ʋ(а1, ..., аn)=2^a1+2^a1+a2+1+...+2^a1+a2+...+an+n-1-1. Обернене відображення ξ=ʋ^-1 - шукана однозначна нумерація.
Приклад 6. Ефективну нумерацію Φ множини формул довільної мови 1-го порядку із зліченним алфавітом введемо таким чином. Занумеруємо множини предметних імен x0, x1, ..., константних символів c0, c1, ... , функціональних символів f0, f1, ... та предикат-них символів p0, p1,... . Кодування k термів та формул.задамо так:
K(xk)=7-k ;
K(ck)=7-k+1;
K(fk t1...tn)=7-C(Cn+1(k,K(t1),...,K(tn)), n-1)+2;
K(pk t1...tn)=7-C(Cn+1(k, K(t1),...,K(tn)), n-1)+3;
K(ḷФ)=7-C(k,К(Ф))+4;
K(٧ФΨ)=7-C(К(Ф),К(Ψ))+5;
K(ЭxkФ)=7-C(k,К(Ф))+6.
Номером (індексом) довільної формули Ф вважатимемо її код К(Ф). Всі тi натуральні числа, які не є кодами формул, вважатимемо номером формули x0=x0 . Зрозуміло, що так введена нумерація Ф неоднозначна. Формулу з номером n позначатимемо Фn . Кодувати довільну скінченну послідовність натуральних чисел. дозволяє також функція Гьоделя Г(x, y) = mod(l(x), 1+(y+1)-r(x)). З визначення випливає, що Г(x, y) є ПРФ.
Теорема 1.2 (про основну властивість функції Гьоделя). Для довільної скінченної послідовності натуральних чисел b0, b1, ..,bn існує натуральне число t таке, що Г(t, i)=bi для всіх іє{0,...,n}.
Використання функції Гьоделя дає змогу промоделювати опера-цію примітивної рекурсії операціями суперпозиції та мінімізації:
Теорема 1.3. Функція f=R(g, h) може бути отримана із функцій g, h, базових функцій і функцій +,× за допомогою скінченної кількості застосувань операцій S^n+1 та М. Наслідок. Клас ЧРФ співпадає з класом функцій, отриманих із функцій о, s, I(m,n) , +, × за допомогою операцій S^n+1 та M.
Ефективні нумерації формальних моделей алгоритмів та АОФ ред.
Розглянемо приклади ефективних нумерацій формальних моделей алгоритмів та алгоритмічно обчислюваних функцій.
Приклад 1. Однозначну ефективну нумерацію всіх МНР-програм задамо на основі кодування МНР-програм як скінченних послідов-ностей команд МНР. Кодування команд Ө задамо так:
Ө(Z(n))= 4-n;
Ө(S(n))= 4-n+1;
Ө(T(т,n))= 4-С(m,n)+2;
Ө(J(m,n,q+1))=4-С(С(m,n),q)+3.
Зрозуміло, що Ө -бієктивне відображення множини всіх команд МНР на N. Використовуючи розглянуту вище бієкцію ν:Ṵ N^k→N, k>=1 задамо кодування Ί всіх МНР-програм так. Якщо P - МНР-програма I1,I2...Iк , то Ί(P) = ν(Ө(I1),..., Ө(Ik)). Відображення ν та Ө бієктивні, тому Ί теж бієкція. Тоді γ=Ί^-1 - шукана однозначна нумерація. Нумерація γ ефективна. Справді, за кожною МНР-програмою P ефективно обчислюється її номер Ί(P). З іншого боку, за кожним nєN ефективно визначається МНР-програма P=γ(n). Справді, спочатку подамо число n+1 як суму зростаючих степенів числа 2: n+1=2^b1+2^b2+...+2^bk,де 0<b1<...<bk. Далі визначимо послідовність чисел a1, ..., ak: a1=b1, ai+1=bi+1-bi-1 для 1<i<k. Тепер за числами a1, ..., ak як за кодами команд МНР відновимо відповідні команди. Послідовність цих команд i є шуканою МНР-програмою P.
МНР-програму з кодом n позначатимемо Pn.
Приклад 1.1. Знайдемо код МНР-програми P, яка обчислює бінарну функцію х+у. Використаємо приклад 3 розділу 2.1. Маємо:
1)J(1,2,5);Ө(J(1,2,5))=4-С(С(1,2),4)+3=4-С(7,4)+3=4*73+3=295;
2)S(0);Ө(S(0))=4*0+1=1;
3)S(2);Ө(S(2))=4*2+1=9;
4)J(0,0,1);Ө(J(0,0,1))=4-С(С(0,0),0)+3=4-С(0,0)+3=4*0+3=3.]
Тепер Ί(P)=ν(295,1,9,3)=2^295+2^297+2^307+2^311-1.
Приклад 1.2. Знайдемо P5119 =γ(5119). Маємо 5119+1=5120=2^10+2^12, звідки a1=10,a2=12-10-1 = 1. Але 10=2+4*C(1,0), тому P5119 така:
1) T(1,0)
2) S(0).
Приклад 2. Ефективну нумерацію всіх МТ задамо на основі кодування МТ. Кожну МТ можна задати послідовністю її команд такою, що 1-а команда містить в лівій частині символ q0 , остання команда містить в правій частині символ q*. Таке завдання неоднозначне, бо множину команд МТ можна впорядкувати у вигляді послідовності з вищевказаною властивістю багатьма способами. Тому наша нумерація МТ неоднозначна.
Занумеруємо внутрішні стани МТ та символи стрічки. Нехай Q={q1,..., qf}, T={a1,..., am}. Кодування μ команд МТ задамо так:
μ(qiaj→qka1)=3-C^4(i,j,k,l);
μ(qiaj→qka1L)=3-C^4(i,j,k,l)+1;
μ(qiaj→qka1R)=3-C^4(i,j,k,l)+2.
Таке μ є бієктивним відображенням множини всіх можливих команд машин Тьюрінга на N. Використовуючи розглянуту вище бієкцію ν:Ṵ N^k→N, k>=1 визначимо код МТ M, заданої послідовністю команд I1,I2...Iк , таким чином: p(M)=ν(μ(I1),...,μ(Ik)). Але ν та μ бієктивні, тому p теж бієкція. Тоді γ=p^-1 - шукана однозначна нумерація послідовностей команд МТ, але неоднозначна нумерація всіх МТ. Неважко переконатись, що така нумерація ефективна.
Приклад 2.1. Знайдемо код МТ М, яка обчислює бінарну функцію х+у. Вважаємо a0=ʆ, a1=|, a2=# та q*=q2 . Використаємо приклад 1 розділу 2.2. Маємо:
q0|→q0|R; μ(q0|→q0|R)=3-C^4(0,1,0,1)+2=3-C(2,1)+2=3*8+2=26;
q0#→q0|R; μ(q0#→q0|R)=3-C^4(0,2,0,1)+2=3-C(9,1)+2=3*64+2=194;
q0ʆ→q1ʆL; μ(q0ʆ→q1ʆL)=3-C^4(0,0,1,0)+1=3-C(1,0)+1=3*2+1=7;
q1|→q*ʆ; μ(q1|→q*ʆ)=3-C^4(1,1,2,0)=3-C(25,0)=3*350=1050.
Тепер p(M)=ν(26,194,7,1050)=2^26+2^221+2^229+2^1280-1.
Приклад 3. Ефективну нумерацію Ѱ всіх m-арних ЧРФ задамо на основі кодування γ операторних термів алгебри ЧРФ. Завдання ЧРФ операторними термами неоднозначне, бо кожну ЧРФ можна описати нескінченною кількістю різних ОТ, тому нумерація Ѱ неоднозначна.
Кодування Ѱ операторних термів задамо так:
γ(о) = 0; γ(s) = 4; γ(I(m,n)) = 4-(C(n, m)-2);
γ(S^n+1(t0, t1,..., tn))=4-C(Cn+1(γ(t0),γ(t1),..., γ(tn)), n-1)+1;
γ(R(t0, t1))=4-C(γ(t0),γ(t1))+2;
γ(M(t))=4-γ(t)+3.
Число nєN вважаємо номером ЧРФ f, якщо n є кодом якогось ОТ, i значенням цього ОТ є функція f. Числа, які не є кодами ОТ, та коди тих ОТ, які не задають ЧРФ, вважаємо номерами всюди невизначеної функції fø. Зрозуміло, що за кожною ЧРФ можна ефективно знайти її номер. З іншого боку, за кожним nєN ефективно визначається ЧРФ f така, що Ѱ(n)=f : за n як за кодом будуємо ОТ; якщо ОТ з таким кодом існує та задає ЧРФ, то Ѱ(n)-саме така ЧРФ f ; якщо ОТ з таким кодом існує, але не задає ЧРФ, то Ѱ(n)=fø; якщо ОТ з таким кодом не існує, то Ѱ(n)= fø. Отже,Ѱ є ефективною нумерацією всіх ЧРФ.
Приклад 3.1. Знайдемо код ОТ алгебри п-арних ЧРФ для всюди невизначеної функції f. Згадуючи приклад 9 розділу 6.6, для fø маємо ОТ М(s), звідки γ(M(s))=4-γ(s)+3=4-4+3=19.
Приклад 4. Ефективну нумерацію всіх ПРФ задамо на основі кодування операторних термів алгебри ПРФ. Така нумерація ПРФ неоднозначна. Кодування Π ОТ алгебри ПРФ задамо так:
γ(о)=0; γ(s)=3; γ(I(m,n)) = 3-(C(n, m)-2);
γ(S^n+1(t0, t1,..., tn)) = 3-C(Cn+1(γ(t0),γ(t1),...,γ(tn)),n-1)+1;
γ(R(t0,t1)) = 3-C(γ(t0),γ(t1))+2.
Число nєN вважаємо номером ПРФ f, якщо n є кодом якогось ОТ та значенням цього ОТ є функція f. Числа, які не є кодами ОТ, та коди тих ОТ, які не задають ПРФ, вважаємо номерами функції о.
Приклад 4.1. Знайдемо код ОТ алгебри ПРФ для f(x1, x2)=x1+x2 . Згідно прикладу 2 розділу 6.6, для x1+x2 маємо ОТ R(I(1,1),S^2(s,I(3,3))), звідки отримуємо γ(R(I(1,1), S2(s,I(3,3))))=3-C(γ(I(1,1)),γ(S2(s,I(3,3))))+2= =3-C(6,3-C(С(γ(s),γ(I(3,3))), 0)+1)+2 =3-C(6, 3-C(С(3, 24),0)+1)+2 =3-C(6,3-C(381, 0)+1)+2 =3-C(6, 3-73152+1)+2 =3-C(6, 219457)+2 =3-24 082 113 916+2 =72 246 341 748+2 = 72 246 341 750.
Приклад 5. Ефективну нумерацію всіх програмованих на N n-арних функцій задамо на основі кодування операторних термів ППА-Ar-N. Зрозуміло, що така нумерація неоднозначна. Єдина істотна відмін-ність від нумерації прикладу 3 - інше кодування γ операторних термів ППА-Ar-N: γ(о)=0; γ(s)=4; γ(+)=8; γ(-)=12; γ(÷)=16: γ(I(m,n)) = 4-(C(n, m)+1); γ(S^n+1(t0, t1,..., tn)) = 4-C(C^n+1(γ(t0), γ(t1),..., γ(tn)), n-1)+1; γ(NΔ(t0, t1, t2)) = 4-C3(γ(t0), γ(t1), γ(t2))+2; γ(N☼(t0, t1)) = 4-C(γ(t0), γ(t1))+3.
Приклад 6. Ефективну нумерацію ₰^n всіх МНР-обчислюваних функцій фіксованої арності n задамо на основі кодування МНР-програм (приклад 1). Номером n-арної МНР-обчислюваної функції f буде код МНР-програми, яка обчислює функцію f. Кожна n-арна МНР-обчислювана функція може задаватися нескінченною кількістю різних МНР-програм, тому така нумерація неоднозначна.
Приклад 7. Ефективну нумерацію всіх МНР-обчислюваних функцій можна ввести на основі кодування МНР-програм. Номером n-арної функції f буде число С(k, n), де k - код МНР-програми для f.
Приклад 8. Ефективну нумерацію всіх МТ-обчислюваних функцій фіксованої арності п задамо на основі кодування МТ. Номером n-арної МТ-обчислюваної функції f буде код МТ, яка обчислює f. Кожна n-арна МТ-обчислювана функція може задаватися нескінчен-ною кількістю різних МТ, тому така нумерація неоднозначна.
Приклад 9. Ефективну нумерацію всіх обчислюваних за Тьюрінгом функцій введемо на основі кодування МТ. Номером МТ-обчислю-ваної функції f арності n буде число С(k, n), де k - код МТ для f.
Нумерації n-арних ЧРФ. Універсальні функції. s-m-n-теорема ред.
В силу співпадіння класів ЧРФ, програмованих на N функцій, МНР-обчислюваних функцій та МТ-обчислюваних функцій, нумерації прикладів 5, 6 та 8 розділу 7.2 можна розглядати як ефек-тивні нумерації всіх n-арних ЧРФ для фіксованого п, а нумерації прикладів 3, 7 та 9 як ефективні нумерації всіх n-арних ЧРФ.
Зафіксуємо для кожного n>=1 ефективну нумерацію n-арних ЧРФ. Звичайно це буде нумерація на основі кодування МНР-програм (приклад 6), інколи нумерація на основі кодування МТ (приклад 8). Вказані нумерації назвемо стандартними нумераціями n-арних ЧРФ. Для стандартних нумерацій введемо наступні позначення.
n-арну ЧРФ з номером m позначатимемо ₰(m,n). У випадку n=1 вживатимемо спрощене позначення ₰m .Область визначення та область значень функції ₰(m,n) позначатимемо відповідно D(n,m) та E(n,m). У випадку n=1 вживатимемо позначення Dm та Em. Номер функції назвемо також індексом функції. Номер функції в стандартній намерації назвемо стандартним індексом функції.
Нумерація ξ називається Гьодельовою, якщо існують рекурсивні функції f та g такі:
- для кожного тєN ₰(n,m)=ξf(m);
- для кожного kєN ξk =₰(n,g(k)) .
Це означає, що існує пара алгоритмів, перший з яких за стандартним індексом функції знаходить її ξ-індекс, а другий за ξ-індексом функції знаходить її стандартний індекс.
Нехай F - деякий клас функцій вигляду Х→Y, для якого задана нумерація ξ: N→F. З кожною такою нумерацією ξ зв’язана функція U: N×Х→Y, що визначається умовою U(n,х)=ξn(х). Таку функцію и називають спряженою з нумерацією ξ. Нумерація називається обчислюваною, якщо спряжена з нею функція є ЧРФ. Для довільного класу n-арних функцій F клас всіх функцій із F фіксованої арності т будемо позначати Fт.
Функція U(y, x1, ..., xn) універсальна для класу Fn, якщо:
- для кожного значення m функція U(y, x1, ..., хп)єFn;
- для кожної fєFn існує таке m, що f(x1, ..., xn)=U(m, x1, ..., xn) для всіх значень x1, ..., xn .
Теорема 3.1. Нехай T - деякий клас тотальних п-арних функцій на N, який містить функції о, s, I та замкнений відносно суперпозиції. Нехай функція u універсальна для Тп. Тоді uєT.
Наслідок 1. Функція, універсальна для класу n-арних РФ, не є ЧРФ.
Наслідок 2. Функція, універсальна для класу n-арних ПРФ, не є ПРФ.
Теорема 3.2. Існує РФ, універсальна для класу n-арних ПРФ.
Наслідок 1. Існує РФ, яка не є ПРФ.
Наслідок 2. Для відповідних класів функцій маємо строгі включення ПРФ උ РФ උ ЧРФ.
Теорема 3.3. Існує ЧРФ, універсальна для класу n-арних ЧРФ.
Такою буде функція U(у, x1, ..., xn) = φ(n,m) (x1, ..., xn). МНР-програма, яка обчислює універсальну ЧРФ, називається універсальною МНР-програмою. Універсальна програма декодує довільне число y в програму Py , а далі вона моделює роботу Py . Тому така універсальна програма може бути задана в явному вигляді. Отже, можна конструктивно знайти індекс k універсальної функції u в стандартній нумерації (n+1)-арних ЧРФ, тобто u суть функція φ(n+1,k).
Машина Тьюрінга, яка обчислює універсальну ЧРФ, називається універсальною МТ. Таку МТ, здатну моделювати роботу довільної МТ за її кодом, теж можна задати в явному вигляді. Для кожного фіксованого значення а1, ..., ат аргументів x1, ..., xт (m+n)-арна ЧРФ s(m,n)(x1, ..., xт, у1, ..., уп). стає n-арною ЧРФ φ(n,k)(у1, ..., уп). Її індекс k можна ефективно знайти за z та а1, ..., аm. Це означає, що існує (m+1)-арна РФ, яку традиційно позначають s(m,n), що обчислює цей індекс:
Теорема 3.4 (s-m-n-теорема). Для довільних m, n>1 існує (m+1)-арна РФ s (z, x1, ..., xm) така, що для всіх z, x1, ..., xт, у1, ..., уп маємо φ(m+n,z) (x1, ..., xт, у1, ..., уm) = φ(m,s(m,n))(у1, ..., уm).
Приклад 1. Залежність функції s(m,n) від n можна зняти, якщо для завдання ЧРФ використати МТ. Справді, за z визначаємо МТ з кодом z для функції φ(m+n,z). Задамо нову МТ M, яка зліва від початкового вмісту стрічки дописує слово |x1#|x2#...#|xm, a далі моделює роботу МТ з кодом z. Така МТ M при вході |y1#|y2#...#|ym обчислює n-арну функцію φ(n,k), причому k - код МТ M, M - не залежить від n .
Теорема 3.5 (s-m-n-теорема в спрощеній формі). Для кожної ЧРФ f(x1, ..., xm, у1, ..., уn) існує РФ s(x1, ..., xm) така, що для всіх x1, ..., xт, у1, ..., уn маємо f(x1, ..., xm, у1, ..., уn) = φ(n,s)(у1, ..., уn). При m=n=1 спрощена s-m-n-теорема формулюється так:
Теорема 3.6. Для кожної ЧРФ f(x, y) існує РФ s(x) така, що для всіх значень x, y маємо f(x, y)= φs(x)(y). Розглянемо приклади застосування s-m-n-теореми.
Приклад 2. Існує РФ s(x, y) така, що для всіх х, y, zєN маємо φs(x,y) (z)=φx(z)+φy(z). Розглянемо функцію f(x, y, z)=φx (z)+φy (z). Функція f є ЧРФ, тому за s-m-n-теоремою існує РФ s(x, y) така, що для всіх х, y, zєN маємо f(x, y, z)=φs(x,y) (z)=φx (z)+φy (z).
Приклад 3. Для кожної 1-арної ЧРФ f існує РФ s(x) така, що для всіх хєN маємо D s(x)= f^-1(Dx). Розглянемо функцію g(x, y)=φx(f(y)). Така функція є ЧРФ за ТЧ, тому за s-m-n-теоремою існує РФ s(x) така, що для всіх х, yєN маємо g(x, y)=φs(x) (у). Зафіксуємо х. Маємо уєD s(x)<–> φ s(x)(у)↓ <–>g(x, y)↓<–>φx(f(y))↓<–>f(y)єDx<–>yєf-1(Dx). Звідси Ds(x)= f^-1(Dx).
Приклад 4. Існує РФ s(x) така, що для всіх хєN маємо Е s(x)=Dx . Розглянемо функцію f(x, y)=у,якщо ує Dx,інакше-невизначена. Така функція є ЧРФ за ТЧ, тому за s-m-n-теоремою існує РФ s(x) така, що для всіх х, yєN маємо f(x, y)=φs(x )(у). Зафіксуємо х. За побудовою функції f маємо D s(x)=Е s(x). Тепер уєЕs(x)↔ уєDs(x)↔φs(x)(у)↓ ↔ f(x, y)↓ ↔ уєDx . Звідси Es(x)=Dx .
Приклад 5. Існує РФ t(x) така, що для всіх хєN маємо Dt(x)=Еx .
Розглянемо функцію f(x, y)=1,якщо ує Еx,інакше-невизначена. Така функція є ЧРФ за ТЧ, тому за s-m-n-теоремою існує РФ t(x) така, що для всіх х, yєN f(x, y)=φt(x)(у). Зафіксуємо х. Маємо уєDt(x)↔φt(x) (у)↓↔f(x, y)↓↔уєЕх . Звідси Dt(x)=Ex .
Приклад 6. Існує РФ s(x) така, що для всіх хєN маємо D(2,s(x))={(u, v) | x=2u+3v}. Розглянемо функцію f(x, u, v)=1,якщо x=2u+3v,інакше-невизначена. За ТЧ f є ЧРФ, тому за s-m-n-теоремою існує РФ s(x) така: для всіх х, u, vєN маємо f(x, u, v)= φ(2,s(x))(u, v). Зафіксуємо х. Тепер (u, v)єD(2,s(x))↔φ(2,s(x))(u, v)↓ ↔ f(x, u, v)↓ ↔ x=2u+3v. Звідси D(2,s(x))={(u, v) | x=2u+3v}.
Приклад 7. Існує РФ s(x, y) така, що для всіх х, yєN маємо D s(x,y)=Dx٧Dy . Розглянемо функцію f(x, y, z)=1,якщо zє Dx або zє Dy,інакше-невизначена. Така функція є ЧРФ за ТЧ, тому за s-m-n-теоремою існує РФ s(x, y) така, що для всіх х, y, zєN маємо f(x, y, z)=s(x,y)(z). Зафіксуємо х та y. Маємо zєD s(x,y)↔φ s(x,y)(z)↓↔f(x, y, z)↓↔ zєDx٧Dy . Звідси випливає D s(x,y)=Dx٧Dy .
Приклад 8. Існує РФ s(x, y) така, що для всіх х, yєN маємо Ds(x,y)=Es(x,y)=Dx٨Dy . Розглянемо функцію f(x, y, z)=1,якщо zє Dx або zє Dy,інакше-невизначена. Така функція є ЧРФ за ТЧ, тому за s-m-n-теоремою існує РФ s(x, y) така, що для всіх х, y, zєN маємо f(x, y, z)=φs(x,y) (z). Зафіксуємо х та y. За побудовою функції f маємо Ds(x,y)=Es(x,y). Тепер zєЕs(x,y)↔zєDs(x,y)↔φs(x,y) (z)↓↔f(x, y, z)↓↔zєDx٨Dy . Звідси отримуємо Ds(x,y)=Es(x,y)=Dx٨Dy .
Теореми Кліні про нерухому точку ред.
Теорема 4.1. Нехай f - (n+1)-арна РФ. Тоді існує n-арна РФ g така, що φ g(x1,x2,...,xn)=φ f(g(x1,x2,...,xn),x1,x2,...,xn) для всіх значень x1, ..., хп. Переформулюємо теорему 7.4.1 для випадку n=0.
Теорема 4.2. Нехай f(x)-РФ. Тоді існує nєN таке, що φn = φf(n). Первісне формулювання самого С.Кліні теореми про нерухому точку має наступний вигляд:
Теорема 4.3. Нехай h(z, x)-ЧРФ. Тоді існує nєN таке, що для всіх x маємо h(n, x)=φ n(x). Теорему Кліні про нерухому точку краще називати теоремою про псевдонерухому точку. Справді, умова φ n=φ f(n) зовсім не означає, що n=f(n), a свідчить тільки про те, що n та f(n)-індекси однієї i тої ж ЧРФ.
Приклад 1. МНР-програму P назвемо самотворною, якщо для довільного xєN маємо P(x)↓τ(P), де τ(P) -код програми P. На перший погляд, таких програм бути не може, бо для побудови P треба знати τ(P) тобто саму програму P. Проте МНР-програма P така, що P(x)↓τ(P) для всіх значень x, таки існує. Справді, візьмемо функцію h(z, x)=z. За теоремою 7.4.3 існує таке n, що для всіх x h(n, x)=φn(x). Отже, φn(x)=h(n, x)=n для всіх x. Тому програма P з кодом n -шукана.
Приклад 2. Існує nєN таке, що для всіх x маємо φn(x)=2n+x^3n. Візьмемо функцію h(z, x)=2z+x3z. За теоремою 7.4.3 існує таке n, що для всіх x h(n, x)=φn(x). Отже, φn(x)=h(n, x)=2n+x3n для всіх x.
Приклад 3. Існує nєN таке, що Dn=En={n}. Візьмемо функцію h(z, x)=x якщо х=z,інакше - невизначена. Така h є ЧРФ. За теоремою 7.4.3 існує таке n, що для всіх x маємо h(n, x)=φn(x). Тоді φn(x)=x якщо х=n,інакше- невизначена. Звідси Dn=Еn={n}.
Приклад 5. Існує nєN таке, що Dп=En=N\{n, 2n}. Візьмемо функцію h(z, x)=x якщо х≠z та х≠2z,інакше - невизначена.Така h є ЧРФ. За теоремою 7.4.3 існує таке n, що h(n, x)=φn(x) для всіх x. Тоді φn(x)= x якщо х≠n та х≠2n,інакше - невизначена. Звідси Dn=En=N\{n, 2n}.
Приклад 4. Існує nєN таке, що Dп=Еп={x | x непарне}υ{2, 4, ..., 2п}. Функція h(z, x) = x якщо х непарне або хє{2,4,...,2z},інакше- невизначена, є ЧРФ за ТЧ. За теоремою 7.4.3 існує таке n, що h(n, x)=φn(x) для всіх x. Тоді φn(x) =x якщо х непарне або хє{2,4,...,2z},інакше- невизначена.Звідси маємо Dn=En={x | x непарне}υ{2, 4, ..., 2п}.
Приклад 6. Існує nєN таке, що Dп=Еп={x | φn(3x)↓}۸{x | x парне}. Функція h(z, x) = x якщо х=z,інакше- невизначена, є ЧРФ за ТЧ. За теоремою 7.4.3 існує таке n, що h(n, x)=φn(x) для всіх x. Тоді маємо φn(x) = Звідси отримуємо Dn=Еn={x | φn(3x)↓}۸{x | x парне}.
Приклад 7. Існує РФ g(x) така: Dg(x)=Eg(x)={3g(x)+2^x} для всіх хєN. Функція h(t, x, y)=у якщо у=3t+2^x,інакше- невизначена, є ЧРФ за ТЧ. За s-m-n-теоремою існує РФ s(t, x) така: h(t, x, y)=φs(t,x)(y) для всіх t, x, yєN. За теоремою 7.4.1 існує РФ g така, що φg(x)=φs(g(x),x) для всіх xєN. Тоді φg(x)(у)=φs(g(x),x)(у)=h(g(x), x, y)=у якщо у=3g(x)+2^x,інакше-невизначена. Звідси для кожного xєN маємо Dg(x)=Eg(x)={3g(x)+2x}.
Теорема 4.4. Для кожної РФ f(x) існує строго монотонна РФ λ(x) така, що для кожного nєN маємо φα(n) =φf(α(n)). Наслідок. Для кожної РФ f(x) та для кожного kєN існує nєN таке, що n>k та φn=φf(n). Розглянуті нами ефективні нумерації ЧРФ неоднозначні. Одно-значні ефективні нумерації ЧРФ існують [6], але немає в певному смислі "природних" однозначних ефективних нумерацій ЧРФ.
Теорема 4.5. Нехай f(x)- строго монотонна тотальна функція така, що з умови m≠n випливає φf(m)≠φf(n) , причому f(n) є найменшим індексом функції φf(n) . Тоді функція f не є ЧРФ.
Функція Гьоделя ред.
Γ(x,y) = mod(l(x), 1+(y+1)⋅ r(x)). Дозволяє кодувати довільну скінченну послідовність натуральних чисел b0, b1, ... , bn. Для кожної такої послідовності існує t таке, що Γ(t,i)=bi, для всіх i ∈ {0,1,...n}.
Теорема про елімінацію примітивної рекурсії ред.
Використання функції Гьоделя дає змогу промоделювати операцію примітивної рекурсії операціями суперпозиції та мінімізації.