Azərbaycanca
Беларускі
Dansk
Deutsch
Española
Français
Indonesia
Italiana
日本語
Қазақ
Lietuvos
Nederlands
Português
Русский
සිංහල
แบบไทย
Türkçe
Українська
中國人
United State
Afrikaans
Різні формальні моделі алгоритмів діють на різних множинах даних. Наприклад машина Тьюрінга реалізує вербальні алгоритми, а МНР-програми визначають функції натуральних аргументів і значень. Для порівняння різних формальних моделей, і переходів між ними треба кодувати елементи однієї множини елементами іншої.
Кодування
Кодування множини 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}.
Теорема про елімінацію примітивної рекурсії
Використання функції Гьоделя дає змогу промоделювати операцію примітивної рекурсії операціями суперпозиції та мінімізації.
Див. також
Посилання
Нумерація Ґьоделя
Вікіпедія, Українська, Україна, книга, книги, бібліотека, стаття, читати, завантажити, безкоштовно, безкоштовно завантажити, mp3, відео, mp4, 3gp, jpg, jpeg, gif, png, малюнок, музика, пісня, фільм, книга, гра, ігри, мобільний, телефон, android, ios, apple, мобільний телефон, samsung, iphone, xiomi, xiaomi, redmi, honor, oppo, nokia, sonya, mi, ПК, web, Інтернет
Rizni formalni modeli algoritmiv diyut na riznih mnozhinah danih Napriklad mashina Tyuringa realizuye verbalni algoritmi a MNR programi viznachayut funkciyi naturalnih argumentiv i znachen Dlya porivnyannya riznih formalnih modelej i perehodiv mizh nimi treba koduvati elementi odniyeyi mnozhini elementami inshoyi KoduvannyaKoduvannya mnozhini A na mnozhini B ce in yektivne ta syur yektivne vidobrazhennya f A V take sho isnuyut algoritmi ℵ ta ℜ dlya kozhnogo a A ℵ a f a dlya kozhnogo b B ℜ b f 1 b NumeraciyiNumeraciyeyu mnozhini A nazvemo syur yektivne funkcionalne vidobrazhennya 3 N A Odnoznachnoyu numeraciyeyu mnozhini A nazvemo biyektivne vidobrazhennya 3 N A Numeraciya 3 N A efektivna yaksho isnuyut algoritmi ℵ ta ℜ dlya kozhnogo a A ℵ a 3 1 a dlya kozhnogo n N ℜ n 3 n Takim chinom 3 N A efektivna numeraciya 3 1 A N koduvannya A na N Kantorovi numeraciyiVvedemo odnoznachni efektivni numeraciyi par ta n ok naturalnih chisel yaki nazivayutsya kantorovimi numeraciyami u v x y lt u v x y u v x lt u displaystyle u v Leftrightarrow x y lt u v lor x y u v land x lt u Vsi pari naturalnih chisel roztashuyemo v poslidovnist tak para x y pereduye pari zobrazhenij na malyunku Nomer pari x y v takij poslidovnosti poznachayut C x y ta nazivayut kantorovim nomerom pari x y Nevazhko perekonatis sho C x y x y 1 x y 2 x Os yiyi tabulyuvannya Numeraciya racionalnih chisel 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 Livu ta pravu komponenti pari z nomerom n poznachayut vidpovidno l n ta r n Funkciyi l n ta r n nazivayut vidpovidno livoyu ta pravoyu koordinatnimi funkciyami Podibna numeraciya zastosovuvalas pri dovedenni zlichennosti mnozhini racionalnih chisel Funkciyi C l ta r zv yazani totozhnostyami C l n r n n l C x y x r C x y y Mayuchi numeraciyu par naturalnih chisel mozhna vvesti numeraciyu n ok naturalnih chisel dlya dovilnogo n gt 2 Cn x1 x2 xn Cn 1 C x1 x2 x3 xn C S C x1 x2 x3 xn Vsi pari naturalnih chisel roztashuyemo v poslidovnist tak para x y pereduye pari u v x y lt u v abo x y u v ta x lt y Nomer pari x y v takij poslidovnosti poznachayut C x y ta nazivayut kantorovim nomerom pari x y Nevazhko perekonatis sho C x y x y 1 x y 2 x Livu ta pravu komponenti pari z nomerom n poznachayut vidpovidno l n ta r n Funkciyi l n ta r n nazivayut vidpovidno livoyu ta pravoyu koordinatnimi funkciyami Funkciya C x y zadaye biyekciyu N N N para funkcij l n r n zadaye biyekciyu N N N Pri comu funkciyi C l ta r zv yazani takimi totozhnostyami C l n r n n l C x y x r C x y y Mayuchi numeraciyu par naturalnih chisel mozhna vvesti numeraciyu n ok naturalnih chisel dlya dovilnogo n gt 2 Cn x1 x2 xn C n 1 C x1 x2 x3 xn C S C x1 x2 x3 xn Koordinatni funkciyi Cn1 Cnn vvodimo tak Nehaj Cn x1 x2 xn m todi Cn1 m x1 Cn2 m x2 Cnn m xn Dlya funkcij Cn Cn1 Cnn spravdzhuyutsya taki totozhnosti Sp Cn1 x Cnn x x Cnk Sp x1 x2 xn xk 1 k n Teorema 1 1 1 Funkciyi C x y l n ta r n ye PRF 2 Funkciyi Cn Cn1 Cnn ye PRF Priklad 1 Znajdemo l 100 ta r 100 Dlya h l 100 ta u r 100 mayemo rivnyannya S h u 100 Nehaj h u r Todi r ye najbilshim naturalnim chislom dlya yakogo r r 1 2 100 Zvidsi r 13 Mayemo h u 13 h 100 13 14 2 9 y 13 9 4 Otzhe l 100 9 ta r 100 4 Priklad 2 Rozv yazhemo rivnyannya C4 x y z v 207 Za viznachennyam mayemo S S S x y z v 207 Nehaj S S x y z a mayemo C a v 207 Nehaj a v r Todi r ye najbilshim naturalnim chislom dlya yakogo r r 1 2 207 Zvidsi r 19 zvidki a 17 ta v 2 Teper mayemo S S x y z 17 Nehaj S x y b todi C b z 17 Nehaj b z q Todi q ye najbilshim naturalnim chislom dlya yakogo q q 1 2 17 Zvidsi q 5 zvidki b 2 ta z 3 Mayemo C x y 2 zvidki x 1 ta y 0 Priklad 3 Zadamo odnoznachnu efektivnu numeraciyu vsih skinchennih poslidovnostej naturalnih chisel na osnovi nastupnogo koduvannya k Ų k 0 N k N takih poslidovnostej k O 0 k a1 ap C C n a1 an n 1 1 Zrozumilo sho take vidobrazhennya biyektivne Teper obernene vidobrazhennya h k 1 shukana odnoznachna numeraciya Priklad 4 Odnoznachnu efektivnu numeraciyu vsih skinchennih poslidovnostej naturalnih chisel mozhna zadati na osnovi takogo koduvannya o Ų k 0 N k N vsih skinchennih poslidovnostej k O 0 k a1 an 2 a1 2 A1 a2 2 a1 a2 an n 1 Biyektivnist vidobrazhennya o viplivaye iz odnoznachnosti podannya kozhnogo naturalnogo chisla v dvijkovij sistemi chislennya Obernene vidobrazhennya a o 1 shukana odnoznachna numeraciya Priklad 5 Odnoznachnu efektivnu numeraciyu vsih neporozhnih skinchennih poslidovnostej naturalnih chisel zadamo na osnovi koduvannya ʋ Ų k 0 N k N sho ye modifikaciyeyu koduvannya o ʋ a1 an 2 a1 2 a1 a2 1 2 a1 a2 an n 1 1 Obernene vidobrazhennya 3 ʋ 1 shukana odnoznachna numeraciya Priklad 6 Efektivnu numeraciyu F mnozhini formul dovilnoyi movi 1 go poryadku iz zlichennim alfavitom vvedemo takim chinom Zanumeruyemo mnozhini predmetnih imen x0 x1 konstantnih simvoliv c0 c1 funkcionalnih simvoliv f0 f1 ta predikat nih simvoliv p0 p1 Koduvannya k termiv ta formul zadamo tak 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 ḷF 7 C k K F 4 K ٧FPS 7 C K F K PS 5 K ExkF 7 C k K F 6 Nomerom indeksom dovilnoyi formuli F vvazhatimemo yiyi kod K F Vsi ti naturalni chisla yaki ne ye kodami formul vvazhatimemo nomerom formuli x0 x0 Zrozumilo sho tak vvedena numeraciya F neodnoznachna Formulu z nomerom n poznachatimemo Fn Koduvati dovilnu skinchennu poslidovnist naturalnih chisel dozvolyaye takozh funkciya Godelya G x y mod l x 1 y 1 r x Z viznachennya viplivaye sho G x y ye PRF Teorema 1 2 pro osnovnu vlastivist funkciyi Godelya Dlya dovilnoyi skinchennoyi poslidovnosti naturalnih chisel b0 b1 bn isnuye naturalne chislo t take sho G t i bi dlya vsih iye 0 n Vikoristannya funkciyi Godelya daye zmogu promodelyuvati opera ciyu primitivnoyi rekursiyi operaciyami superpoziciyi ta minimizaciyi Teorema 1 3 Funkciya f R g h mozhe buti otrimana iz funkcij g h bazovih funkcij i funkcij za dopomogoyu skinchennoyi kilkosti zastosuvan operacij S n 1 ta M Naslidok Klas ChRF spivpadaye z klasom funkcij otrimanih iz funkcij o s I m n za dopomogoyu operacij S n 1 ta M Efektivni numeraciyi formalnih modelej algoritmiv ta AOFRozglyanemo prikladi efektivnih numeracij formalnih modelej algoritmiv ta algoritmichno obchislyuvanih funkcij Priklad 1 Odnoznachnu efektivnu numeraciyu vsih MNR program zadamo na osnovi koduvannya MNR program yak skinchennih poslidov nostej komand MNR Koduvannya komand Ө zadamo tak Ө Z n 4 n Ө S n 4 n 1 Ө T t n 4 S m n 2 Ө J m n q 1 4 S S m n q 3 Zrozumilo sho Ө biyektivne vidobrazhennya mnozhini vsih komand MNR na N Vikoristovuyuchi rozglyanutu vishe biyekciyu n Ṵ N k N k gt 1 zadamo koduvannya I vsih MNR program tak Yaksho P MNR programa I1 I2 Ik to I P n Ө I1 Ө Ik Vidobrazhennya n ta Ө biyektivni tomu I tezh biyekciya Todi g I 1 shukana odnoznachna numeraciya Numeraciya g efektivna Spravdi za kozhnoyu MNR programoyu P efektivno obchislyuyetsya yiyi nomer I P Z inshogo boku za kozhnim nyeN efektivno viznachayetsya MNR programa P g n Spravdi spochatku podamo chislo n 1 yak sumu zrostayuchih stepeniv chisla 2 n 1 2 b1 2 b2 2 bk de 0 lt b1 lt lt bk Dali viznachimo poslidovnist chisel a1 ak a1 b1 ai 1 bi 1 bi 1 dlya 1 lt i lt k Teper za chislami a1 ak yak za kodami komand MNR vidnovimo vidpovidni komandi Poslidovnist cih komand i ye shukanoyu MNR programoyu P MNR programu z kodom n poznachatimemo Pn Priklad 1 1 Znajdemo kod MNR programi P yaka obchislyuye binarnu funkciyu h u Vikoristayemo priklad 3 rozdilu 2 1 Mayemo 1 J 1 2 5 Ө J 1 2 5 4 S S 1 2 4 3 4 S 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 S S 0 0 0 3 4 S 0 0 3 4 0 3 3 Teper I P n 295 1 9 3 2 295 2 297 2 307 2 311 1 Priklad 1 2 Znajdemo P5119 g 5119 Mayemo 5119 1 5120 2 10 2 12 zvidki a1 10 a2 12 10 1 1 Ale 10 2 4 C 1 0 tomu P5119 taka 1 T 1 0 2 S 0 Priklad 2 Efektivnu numeraciyu vsih MT zadamo na osnovi koduvannya MT Kozhnu MT mozhna zadati poslidovnistyu yiyi komand takoyu sho 1 a komanda mistit v livij chastini simvol q0 ostannya komanda mistit v pravij chastini simvol q Take zavdannya neodnoznachne bo mnozhinu komand MT mozhna vporyadkuvati u viglyadi poslidovnosti z vishevkazanoyu vlastivistyu bagatma sposobami Tomu nasha numeraciya MT neodnoznachna Zanumeruyemo vnutrishni stani MT ta simvoli strichki Nehaj Q q1 qf T a1 am Koduvannya m komand MT zadamo tak m qiaj qka1 3 C 4 i j k l m qiaj qka1L 3 C 4 i j k l 1 m qiaj qka1R 3 C 4 i j k l 2 Take m ye biyektivnim vidobrazhennyam mnozhini vsih mozhlivih komand mashin Tyuringa na N Vikoristovuyuchi rozglyanutu vishe biyekciyu n Ṵ N k N k gt 1 viznachimo kod MT M zadanoyi poslidovnistyu komand I1 I2 Ik takim chinom p M n m I1 m Ik Ale n ta m biyektivni tomu p tezh biyekciya Todi g p 1 shukana odnoznachna numeraciya poslidovnostej komand MT ale neodnoznachna numeraciya vsih MT Nevazhko perekonatis sho taka numeraciya efektivna Priklad 2 1 Znajdemo kod MT M yaka obchislyuye binarnu funkciyu h u Vvazhayemo a0 ʆ a1 a2 ta q q2 Vikoristayemo priklad 1 rozdilu 2 2 Mayemo q0 q0 R m q0 q0 R 3 C 4 0 1 0 1 2 3 C 2 1 2 3 8 2 26 q0 q0 R m q0 q0 R 3 C 4 0 2 0 1 2 3 C 9 1 2 3 64 2 194 q0ʆ q1ʆL m q0ʆ q1ʆL 3 C 4 0 0 1 0 1 3 C 1 0 1 3 2 1 7 q1 q ʆ m q1 q ʆ 3 C 4 1 1 2 0 3 C 25 0 3 350 1050 Teper p M n 26 194 7 1050 2 26 2 221 2 229 2 1280 1 Priklad 3 Efektivnu numeraciyu Ѱ vsih m arnih ChRF zadamo na osnovi koduvannya g operatornih termiv algebri ChRF Zavdannya ChRF operatornimi termami neodnoznachne bo kozhnu ChRF mozhna opisati neskinchennoyu kilkistyu riznih OT tomu numeraciya Ѱ neodnoznachna Koduvannya Ѱ operatornih termiv zadamo tak g o 0 g s 4 g I m n 4 C n m 2 g S n 1 t0 t1 tn 4 C Cn 1 g t0 g t1 g tn n 1 1 g R t0 t1 4 C g t0 g t1 2 g M t 4 g t 3 Chislo nyeN vvazhayemo nomerom ChRF f yaksho n ye kodom yakogos OT i znachennyam cogo OT ye funkciya f Chisla yaki ne ye kodami OT ta kodi tih OT yaki ne zadayut ChRF vvazhayemo nomerami vsyudi neviznachenoyi funkciyi fo Zrozumilo sho za kozhnoyu ChRF mozhna efektivno znajti yiyi nomer Z inshogo boku za kozhnim nyeN efektivno viznachayetsya ChRF f taka sho Ѱ n f za n yak za kodom buduyemo OT yaksho OT z takim kodom isnuye ta zadaye ChRF to Ѱ n same taka ChRF f yaksho OT z takim kodom isnuye ale ne zadaye ChRF to Ѱ n fo yaksho OT z takim kodom ne isnuye to Ѱ n fo Otzhe Ѱ ye efektivnoyu numeraciyeyu vsih ChRF Priklad 3 1 Znajdemo kod OT algebri p arnih ChRF dlya vsyudi neviznachenoyi funkciyi f Zgaduyuchi priklad 9 rozdilu 6 6 dlya fo mayemo OT M s zvidki g M s 4 g s 3 4 4 3 19 Priklad 4 Efektivnu numeraciyu vsih PRF zadamo na osnovi koduvannya operatornih termiv algebri PRF Taka numeraciya PRF neodnoznachna Koduvannya P OT algebri PRF zadamo tak g o 0 g s 3 g I m n 3 C n m 2 g S n 1 t0 t1 tn 3 C Cn 1 g t0 g t1 g tn n 1 1 g R t0 t1 3 C g t0 g t1 2 Chislo nyeN vvazhayemo nomerom PRF f yaksho n ye kodom yakogos OT ta znachennyam cogo OT ye funkciya f Chisla yaki ne ye kodami OT ta kodi tih OT yaki ne zadayut PRF vvazhayemo nomerami funkciyi o Priklad 4 1 Znajdemo kod OT algebri PRF dlya f x1 x2 x1 x2 Zgidno prikladu 2 rozdilu 6 6 dlya x1 x2 mayemo OT R I 1 1 S 2 s I 3 3 zvidki otrimuyemo g R I 1 1 S2 s I 3 3 3 C g I 1 1 g S2 s I 3 3 2 3 C 6 3 C S g s g I 3 3 0 1 2 3 C 6 3 C S 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 Priklad 5 Efektivnu numeraciyu vsih programovanih na N n arnih funkcij zadamo na osnovi koduvannya operatornih termiv PPA Ar N Zrozumilo sho taka numeraciya neodnoznachna Yedina istotna vidmin nist vid numeraciyi prikladu 3 inshe koduvannya g operatornih termiv PPA Ar N g o 0 g s 4 g 8 g 12 g 16 g I m n 4 C n m 1 g S n 1 t0 t1 tn 4 C C n 1 g t0 g t1 g tn n 1 1 g ND t0 t1 t2 4 C3 g t0 g t1 g t2 2 g N t0 t1 4 C g t0 g t1 3 Priklad 6 Efektivnu numeraciyu n vsih MNR obchislyuvanih funkcij fiksovanoyi arnosti n zadamo na osnovi koduvannya MNR program priklad 1 Nomerom n arnoyi MNR obchislyuvanoyi funkciyi f bude kod MNR programi yaka obchislyuye funkciyu f Kozhna n arna MNR obchislyuvana funkciya mozhe zadavatisya neskinchennoyu kilkistyu riznih MNR program tomu taka numeraciya neodnoznachna Priklad 7 Efektivnu numeraciyu vsih MNR obchislyuvanih funkcij mozhna vvesti na osnovi koduvannya MNR program Nomerom n arnoyi funkciyi f bude chislo S k n de k kod MNR programi dlya f Priklad 8 Efektivnu numeraciyu vsih MT obchislyuvanih funkcij fiksovanoyi arnosti p zadamo na osnovi koduvannya MT Nomerom n arnoyi MT obchislyuvanoyi funkciyi f bude kod MT yaka obchislyuye f Kozhna n arna MT obchislyuvana funkciya mozhe zadavatisya neskinchen noyu kilkistyu riznih MT tomu taka numeraciya neodnoznachna Priklad 9 Efektivnu numeraciyu vsih obchislyuvanih za Tyuringom funkcij vvedemo na osnovi koduvannya MT Nomerom MT obchislyu vanoyi funkciyi f arnosti n bude chislo S k n de k kod MT dlya f Numeraciyi n arnih ChRF Universalni funkciyi s m n teoremaV silu spivpadinnya klasiv ChRF programovanih na N funkcij MNR obchislyuvanih funkcij ta MT obchislyuvanih funkcij numeraciyi prikladiv 5 6 ta 8 rozdilu 7 2 mozhna rozglyadati yak efek tivni numeraciyi vsih n arnih ChRF dlya fiksovanogo p a numeraciyi prikladiv 3 7 ta 9 yak efektivni numeraciyi vsih n arnih ChRF Zafiksuyemo dlya kozhnogo n gt 1 efektivnu numeraciyu n arnih ChRF Zvichajno ce bude numeraciya na osnovi koduvannya MNR program priklad 6 inkoli numeraciya na osnovi koduvannya MT priklad 8 Vkazani numeraciyi nazvemo standartnimi numeraciyami n arnih ChRF Dlya standartnih numeracij vvedemo nastupni poznachennya n arnu ChRF z nomerom m poznachatimemo m n U vipadku n 1 vzhivatimemo sproshene poznachennya m Oblast viznachennya ta oblast znachen funkciyi m n poznachatimemo vidpovidno D n m ta E n m U vipadku n 1 vzhivatimemo poznachennya Dm ta Em Nomer funkciyi nazvemo takozh indeksom funkciyi Nomer funkciyi v standartnij nameraciyi nazvemo standartnim indeksom funkciyi Numeraciya 3 nazivayetsya Godelovoyu yaksho isnuyut rekursivni funkciyi f ta g taki dlya kozhnogo tyeN n m 3f m dlya kozhnogo kyeN 3k n g k Ce oznachaye sho isnuye para algoritmiv pershij z yakih za standartnim indeksom funkciyi znahodit yiyi 3 indeks a drugij za 3 indeksom funkciyi znahodit yiyi standartnij indeks Nehaj F deyakij klas funkcij viglyadu H Y dlya yakogo zadana numeraciya 3 N F Z kozhnoyu takoyu numeraciyeyu 3 zv yazana funkciya U N H Y sho viznachayetsya umovoyu U n h 3n h Taku funkciyu i nazivayut spryazhenoyu z numeraciyeyu 3 Numeraciya nazivayetsya obchislyuvanoyu yaksho spryazhena z neyu funkciya ye ChRF Dlya dovilnogo klasu n arnih funkcij F klas vsih funkcij iz F fiksovanoyi arnosti t budemo poznachati Ft Funkciya U y x1 xn universalna dlya klasu Fn yaksho dlya kozhnogo znachennya m funkciya U y x1 hp yeFn dlya kozhnoyi fyeFn isnuye take m sho f x1 xn U m x1 xn dlya vsih znachen x1 xn Teorema 3 1 Nehaj T deyakij klas totalnih p arnih funkcij na N yakij mistit funkciyi o s I ta zamknenij vidnosno superpoziciyi Nehaj funkciya u universalna dlya Tp Todi uyeT Naslidok 1 Funkciya universalna dlya klasu n arnih RF ne ye ChRF Naslidok 2 Funkciya universalna dlya klasu n arnih PRF ne ye PRF Teorema 3 2 Isnuye RF universalna dlya klasu n arnih PRF Naslidok 1 Isnuye RF yaka ne ye PRF Naslidok 2 Dlya vidpovidnih klasiv funkcij mayemo strogi vklyuchennya PRF උ RF උ ChRF Teorema 3 3 Isnuye ChRF universalna dlya klasu n arnih ChRF Takoyu bude funkciya U u x1 xn f n m x1 xn MNR programa yaka obchislyuye universalnu ChRF nazivayetsya universalnoyu MNR programoyu Universalna programa dekoduye dovilne chislo y v programu Py a dali vona modelyuye robotu Py Tomu taka universalna programa mozhe buti zadana v yavnomu viglyadi Otzhe mozhna konstruktivno znajti indeks k universalnoyi funkciyi u v standartnij numeraciyi n 1 arnih ChRF tobto u sut funkciya f n 1 k Mashina Tyuringa yaka obchislyuye universalnu ChRF nazivayetsya universalnoyu MT Taku MT zdatnu modelyuvati robotu dovilnoyi MT za yiyi kodom tezh mozhna zadati v yavnomu viglyadi Dlya kozhnogo fiksovanogo znachennya a1 at argumentiv x1 xt m n arna ChRF s m n x1 xt u1 up staye n arnoyu ChRF f n k u1 up Yiyi indeks k mozhna efektivno znajti za z ta a1 am Ce oznachaye sho isnuye m 1 arna RF yaku tradicijno poznachayut s m n sho obchislyuye cej indeks Teorema 3 4 s m n teorema Dlya dovilnih m n gt 1 isnuye m 1 arna RF s z x1 xm taka sho dlya vsih z x1 xt u1 up mayemo f m n z x1 xt u1 um f m s m n u1 um Priklad 1 Zalezhnist funkciyi s m n vid n mozhna znyati yaksho dlya zavdannya ChRF vikoristati MT Spravdi za z viznachayemo MT z kodom z dlya funkciyi f m n z Zadamo novu MT M yaka zliva vid pochatkovogo vmistu strichki dopisuye slovo x1 x2 xm a dali modelyuye robotu MT z kodom z Taka MT M pri vhodi y1 y2 ym obchislyuye n arnu funkciyu f n k prichomu k kod MT M M ne zalezhit vid n Teorema 3 5 s m n teorema v sproshenij formi Dlya kozhnoyi ChRF f x1 xm u1 un isnuye RF s x1 xm taka sho dlya vsih x1 xt u1 un mayemo f x1 xm u1 un f n s u1 un Pri m n 1 sproshena s m n teorema formulyuyetsya tak Teorema 3 6 Dlya kozhnoyi ChRF f x y isnuye RF s x taka sho dlya vsih znachen x y mayemo f x y fs x y Rozglyanemo prikladi zastosuvannya s m n teoremi Priklad 2 Isnuye RF s x y taka sho dlya vsih h y zyeN mayemo fs x y z fx z fy z Rozglyanemo funkciyu f x y z fx z fy z Funkciya f ye ChRF tomu za s m n teoremoyu isnuye RF s x y taka sho dlya vsih h y zyeN mayemo f x y z fs x y z fx z fy z Priklad 3 Dlya kozhnoyi 1 arnoyi ChRF f isnuye RF s x taka sho dlya vsih hyeN mayemo D s x f 1 Dx Rozglyanemo funkciyu g x y fx f y Taka funkciya ye ChRF za TCh tomu za s m n teoremoyu isnuye RF s x taka sho dlya vsih h yyeN mayemo g x y fs x u Zafiksuyemo h Mayemo uyeD s x lt gt f s x u lt gt g x y lt gt fx f y lt gt f y yeDx lt gt yyef 1 Dx Zvidsi Ds x f 1 Dx Priklad 4 Isnuye RF s x taka sho dlya vsih hyeN mayemo E s x Dx Rozglyanemo funkciyu f x y u yaksho uye Dx inakshe neviznachena Taka funkciya ye ChRF za TCh tomu za s m n teoremoyu isnuye RF s x taka sho dlya vsih h yyeN mayemo f x y fs x u Zafiksuyemo h Za pobudovoyu funkciyi f mayemo D s x E s x Teper uyeEs x uyeDs x fs x u f x y uyeDx Zvidsi Es x Dx Priklad 5 Isnuye RF t x taka sho dlya vsih hyeN mayemo Dt x Ex Rozglyanemo funkciyu f x y 1 yaksho uye Ex inakshe neviznachena Taka funkciya ye ChRF za TCh tomu za s m n teoremoyu isnuye RF t x taka sho dlya vsih h yyeN f x y ft x u Zafiksuyemo h Mayemo uyeDt x ft x u f x y uyeEh Zvidsi Dt x Ex Priklad 6 Isnuye RF s x taka sho dlya vsih hyeN mayemo D 2 s x u v x 2u 3v Rozglyanemo funkciyu f x u v 1 yaksho x 2u 3v inakshe neviznachena Za TCh f ye ChRF tomu za s m n teoremoyu isnuye RF s x taka dlya vsih h u vyeN mayemo f x u v f 2 s x u v Zafiksuyemo h Teper u v yeD 2 s x f 2 s x u v f x u v x 2u 3v Zvidsi D 2 s x u v x 2u 3v Priklad 7 Isnuye RF s x y taka sho dlya vsih h yyeN mayemo D s x y Dx٧Dy Rozglyanemo funkciyu f x y z 1 yaksho zye Dx abo zye Dy inakshe neviznachena Taka funkciya ye ChRF za TCh tomu za s m n teoremoyu isnuye RF s x y taka sho dlya vsih h y zyeN mayemo f x y z s x y z Zafiksuyemo h ta y Mayemo zyeD s x y f s x y z f x y z zyeDx٧Dy Zvidsi viplivaye D s x y Dx٧Dy Priklad 8 Isnuye RF s x y taka sho dlya vsih h yyeN mayemo Ds x y Es x y Dx٨Dy Rozglyanemo funkciyu f x y z 1 yaksho zye Dx abo zye Dy inakshe neviznachena Taka funkciya ye ChRF za TCh tomu za s m n teoremoyu isnuye RF s x y taka sho dlya vsih h y zyeN mayemo f x y z fs x y z Zafiksuyemo h ta y Za pobudovoyu funkciyi f mayemo Ds x y Es x y Teper zyeEs x y zyeDs x y fs x y z f x y z zyeDx٨Dy Zvidsi otrimuyemo Ds x y Es x y Dx٨Dy Teoremi Klini pro neruhomu tochkuTeorema 4 1 Nehaj f n 1 arna RF Todi isnuye n arna RF g taka sho f g x1 x2 xn f f g x1 x2 xn x1 x2 xn dlya vsih znachen x1 hp Pereformulyuyemo teoremu 7 4 1 dlya vipadku n 0 Teorema 4 2 Nehaj f x RF Todi isnuye nyeN take sho fn ff n Pervisne formulyuvannya samogo S Klini teoremi pro neruhomu tochku maye nastupnij viglyad Teorema 4 3 Nehaj h z x ChRF Todi isnuye nyeN take sho dlya vsih x mayemo h n x f n x Teoremu Klini pro neruhomu tochku krashe nazivati teoremoyu pro psevdoneruhomu tochku Spravdi umova f n f f n zovsim ne oznachaye sho n f n a svidchit tilki pro te sho n ta f n indeksi odniyeyi i toyi zh ChRF Priklad 1 MNR programu P nazvemo samotvornoyu yaksho dlya dovilnogo xyeN mayemo P x t P de t P kod programi P Na pershij poglyad takih program buti ne mozhe bo dlya pobudovi P treba znati t P tobto samu programu P Prote MNR programa P taka sho P x t P dlya vsih znachen x taki isnuye Spravdi vizmemo funkciyu h z x z Za teoremoyu 7 4 3 isnuye take n sho dlya vsih x h n x fn x Otzhe fn x h n x n dlya vsih x Tomu programa P z kodom n shukana Priklad 2 Isnuye nyeN take sho dlya vsih x mayemo fn x 2n x 3n Vizmemo funkciyu h z x 2z x3z Za teoremoyu 7 4 3 isnuye take n sho dlya vsih x h n x fn x Otzhe fn x h n x 2n x3n dlya vsih x Priklad 3 Isnuye nyeN take sho Dn En n Vizmemo funkciyu h z x x yaksho h z inakshe neviznachena Taka h ye ChRF Za teoremoyu 7 4 3 isnuye take n sho dlya vsih x mayemo h n x fn x Todi fn x x yaksho h n inakshe neviznachena Zvidsi Dn En n Priklad 5 Isnuye nyeN take sho Dp En N n 2n Vizmemo funkciyu h z x x yaksho h z ta h 2z inakshe neviznachena Taka h ye ChRF Za teoremoyu 7 4 3 isnuye take n sho h n x fn x dlya vsih x Todi fn x x yaksho h n ta h 2n inakshe neviznachena Zvidsi Dn En N n 2n Priklad 4 Isnuye nyeN take sho Dp Ep x x neparne y 2 4 2p Funkciya h z x x yaksho h neparne abo hye 2 4 2z inakshe neviznachena ye ChRF za TCh Za teoremoyu 7 4 3 isnuye take n sho h n x fn x dlya vsih x Todi fn x x yaksho h neparne abo hye 2 4 2z inakshe neviznachena Zvidsi mayemo Dn En x x neparne y 2 4 2p Priklad 6 Isnuye nyeN take sho Dp Ep x fn 3x ۸ x x parne Funkciya h z x x yaksho h z inakshe neviznachena ye ChRF za TCh Za teoremoyu 7 4 3 isnuye take n sho h n x fn x dlya vsih x Todi mayemo fn x Zvidsi otrimuyemo Dn En x fn 3x ۸ x x parne Priklad 7 Isnuye RF g x taka Dg x Eg x 3g x 2 x dlya vsih hyeN Funkciya h t x y u yaksho u 3t 2 x inakshe neviznachena ye ChRF za TCh Za s m n teoremoyu isnuye RF s t x taka h t x y fs t x y dlya vsih t x yyeN Za teoremoyu 7 4 1 isnuye RF g taka sho fg x fs g x x dlya vsih xyeN Todi fg x u fs g x x u h g x x y u yaksho u 3g x 2 x inakshe neviznachena Zvidsi dlya kozhnogo xyeN mayemo Dg x Eg x 3g x 2x Teorema 4 4 Dlya kozhnoyi RF f x isnuye strogo monotonna RF l x taka sho dlya kozhnogo nyeN mayemo fa n ff a n Naslidok Dlya kozhnoyi RF f x ta dlya kozhnogo kyeN isnuye nyeN take sho n gt k ta fn ff n Rozglyanuti nami efektivni numeraciyi ChRF neodnoznachni Odno znachni efektivni numeraciyi ChRF isnuyut 6 ale nemaye v pevnomu smisli prirodnih odnoznachnih efektivnih numeracij ChRF Teorema 4 5 Nehaj f x strogo monotonna totalna funkciya taka sho z umovi m n viplivaye ff m ff n prichomu f n ye najmenshim indeksom funkciyi ff n Todi funkciya f ne ye ChRF Funkciya GodelyaG x y mod l x 1 y 1 r x Dozvolyaye koduvati dovilnu skinchennu poslidovnist naturalnih chisel b0 b1 bn Dlya kozhnoyi takoyi poslidovnosti isnuye t take sho G t i bi dlya vsih i 0 1 n Teorema pro eliminaciyu primitivnoyi rekursiyiVikoristannya funkciyi Godelya daye zmogu promodelyuvati operaciyu primitivnoyi rekursiyi operaciyami superpoziciyi ta minimizaciyi Div takozhNumeraciya Gedelya Numeraciya KantoraPosilannyaNumeraciya Godelya