Нумерації

Кодування множини A на множині B — це ін'єктивне та сюр'єктивне відображення φ: А→В таке, що існують алгоритми ℵ та ℜ:

• для кожного а∈А ℵ(а)∈φ (а);
• для кожного b∈B ℜ(b) = φ-1(b).

Нумерацією множини А назвемо сюр'єктивне функціональне відображення ξ : N →А. Однозначною нумерацією множини А назвемо бієктивне відображення ξ : N →А.

Нумерація ξ : N→А ефективна, якщо існують алгоритми ℵ та ℜ:

• для кожного а∈А ℵ(а)∈ξ–1(а);
• для кожного n∈N ℜ(n) = ξ(n).

Таким чином, ξ : N→А – ефективна нумерація ⇔ ξ–1: А→N – кодування А на N.

Введемо однозначні ефективні нумерації пар та n-ок натуральних чисел, які називаються канторовими нумераціями.

${\displaystyle (u,\ v)\Leftrightarrow x+y<u+v\ \lor \ (x+y=u+v\ \land \ x<u)}$

Всі пари натуральних чисел розташуємо в послідовність так: пара (x, y) передує парі зображеній на малюнку

Номер пари (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 зв'язaні тотожностями:

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).

Всi пари натуральних чисел розташуємо в послiдовнiсть так: пара (x, y) передує парі (u, v)↔x+y<u+v або (x+y = u+v та x<y).

Номер пари (x, y) в такiй послiдовностi позначають C(x, y) та називають канторовим номером пари (x, y).

Неважко переконатись, що C(x, y) = [(x+y+1)*(x+y)/2]+x

Лiву та праву компоненти пари з номером n позначають вiдповiдно l(n) та r(n). Функцiї l(n) та r(n) називають вiдповiдно лiвою та правою координатними функцiями.

Функцiя C(x, y) задає бiєкцiю N×N→N, пара функцiй (l(n), r(n)) задає бiєкцiю N→N×N.

При цьому функцiї C,l та r зв’язaнi такими тотожностями: C(l(n), r(n)=n; l(C(x, y))=x; r(C(x, y))=y. Маючи нумерацiю пар натуральних чисел, можна ввести нумерацiю n-ок натуральних чисел для довiльного n>2:

Cn(x1, x2,..., xn)=C^n-1(C(x1, x2), x3,..., xn)=C(...С(C(x1, x2), x3),...), xn).

Координатнi функцiї Cn1 , ..., Cnn вводимо так:

Нехай Cn(x1, x2,..., xn)=m; тоді Cn1(m)=x1; Cn2(m)=x2; ... , Cnn(m)=xn.

Для функцiй Cn, Cn1 , ..., Cnn справджуються такi тотожностi:

Cп(Cn1(x), ..., Cnn(x))=x; Cnk(Cп(x1, x2,..., xn))=xk, 1≤k≤n.

Теорема 1.1. 1) Функцiї C(x, y), l(n) та r(n) є ПРФ. 2) Функцiї Cn, Cn1 , ..., Cnn є ПРФ.

Приклад 1. Знайдемо l(100) та r(100). Для х=l(100) та у=r(100) маємо рівняння С(х, у)=100. Нехай х+у=р. Тоді р є найбільшим натуральним числом, для якого р*(р+1)≤2*100. Звідси р=13. Маємо х+у=13, х=100-[(1314)/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. Задамо однозначну ефективну нумерацiю всiх скiнченних послiдовностей натуральних чисел на основі наступного кодування k:Ų,k≥0,N^k→N таких послідовностей: k(Ø)=0; k(а1, ..., ап)= C(C^n(а1, ..., аn), n-1)+1. Зрозуміло, що таке відображення бієктивне. Тепер обернене відображення η=k^-1 - шукана однозначна нумерацiя.

Приклад 4. Однозначну ефективну нумерацiю всiх скiнченних послiдовностей натуральних чисел можна задати на основі такого кодування ò:Ų,k≥0,N^k→N всіх скiнченних послiдовностей: k(Ø)=0; k(а1, ..., аn)=2^a1+2^A1+a2+...+2^a1+a2+...+an+n-1. Бiєктивнiсть вiдображення ò випливає iз однозначностi подання кожного натурального числа в двiйковiй системi числення. Обернене відображення α=ò^-1 -шукана однозначна нумерацiя.

Приклад 5. Однозначну ефективну нумерацiю всiх непорожніх скiнченних послiдовностей натуральних чисел задамо на основі кодування ʋ:Ų,k≥0,N^k→N, що є модифікацією кодування ò: ʋ(а1, ..., аn)=2^a1+2^a1+a2+1+...+2^a1+a2+...+an+n-1-1. Обернене відображення ξ=ʋ^-1 - шукана однозначна нумерацiя.

Приклад 6. Ефективну нумерацiю Φ множини формул довiльної мови 1-го порядку із злiченним алфавiтом введемо таким чином. Занумеруємо множини предметних імен x0, x1, ..., константних символiв c0, c1, ... , функцiональних символiв f0, f1, ... та предикат-них символiв p0, p1,... . Кодування k термiв та формул.задамо так:

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льної формули Ф вважатимемо її код К(Ф). Всi тi натуральнi числа, якi не є кодами формул, вважатимемо номером формули x0=x0 . Зрозуміло, що так введена нумерація Ф неоднозначна. Формулу з номером n позначатимемо Фn . Кодувати довiльну скiнченну послiдовнiсть натуральних чисел. дозволяє також функція Гьоделя Г(x, y) = mod(l(x), 1+(y+1)-r(x)). З визначення випливає, що Г(x, y) є ПРФ.

Теорема 1.2 (про основну властивість функції Гьоделя). Для довiльної скiнченної послiдовностi натуральних чисел b0, b1, ..,bn існує натуральне число t таке, що Г(t, i)=bi для всiх iє{0,...,n}.

Використання функції Гьоделя дає змогу промоделювати опера-цiю примiтивної рекурсiї операціями суперпозиції та мінімізації:

Теорема 1.3. Функцiя f=R(g, h) може бути отримана iз функцiй g, h, базових функцiй і функцiй +,× за допомогою скiнченної кiлькостi застосувань операцiй S^n+1 та М. Наслiдок. Клас ЧРФ спiвпадає з класом функцiй, отриманих із функцій о, s, I(m,n) , +, × за допомогою операцiй S^n+1 та M.

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

Приклад 1. Однозначну ефективну нумерацiю всiх МНР-програм задамо на основi кодування МНР-програм як скiнченних послiдов-ностей команд МНР. Кодування команд Ө задамо так:

Ө(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.

Зрозумiло, що Ө -бiєктивне вiдображення множини всiх команд МНР на N. Використовуючи розглянуту вище бiєкцiю ν:Ṵ N^k→N, k>=1 задамо кодування Ί всiх МНР-програм так. Якщо P - МНР-програма I1,I2...Iк , то Ί(P) = ν(Ө(I1),..., Ө(Ik)). Відображення ν та Ө бiєктивнi, тому Ί теж бiєкцiя. Тодi γ=Ί^-1 - шукана однозначна нумерацiя. Нумерацiя γ ефективна. Справдi, за кожною МНР-програмою P ефективно обчислюється її номер Ί(P). З iншого боку, за кожним nєN ефективно визначається МНР-програма P=γ(n). Справді, спочатку подамо число n+1 як суму зростаючих степенiв числа 2: n+1=2^b1+2^b2+...+2^bk,де 0<b1<...<bk. Далi визначимо послiдовнiсть чисел a1, ..., ak: a1=b1, ai+1=bi+1-bi-1 для 1<i<k. Тепер за числами a1, ..., ak як за кодами команд МНР вiдновимо вiдповiднi команди. Послiдовнiсть цих команд 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, звiдки a1=10,a2=12-10-1 = 1. Але 10=2+4*C(1,0), тому P5119 така:

1) T(1,0)

2) S(0).

Приклад 2. Ефективну нумерацiю всiх МТ задамо на основi кодування МТ. Кожну МТ можна задати послiдовнiстю її команд такою, що 1-а команда мiстить в лiвiй частинi символ q0 , остання команда мiстить в правiй частинi символ q*. Таке завдання неоднозначне, бо множину команд МТ можна впорядкувати у виглядi послiдовностi з вищевказаною властивiстю багатьма способами. Тому наша нумерацiя МТ неоднозначна.

Занумеруємо внутрiшнi стани МТ та символи стрiчки. Нехай 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.

Таке μ є бiєктивним вiдображенням множини всiх можливих команд машин Тьюрiнга на N. Використовуючи розглянуту вище бiєкцiю ν:Ṵ N^k→N, k>=1 визначимо код МТ M, заданої послiдовнiстю команд I1,I2...Iк , таким чином: p(M)=ν(μ(I1),...,μ(Ik)). Але ν та μ бiєктивнi, тому p теж бiєкцiя. Тодi γ=p^-1 - шукана однозначна нумерацiя послiдовностей команд МТ, але неоднозначна нумерацiя всiх МТ. Неважко переконатись, що така нумерацiя ефективна.

Приклад 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. Ефективну нумерацiю Ѱ всiх m-арних ЧРФ задамо на основi кодування γ операторних термiв алгебри ЧРФ. Завдання ЧРФ операторними термами неоднозначне, бо кожну ЧРФ можна описати нескiнченною кiлькiстю рiзних ОТ, тому нумерацiя Ѱ неоднозначна.

Кодування Ѱ операторних термiв задамо так:

γ(о) = 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 значенням цього ОТ є функцiя f. Числа, якi не є кодами ОТ, та коди тих ОТ, якi не задають ЧРФ, вважаємо номерами всюди невизначеної функцiї fø. Зрозумiло, що за кожною ЧРФ можна ефективно знайти її номер. З iншого боку, за кожним nєN ефективно визначається ЧРФ f така, що Ѱ(n)=f : за n як за кодом будуємо ОТ; якщо ОТ з таким кодом iснує та задає ЧРФ, то Ѱ(n)-саме така ЧРФ f ; якщо ОТ з таким кодом iснує, але не задає ЧРФ, то Ѱ(n)=fø; якщо ОТ з таким кодом не iснує, то Ѱ(n)= fø. Отже,Ѱ є ефективною нумерацiєю всiх ЧРФ.

Приклад 3.1. Знайдемо код ОТ алгебри п-арних ЧРФ для всюди невизначеної функцiї f. Згадуючи приклад 9 розділу 6.6, для fø маємо ОТ М(s), звідки γ(M(s))=4-γ(s)+3=4-4+3=19.

Приклад 4. Ефективну нумерацiю всiх ПРФ задамо на основi кодування операторних термiв алгебри ПРФ. Така нумерацiя ПРФ неоднозначна. Кодування Π ОТ алгебри ПРФ задамо так:

γ(о)=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 є кодом якогось ОТ та значенням цього ОТ є функцiя f. Числа, якi не є кодами ОТ, та коди тих ОТ, якi не задають ПРФ, вважаємо номерами функцiї о.

Приклад 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. Ефективну нумерацiю всiх програмованих на N n-арних функцiй задамо на основi кодування операторних термiв ППА-Ar-N. Зрозуміло, що така нумерацiя неоднозначна. Єдина iстотна вiдмiн-нiсть вiд нумерацiї прикладу 3 - iнше кодування γ операторних термiв ППА-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. Ефективну нумерацiю ₰^n всiх МНР-обчислюваних функцiй фіксованої арності n задамо на основi кодування МНР-програм (приклад 1). Hомером n-арної МНР-обчислюваної функцiї f буде код МНР-програми, яка обчислює функцію f. Кожна n-арна МНР-обчислювана функцiя може задаватися нескiнченною кiлькiстю рiзних МНР-програм, тому така нумерацiя неоднозначна.

Приклад 7. Ефективну нумерацiю всiх МНР-обчислюваних функцiй можна ввести на основі кодування МНР-програм. Hомером n-арної функцiї f буде число С(k, n), де k - код МНР-програми для f.

Приклад 8. Ефективну нумерацiю всiх МТ-обчислюваних функцiй фіксованої арності п задамо на основi кодування МТ. Номером n-арної МТ-обчислюваної функцiї f буде код МТ, яка обчислює f. Кожна n-арна МТ-обчислювана функцiя може задаватися нескiнчен-ною кiлькiстю рiзних МТ, тому така нумерацiя неоднозначна.

Приклад 9. Ефективну нумерацiю всiх обчислюваних за Тьюрiнгом функцiй введемо на основі кодування МТ. Hомером МТ-обчислю-ваної функцiї f арності n буде число С(k, n), де k - код МТ для f.

В силу спiвпадiння класiв ЧРФ, програмованих на N функцiй, МНР-обчислюваних функцiй та МТ-обчислюваних функцiй, нумерацiї прикладiв 5, 6 та 8 розділу 7.2 можна розглядати як ефек-тивні нумерацiї всiх n-арних ЧРФ для фіксованого п, а нумерацiї прикладiв 3, 7 та 9  як ефективні нумерацiї всiх n-арних ЧРФ.

Зафiксуємо для кожного n>=1 ефективну нумерацiю n-арних ЧРФ. Звичайно це буде нумерація на основі кодування МНР-програм (приклад 6), інколи нумерація на основі кодування МТ (приклад 8). Вказані нумерації назвемо стандартними нумераціями n-арних ЧРФ. Для стандартних нумерацій введемо наступні позначення.

n-арну ЧРФ з номером m позначатимемо ₰(m,n). У випадку n=1 вживатимемо спрощене позначення ₰m .Область визначення та область значень функцiї ₰(m,n) позначатимемо вiдповiдно D(n,m) та E(n,m). У випадку n=1 вживатимемо позначення Dm та Em. Номер функцiї назвемо також iндексом функцiї. Номер функцiї в стандартній намерації назвемо стандартним iндексом функцiї.

Нумерація ξ називається Гьодельовою, якщо існують рекурсивні функції f та g такі:

- для кожного тєN ₰(n,m)=ξf(m);

- для кожного kєN ξk =₰(n,g(k)) .

Це означає, що існує пара алгоритмів, перший з яких за стандартним індексом функції знаходить її ξ-індекс, а другий за ξ-індексом функції знаходить її стандартний індекс.

Нехай F - деякий клас функцій вигляду Х→Y, для якого задана нумерація ξ: N→F. З кожною такою нумерацією ξ зв’язана функція U: N×Х→Y, що визначається умовою U(n,х)=ξn(х). Таку функцію и називають спряженою з нумерацією ξ. Нумерація називається обчислюваною, якщо спряжена з нею функція є ЧРФ. Для довiльного класу n-арних функцiй F клас всiх функцiй iз F фіксованої арності т будемо позначати Fт.

Функцiя U(y, x1, ..., xn) унiверсальна для класу Fn, якщо:

- для кожного значення m функцiя U(y, x1, ..., xп)єFn;

- для кожної fєFn iснує таке m, що f(x1, ..., xn)=U(m, x1, ..., xn) для всiх значень x1, ..., xn .

Теорема 3.1. Нехай T - деякий клас тотальних п-арних функцiй на N, який мiстить функцiї о, s, I та замкнений вiдносно суперпозицiї. Нехай функцiя u унiверсальна для Tп. Тодi uєT.

Наслiдок 1. Функцiя, унiверсальна для класу n-арних РФ, не є ЧРФ.

Наслiдок 2. Функцiя, унiверсальна для класу n-арних ПРФ, не є ПРФ.

Теорема 3.2. Існує РФ, унiверсальна для класу n-арних ПРФ.

Наслiдок 1. Існує РФ, яка не є ПРФ.

Наслiдок 2. Для вiдповiдних класiв функцiй маємо строгi включення ПРФ උ РФ උ ЧРФ.

Теорема 3.3. Існує ЧРФ, унiверсальна для класу n-арних ЧРФ.

Такою буде функція U(у, x1, ..., xn) = φ(n,m) (x1, ..., xn). МНР-програма, яка обчислює унiверсальну ЧРФ, називається унiверсальною МНР-програмою. Унiверсальна програма декодує довiльне число y в програму Py , а далi вона моделює роботу Py . Тому така унiверсальна програма може бути задана в явному виглядi. Отже, можна конструктивно знайти iндекс k унiверсальної функцiї u в стандартній нумерацiї (n+1)-арних ЧРФ, тобто u суть функцiя φ(n+1,k).

Машина Тьюрiнга, яка обчислює унiверсальну ЧРФ, називається унiверсальною МТ. Таку МТ, здатну моделювати роботу довiльної МТ за її кодом, теж можна задати в явному виглядi. Для кожного фiксованого значення а1, ..., ат аргументiв x1, ..., xт (m+n)-арна ЧРФ s(m,n)(x1, ..., xт, у1, ..., уп). стає n-арною ЧРФ φ(n,k)(у1, ..., уп). Її iндекс k можна ефективно знайти за z та а1, ..., аm. Це означає, що iснує (m+1)-арна РФ, яку традицiйно позначають s(m,n), що обчислює цей iндекс:

Теорема 3.4 (s-m-n-теорема). Для довiльних m, n>1 iснує (m+1)-арна РФ s (z, x1, ..., xm) така, що для всiх z, x1, ..., xт, у1, ..., уп маємо φ(m+n,z) (x1, ..., xт, у1, ..., уm) = φ(m,s(m,n))(у1, ..., уm).

Приклад 1. Залежнiсть функцiї s(m,n) вiд n можна зняти, якщо для завдання ЧРФ використати МТ. Справді, за z визначаємо МТ з кодом z для функцiї φ(m+n,z). Задамо нову МТ M, яка злiва вiд початкового вмiсту стрiчки дописує слово |x1#|x2#...#|xm, a далi моделює роботу МТ з кодом z. Така МТ M при входi |y1#|y2#...#|ym обчислює n-арну функцiю φ(n,k), причому k - код МТ M, M - не залежить вiд n .

Теорема 3.5 (s-m-n-теорема в спрощенiй формi). Для кожної ЧРФ f(x1, ..., xm, у1, ..., уn) iснує РФ s(x1, ..., xm) така, що для всiх x1, ..., xт, у1, ..., уn маємо f(x1, ..., xm, у1, ..., уn) = φ(n,s)(у1, ..., уn). При m=n=1 спрощена s-m-n-теорема формулюється так:

Теорема 3.6. Для кожної ЧРФ f(x, y) iснує РФ s(x) така, що для всiх значень 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) (у). Зафіксуємо х. Mаємо ує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 . Звідси Еs(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)(у). Зафіксуємо х. Mаємо уєDt(x)↔φt(x) (у)↓↔f(x, y)↓↔уєEx . Звідси 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)=Е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. За побудовою функції f маємо Ds(x,y)=Еs(x,y). Тепер zєЕs(x,y)↔zєDs(x,y)↔φs(x,y) (z)↓↔f(x, y, z)↓↔zєDx٨Dy . Звідси отримуємо Ds(x,y)=Еs(x,y)=Dx٨Dy .

Теорема 4.1. Нехай f - (n+1)-арна РФ. Тодi iснує n-арна РФ g така, що φ g(x1,x2,...,xn)=φ f(g(x1,x2,...,xn),x1,x2,...,xn) для всiх значень x1, ..., xп. Переформулюємо теорему 7.4.1 для випадку n=0.

Теорема 4.2. Нехай f(x)-РФ. Тодi iснує nєN таке, що φn = φf(n). Первісне формулювання самого С.Кліні теореми про нерухому точку має наступний вигляд:

Теорема 4.3. Нехай h(z, x)-ЧРФ. Тодi iснує nєN таке, що для всiх x маємо h(n, x)=φ n(x). Теорему Клiнi про нерухому точку краще називати теоремою про псевдонерухому точку. Справдi, умова φ n=φ f(n) зовсім не означає, що n=f(n), a свiдчить тiльки про те, що n та f(n)-iндекси однієї i тої ж ЧРФ.

Приклад 1. МНР-програму P назвемо самотворною, якщо для довiльного xєN маємо P(x)↓τ(P), де τ(P) -код програми P. На перший погляд, таких програм бути не може, бо для побудови P треба знати τ(P) тобто саму програму P. Проте МНР-програма P така, що P(x)↓τ(P) для всiх значень x, таки існує. Справді, вiзьмемо функцiю h(z, x)=z. За теоремою 7.4.3 iснує таке n, що для всiх x h(n, x)=φn(x). Отже, φn(x)=h(n, x)=n для всiх x. Тому програма P з кодом n -шукана.

Приклад 2. Існує nєN таке, що для всiх x маємо φn(x)=2n+x^3n. Вiзьмемо функцiю h(z, x)=2z+x3z. За теоремою 7.4.3 iснує таке n, що для всiх x h(n, x)=φn(x). Отже, φn(x)=h(n, x)=2n+x3n для всiх x.

Приклад 3. Існує nєN таке, що Dn=En={n}. Вiзьмемо функцiю h(z, x)=x якщо х=z,iнакше - невизначена. Така h є ЧРФ. За теоремою 7.4.3 iснує таке n, що для всiх x маємо h(n, x)=φn(x). Тоді φn(x)=x якщо х=n,iнакше- невизначена. Звідси Dn=Еn={n}.

Приклад 5. Існує nєN таке, що Dп=En=N\{n, 2n}. Вiзьмемо функцiю h(z, x)=x якщо х≠z та х≠2z,iнакше - невизначена.Така h є ЧРФ. За теоремою 7.4.3 iснує таке n, що h(n, x)=φn(x) для всiх x. Тоді φn(x)= x якщо х≠n та х≠2n,iнакше - невизначена. Звідси Dn=En=N\{n, 2n}.

Приклад 4. Існує nєN таке, що Dп=Еп={x | x непарнe}υ{2, 4, ..., 2п}. Функцiя h(z, x) = x якщо х непарне або хє{2,4,...,2z},інакше- невизначена, є ЧРФ за ТЧ. За теоремою 7.4.3 iснує таке n, що h(n, x)=φn(x) для всiх x. Тоді φn(x) =x якщо х непарне або хє{2,4,...,2z},інакше- невизначена.Звідси маємо Dn=En={x | x непарнe}υ{2, 4, ..., 2п}.

Приклад 6. Існує nєN таке, що Dп=Еп={x | φn(3x)↓}۸{x | x парнe}. Функцiя h(z, x) = x якщо х=z,iнакше- невизначена, є ЧРФ за ТЧ. За теоремою 7.4.3 iснує таке n, що h(n, x)=φn(x) для всiх x. Тоді маємо φn(x) = Звідси отримуємо Dn=Еn={x | φn(3x)↓}۸{x | x парнe}.

Приклад 7. Існує РФ g(x) така: Dg(x)=Еg(x)={3g(x)+2^x} для всіх хєN. Функція h(t, x, y)=у якщо у=3t+2^x,iнакше- невизначена, є ЧРФ за ТЧ. За 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,iнакше-невизначена. Звідси для кожного xєN маємо Dg(x)=Еg(x)={3g(x)+2x}.

Теорема 4.4. Для кожної РФ f(x) iснує строго монотонна РФ λ(x) така, що для кожного nєN маємо φα(n) =φf(α(n)). Наслiдок. Для кожної РФ f(x) та для кожного kєN iснує nєN таке, що n>k та φn=φf(n). Розглянутi нами ефективнi нумерацiї ЧРФ неоднозначнi. Одно-значнi ефективні нумерацiї ЧРФ iснують [6], але немає в певному смислi "природних" однозначних ефективних нумерацiй ЧРФ.

Теорема 4.5. Нехай f(x)- строго монотонна тотальна функцiя така, що з умови m≠n випливає φf(m)≠φf(n) , причому f(n) є найменшим iндексом функцiї φf(n) . Тодi функцiя f не є ЧРФ.

Γ(x,y) = mod(l(x), 1+(y+1)⋅ r(x)). Дозволяє кодувати довільну скінченну послідовність натуральних чисел b0, b1, ... , bn. Для кожної такої послідовності існує t таке, що Γ(t,i)=bi, для всіх i ∈ {0,1,...n}.

Використання функції Гьоделя дає змогу промоделювати операцію примітивної рекурсії операціями суперпозиції та мінімізації.

• Нумерація Геделя
• Нумерація Кантора

Нумерація Ґьоделя