Нумерації. 
Теореми про нерухому точку (реферат)

Реферат на тему:

Нумерації. Теореми про нерухому точку

1. КОДУВАННЯ ТА НУМЕРАЦІЇ. КАНТОРОВІ НУМЕРАЦІЇ.

Під кодуванням множини, А на множині В будемо розуміти ін'єктивне та сюр'єктивне відображення А->В таке, що існують алгоритми A та B:

для кожного, а A (а)(а);

для кожного bB (b)=(b).

Нумерацiєю множини, А називають сюр'єктивне функцiональне вiдображення ->А.

Однозначною нумерацiєю множини, А називають бієктивне вiдображення ->А.

Нумерацiю ->А називають ефективною, якщо iснують алгоритми A та B такі:

для кожного, а A (а)-1(а);

для кожного nB (п)=).

Таким чином, ->А фективна нумерація А->N одування, А на N.

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

Всi пари натуральних чисел розташуємо в послiдовнiсть так:

пара (x, y) передує парі (u, v) +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)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, пара функцiй (l (n), r (n)) задає бiєкцiю N->N При цьому функцiї C, l та r зв’язaнi такими тотожностями:

C (l (n), r (n)=nl (C (x, y))=xr (C (x, y))=y.

Маючи нумерацiю пар натуральних чисел, можна ввести нумерацiю n-ок натуральних чисел для довiльного n>2:

Cп (x1, x2,…, xп)=Cп (x1, x2), x3,…, xп)=C (…С (C (x1, x2), x3),…), xп).

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

Нехай Cп (x1, x2,…, xп)=mтоді Cn1(m)=x1- Cn2(m)=x2- …, Cnn (m)=xn.

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

Cп (Cn1(x), …, Cnn (x))=x;

Cnk (Cп (x1, x2,…, xп))=xk, 1/p>

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

2) Функцiї Cп, Cn1, …, Cnn є ПРФ.

Приклад 1. Знайдемо l (100) та r (100). Для х=l (100) та у=r (100) маємо рівняння С (х, у)=100. Нехай х+у=р. Тоді р є найбільшим натуральним числом, для якого р+1). Звідси р=13. Маємо х+у=13, х=100-[(13/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). Звідси р=19, звідки а=17 та v=2. Тепер маємо С (С (x, y), z)=17. Нехай С (x, y)=b, тоді C (b, z)=17. Нехай b+z=q. Тоді q є найбільшим натуральним числом, для якого q1) Звідси q=5, звідки b=2 та z=3. Маємо C (x, y)=2, звідки x=1 та y=0.

Приклад 3. Задамо однозначну ефективну нумерацiю всiх скiнченних послiдовностей натуральних чисел на основі наступного кодування math xmlns="http://www.w3.org/1998/Math/MathML" display="block" >k>=0Nk ->N таких послідовностей:

;

1, …, ап)= C (Cп (а1, …, ап), п-1)+1.

Зрозуміло, що таке відображення бієктивне. Тепер обернене відображення -1 укана однозначна нумерацiя.

Приклад 4. Однозначну ефективну нумерацiю всiх скiнченних послiдовностей натуральних чисел можна задати на основі такого кодування math xmlns="http://www.w3.org/1998/Math/MathML" display="block" >k>=0Nk ->N всіх скiнченних послiдовностей:

;

1, …, ап)= $$2^{{а}_1}$$ + $$2^{{а}_1+{а}_2+1}$$ +…+ $$2^{{а}_1+{а}_2+\text{.}\text{.}\text{.}+{а}_{п}+п-1}$$ .

Бiєктивнiсть вiдображення випливає iз однозначностi подання кожного натурального числа в двiйковiй системi числення. Обернене відображення укана однозначна нумерацiя.

Приклад 5. Однозначну ефективну нумерацiю всiх непорожніх скiнченних послiдовностей натуральних чисел задамо на основі кодування math xmlns="http://www.w3.org/1998/Math/MathML" display="block" >k>=0Nk ->N, що є модифікацією кодування.

1, …, ап)= $$2^{{а}_1}$$ + $$2^{{а}_1+{а}_2+1}$$ +…+ $$2^{{а}_1+{а}_2+\text{.}\text{.}\text{.}+{а}_{п}+п-1}$$ -1.

Обернене відображення укана однозначна нумерацiя.

Приклад 6. Ефективну нумерацiю множини формул довiльної мови 1-го порядку із злiченним алфавiтом введемо таким чином.

Занумеруємо множини предметних імен x0, x1, …, константних символiв c0, c1, …, функцiональних символiв f0, f1, … та предикат-них символiв p0, p1,…. Кодування ермiв та формул. задамо так:

)=7.

)=7;

t1…tn)=7n+1(k,),…,)), n2;

t1…tn)=7n+1(k,),…,)), n3;

)=7,4;

5;

6.

Номером (індексом) довiльної формули вважатимемо її код Всi тi натуральнi числа, якi не є кодами формул, вважатимемо номером формули x0=x0. Зрозуміло, що так введена нумерація неоднозначна. Формулу з номером n позначатимемо.

Кодувати довiльну скiнченну послiдовнiсть натуральних чисел. дозволяє також функція Гьоделя y) = mod (l (x), 1+(y+1))).

З визначення випливає, що y) є ПРФ.

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

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

Теорема 1.3. Функцiя f=R (g, h) може бути отримана iз функцiй g, h, базових функцiй і функцiй +, $$\text{та}\text{{}\stackrel{}{-}$$ за допомогою скiнченної кiлькостi застосувань операцiй Sn+1 та М.

Наслiдок. Клас ЧРФ спiвпадає з класом функцiй, отриманих із функцій о, s, I $${}_{т}^{п}$$, +, $$\text{та}\text{{}\stackrel{}{-}$$ за допомогою операцiй Sn+1 та M.

2. ЕФЕКТИВНІ НУМЕРАЦІЇ ФОРМАЛЬНИХ МОДЕЛЕЙ АЛГОРИТМІВ ТА АОФ Розглянемо приклади ефективних нумерацій формальних моделей алгоритмів та алгоритмічно обчислюваних функцій.

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

n)) = 4/p>

n)) = 4;

т, n)) = 4 т, n)+2;

m, n, q+1))=4С (т, n), q)+3.

Зрозумiло, що iєктивне вiдображення множини всiх команд МНР на N. Використовуючи розглянуту вище бiєкцiю math xmlns="http://www.w3.org/1998/Math/MathML" display="block" >k>=1Nk ->N, задамо кодування всiх МНР-програм так.

Якщо P НР-програма I1I2… Iк, то =),…,)).

Відображення та бiєктивнi, тому теж бiєкцiя. Тодi укана однозначна нумерацiя.

Нумерацiя ефективна. Справдi, за кожною МНР-програмою P ефективно обчислюється її номер. З iншого боку, за кожним nефективно визначається МНР-програма P=. Справді, спочатку подамо число n+1 як суму зростаючих степенiв числа 2: n+1= $$2^{b_1}$$ + $$2^{b_2}$$ +…+ $$2^{b_k}$$, де 0lt-…<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. 1)J (1,2,5) — 1,2,5))=4С (1,2), 4)+3=47,4)+3=43=295;

2. 2)S (0) — 0))=4=1;

3. 3)S (2) — 2))=4=9;

4. 4)J (0,0,1) — 0,0,1))=4С (0,0), 0)+3=40,0)+3=4=3.

Тепер = 5, 1, 9, 3) = 2295+2297+2307+2311/p>

Приклад 1.2. Знайдемо P5119 =19). Маємо 5119+1=5120=210+212, звiдки a1=10, a2=12−10−1 = 1. Але 10=2+4,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}. Кодування команд МТ задамо так:

aj1) = 3i, j, k, l);

aj1L) = 3i, j, k, l)+1;

aj1R) = 3i, j, k, l)+2.

Таке є бiєктивним вiдображенням множини всiх можливих команд машин Тьюрiнга на N. Використовуючи розглянуту вище бiєкцiю math xmlns="http://www.w3.org/1998/Math/MathML" display="block" >k>=1Nk ->N, визначимо код МТ M, заданої послiдовнiстю команд I1I2… Iк, таким чином: =),…,)). Але та бiєктивнi, тому теж бiєкцiя. Тодi укана однозначна нумерацiя послiдовностей команд МТ, але неоднозначна нумерацiя всiх МТ. Неважко переконатись, що така нумерацiя ефективна.

Приклад 2.1. Знайдемо код МТ М, яка обчислює бінарну функцію х+у. Вважаємо a0=a1=|, a2=# та q*=q2. Використаємо приклад 1 розділу 2.2. Маємо:

q0||R- ||R)=30,1,0,1)+2=3,1)+2=3=26;

q0#|R- #|R)=30,2,0,1)+2=3,1)+2=32=194;

q0 q1 q130,0,1,0)+1=3,0)+1=3=7;

q1| |1,1,2,0)= 35,0)=3=1050.

Тепер =, 194, 7, 1050) = 226+2221+2229+21 280/p>

Приклад 3. Ефективну нумерацiю всiх т-арних ЧРФ задамо на основi кодування операторних термiв алгебри ЧРФ. Завдання ЧРФ операторними термами неоднозначне, бо кожну ЧРФ можна описати нескiнченною кiлькiстю рiзних ОТ, тому нумерацiя неоднозначна.

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

) = 0- = 4- $${}_{т}^{п}$$) = 4n, m)-2);

+1(t0, t1,…, tn)) = 4n+1(),),…,)), n-1)+1;

t0, t1)) = 4),))+2;

t)) = 4(t)+3.

Число nвважаємо номером ЧРФ f, якщо n є кодом якогось ОТ, i значенням цього ОТ є функцiя f. Числа, якi не є кодами ОТ, та коди тих ОТ, якi не задають ЧРФ, вважаємо номерами всюди невизначеної функцiї fЗрозумiло, що за кожною ЧРФ можна ефективно знайти її номер. З iншого боку, за кожним nефективно визначається ЧРФ f така, що =f: за n як за кодом будуємо ОТякщо ОТ з таким кодом iснує та задає ЧРФ, то аме така ЧРФ f — якщо ОТ з таким кодом iснує, але не задає ЧРФ, то =f якщо ОТ з таким кодом не iснує, то = f Отже, є ефективною нумерацiєю всiх ЧРФ.

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

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

) = 0- = 3- $${}_{т}^{п}$$) = 3n, m)-2);

+1(t0, t1,…, tn)) = 3n+1(),),…,)), n-1)+1;

t0, t1)) = 3),))+2.

Число nвважаємо номером ПРФ f, якщо n є кодом якогось ОТ та значенням цього ОТ є функцiя f. Числа, якi не є кодами ОТ, та коди тих ОТ, якi не задають ПРФ, вважаємо номерами функцiї о.

Приклад 4.1. Знайдемо код ОТ алгебри ПРФ для f (x1, x2)=x1+x2. Згідно прикладу 2 розділу 6.6, для x1+x2 маємо ОТ R (I $${}_1^1$$, S2(s, I $${}_3^3$$)), звідки отримуємо I $${}_1^1$$, S2(s, I $${}_3^3$$))) = 3$${}_1^1$$), (s, I $${}_3^3$$)))+2 =.

= 3, 3С (, $${}_3^3$$)), 0)+1)+2 = 3, 3С (3, 24), 0)+1)+2 =.

= 3, 381, 0)+1)+2 = 3, 352+1)+2 = 3, 219 457)+2 =.

= 3082 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в ППА-Ar-N :

) = 0- = 4- = 8- 12- $$\begin{array}{c}(\stackrel{}{-})\\ \end{array}$$ =16:

$${}_{т}^{п}$$) = 4n, m)+1);

+1(t0, t1,…, tn)) = 4n+1(),),…,)), n-1)+1;

t1, t2)) = 4),),))+2;

t1)) = 4),))+3.

Приклад 6. Ефективну нумерацiю всiх МНР-обчислюваних функцiй фіксованої арності п задамо на основ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 арності п буде число С (k, n), де k од МТ для f.

3. НУМЕРАЦІЇ n-АРНИХ ЧРФ. УНІВЕРСАЛЬНІ ФУНКЦІЇ. s-m-n-ТЕОРЕМА В силу сп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ефективну нумерацiю n-арних ЧРФ. Звичайно це буде нумерація на основі кодування МНР-програм (приклад 6), інколи нумерація на основі кодування МТ (приклад 8). Вказані нумерації назвемо стандартними нумераціями n-арних ЧРФ. Для стандартних нумерацій введемо наступні позначення.

n-арну ЧРФ з номером m позначатимемо ath xmlns="http://www.w3.org/1998/Math/MathML" display="block" >тп. У випадку n=1 вживатимемо спрощене позначення Область визначення та область значень функцiї ath xmlns="http://www.w3.org/1998/Math/MathML" display="block" >тп позначатимемо вiдповiдно D $${}_{т}^{п}$$ та E $${}_{т}^{п}$$. У випадку n=1 вживатимемо позначення Dm та Em.

Номер функцiї назвемо також iндексом функцiї. Номер функцiї в стандартній намерації назвемо стандартним iндексом функцiї.

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

ля кожного т ath xmlns="http://www.w3.org/1998/Math/MathML" display="block" >тп =);

ля кожного k ath xmlns="http://www.w3.org/1998/Math/MathML" display="block" >g (k)п .

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

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

Для довiльного класу п-арних функцiй F клас всiх функцiй iз F фіксованої арності т будемо позначати Fт.

Функцiя и (y, x1, …, xп) унiверсальна для класу Fп, якщо:

ля кожного значення m функцiя и (y, x1, …, xп);

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

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

Насл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-арних ЧРФ.

Такою буде функція и (у, x1, …, xп) = ath xmlns="http://www.w3.org/1998/Math/MathML" display="block" >уп (x1, …, xп).

МНР-програма, яка обчислює унiверсальну ЧРФ, називається унiверсальною МНР-програмою.

Унiверсальна програма декодує довiльне число y в програму Py, а далi вона моделює роботу Py. Тому така унiверсальна програма може бути задана в явному виглядi. Отже, можна конструктивно знайти iндекс k унiверсальної функцiї u в стандартній нумерацiї (n+1)-арних ЧРФ, тобто u суть функцiя ath xmlns="http://www.w3.org/1998/Math/MathML" display="block" >kп+1 .

Машина Тьюрiнга, яка обчислює унiверсальну ЧРФ, називається унiверсальною МТ. Таку МТ, здатну моделювати роботу довiльної МТ за її кодом, теж можна задати в явному виглядi.

Для кожного фiксованого значення а1, …, ат аргументiв x1, …, xт (m+n)-арна ЧРФ ath xmlns="http://www.w3.org/1998/Math/MathML" display="block" >zm+n (x1, …, xт, у1, …, уп). стає n-арною ЧРФ ath xmlns="http://www.w3.org/1998/Math/MathML" display="block" >kn (у1, …, уп). Її iндекс k можна ефективно знайти за z та а1, …, ат. Це означає, що iснує (m+1)-арна РФ, яку традицiйно позначають s $${}_{п}^{т}$$, що обчислює цей iндекс:

Теорема 3.4 (s-m-n-теорема). Для довiльних m, n>1 iснує (m+1)-арна РФ s $${}_{п}^{т}$$ (z, x1, …, xm) така, що для всiх z, x1, …, xт, у1, …, уп маємо ath xmlns="http://www.w3.org/1998/Math/MathML" display="block" >zm+n (x1, …, xт, у1, …, уп) = ath xmlns="http://www.w3.org/1998/Math/MathML" display="block" >snm (z, x1,…, xm) n (у1, …, уп).

Приклад 1. Залежнiсть функцiї s $${}_{п}^{т}$$ вiд n можна зняти, якщо для завдання ЧРФ використати МТ.

Справді, за z визначаємо МТ з кодом z для функцiї ath xmlns="http://www.w3.org/1998/Math/MathML" display="block" >zm+n. Задамо нову МТ M, яка злiва вiд початкового вмiсту стрiчки дописує слово $$\begin{array}{c}{|}^{x_1}\\ \text{.}\text{.}\text{.}\\ {|}^{x_2}{|}^{x_m}\end{array}$$, a далi моделює роботу МТ з кодом z. Така МТ M при входi $$\begin{array}{c}{|}^{y_1}\\ \text{.}\text{.}\text{.}\\ {|}^{y_2}{|}^{y_n}\end{array}$$ обчислює n-арну функцiю ath xmlns="http://www.w3.org/1998/Math/MathML" display="block" >kn, причому k код МТ M, е залежить вiд n .

Теорема 3.5 (s-m-n-теорема в спрощенiй формi). Для кожної ЧРФ f (x1, …, xт, у1, …, уп) iснує РФ s (x1, …, xm) така, що для всiх x1, …, xт, у1, …, уп маємо f (x1, …, xт, у1, …, уп) = ath xmlns="http://www.w3.org/1998/Math/MathML" display="block" >s (z, x1,…, xm) n (у1, …, уп).

При т=п=1 спрощена s-m-n-теорема формулюється так:

Теорема 3.6. Для кожної ЧРФ f (x, y) iснує РФ s (x) така, що для всiх значень x, y маємо f (x, y)=)(y).

Розглянемо приклади застосування s-m-n-теореми.

Приклад 2. Існує РФ s (x, y) така, що для всіх х, y, zмаємо, y)(z)=)+).

Розглянемо функцію f (x, y, z)=)+). Функція f є ЧРФ, тому за s-m-n-теоремою існує РФ s (x, y) така, що для всіх х, y, zмаємо f (x, y, z)=, y)(z)=)+).

Приклад 3. Для кожної 1-арної ЧРФ f існує РФ s (x) така, що для всіх хмаємо Ds (x)= f-1(Dx).

Розглянемо функцію g (x, y)=(y)). Така функція є ЧРФ за ТЧ, тому за s-m-n-теоремою існує РФ s (x) така, що для всіх х, yмаємо g (x, y)=)(у). Зафіксуємо х. Mаємо уx))(у)(x, y)(y))y) (Dx). Звідси Ds (x)= f-1(Dx).

Приклад 4. Існує РФ s (x) така, що для всіх хмаємо Еs (x)=Dx .

Розглянемо функцію f (x, y)= $$\{\begin{array}{c}y\text{, якщо}y{D}_x\text{,}\\ \text{невизначене інакше}\text{.}\end{array}$$ Така функція є ЧРФ за ТЧ, тому за s-m-n-теоремою існує РФ s (x) така, що для всіх х, yмаємо f (x, y)=)(у). Зафіксуємо х. За побудовою функції f маємо Ds (x)=Еs (x). Тепер у (x) x))(у)x, y). Звідси Еs (x)=Dx .

Приклад 5. Існує РФ t (x) така, що для всіх хмаємо Dt (x)=Еx .

Розглянемо функцію f (x, y)= Така функція є ЧРФ за ТЧ, тому за s-m-n-теоремою існує РФ t (x) така, що для всіх х, y f (x, y)=)(у). Зафіксуємо х. Mаємо уx))(у)x, y). Звідси Dt (x)=Ex .

Приклад 6. Існує РФ s (x) така, що для всіх хмаємо $$D_{s(x)}^2$$ ={(u, v) | x=2u+3v}.

Розглянемо функцію f (x, u, v)= $$\{\begin{array}{c}1\text{, якщо}x=2u+3v\text{,}\\ \text{невизначене інакше}\text{.}\end{array}$$ За ТЧ f є ЧРФ, тому за s-m-n-теоремою існує РФ s (x) така: для всіх х, u, vмаємо f (x, u, v)= $${}_{s(x)}^2$$ (u, v). Зафіксуємо х. Тепер (u, v) ath xmlns="http://www.w3.org/1998/Math/MathML" display="block" >Ds (x)2 math xmlns="http://www.w3.org/1998/Math/MathML" display="block" >s (x)2 (u, v) x, u, v)2u+3v. Звідси $$D_{s(x)}^2$$ ={(u, v) | x=2u+3v}.

Приклад 7. Існує РФ s (x, y) така, що для всіх х, yмаємо Ds (x, y)=Dx.

Розглянемо функцію f (x, y, z)= $$\{\begin{array}{c}1\text{, якщо}z{D}_x\text{або}z{D}_y\text{,}\\ \text{невизначене інакше}\text{.}\end{array}$$ Така функція є ЧРФ за ТЧ, тому за s-m-n-теоремою існує РФ s (x, y) така, що для всіх х, y, zмаємо f (x, y, z)=, y)(z). Зафіксуємо х та y. Маємо zx, y), y)(z)x, y, z). Звідси випливає Ds (x, y)=Dx.

Приклад 8. Існує РФ s (x, y) така, що для всіх х, yмаємо Ds (x, y)=Еs (x, y)=Dx.

Розглянемо функцію f (x, y, z)= $$\{\begin{array}{c}z\text{, якщо}z{D}_x\text{та}z{D}_y\text{,}\\ \text{невизначене інакше}\text{.}\end{array}$$ Така функція є ЧРФ за ТЧ, тому за s-m-n-теоремою існує РФ s (x, y) така, що для всіх х, y, zмаємо f (x, y, z)=, y)(z). Зафіксуємо х та y. За побудовою функції f маємо Ds (x, y)=Еs (x, y). Тепер z (x, y) x, y), y)(z)x, y, z). Звідси отримуємо Ds (x, y)=Еs (x, y)=Dx.

4. ТЕОРЕМИ КЛІНІ ПРО НЕРУХОМУ ТОЧКУ.

Теорема 4.1. Нехай f +1)-арна РФ. Тодi iснує n-арна РФ g така, що ath xmlns="http://www.w3.org/1998/Math/MathML" display="block" >g (x1,…, xn) =ath xmlns="http://www.w3.org/1998/Math/MathML" display="block" >f (g (x1,…, xn), x1,…, xn) для всiх значень x1, …, xп.

Переформулюємо теорему 7.4.1 для випадку n=0.

Теорема 4.2. Нехай f (x) Ф. Тодi iснує nтаке, що).

Первісне формулювання самого С. Кліні теореми про нерухому точку має наступний вигляд:

Теорема 4.3. Нехай h (z, x) РФ. Тодi iснує nтаке, що для всiх x маємо h (n, x)=).

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

Приклад 1. МНР-програму P назвемо самотворною, якщо для довiльного xмаємо P (x)(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)=). Отже,)=h (n, x)=n для всiх x. Тому програма P з кодом n укана.

Приклад 2. Існує nтаке, що для всiх x маємо)=2n+x3n.

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

Приклад 3. Існує nтаке, що Dn=En={n}.

Вiзьмемо функцiю h (z, x)= $$\{\begin{array}{c}x\text{, якщо}x=z\text{,}\\ \text{невизначене інакше}\text{.}\end{array}$$ Така h є ЧРФ. За теоремою 7.4.3 iснує таке n, що для всiх x маємо h (n, x)=). Тоді)= $$\{\begin{array}{c}x\text{, якщо}x=n\text{,}\\ \text{невизначене інакше}\text{.}\end{array}$$ Звідси Dп=Еп={n}.

Приклад 5. Існує nтаке, що Dп=En=N{n, 2n}.

Вiзьмемо функцiю h (z, x)= $$\{\begin{array}{c}x\text{, якщо}x/=z\text{та}x/=2z\text{,}\\ \text{невизначене інакше}\text{.}\end{array}$$ Така h є ЧРФ. За теоремою 7.4.3 iснує таке n, що h (n, x)=) для всiх x. Тоді)= $$\{\begin{array}{c}x\text{, якщо}x/=n\text{та}x/=2n\text{,}\\ \text{невизначене інакше}\text{.}\end{array}$$ Звідси Dп=En=N{n, 2n}.

Приклад 4. Існує nтаке, що Dп=Еп={x | x непарнe} 4, …, 2п}.

Функцiя h (z, x) = $$\{\begin{array}{c}x\text{, якщо}x\text{непарне або}x\{2\text{, 4,}\text{.}\text{.}\text{.}\text{, 2}z\}\text{,}\\ \text{невизначене інакше,}\end{array}$$ є ЧРФ за ТЧ. За теоремою 7.4.3 iснує таке n, що h (n, x)=) для всiх x. Тоді) = $$\{\begin{array}{c}x\text{, якщо}x\text{непарне або}x\{2\text{, 4,}\text{.}\text{.}\text{.}\text{, 2}n\}\text{,}\\ \text{невизначене інакше}\text{.}\end{array}$$ Звідси маємо Dп=En={x | x непарнe} 4, …, 2п}.

Приклад 6. Існує nтаке, що Dп=Еп={x | x)| x парнe}.

Функцiя h (z, x) = $$\{\begin{array}{c}x\text{, якщо}{}_z(3x)V\text{та}x\text{парне,}\\ \text{невизначене інакше,}\end{array}$$ є ЧРФ за ТЧ. За теоремою 7.4.3 iснує таке n, що h (n, x)=) для всiх x. Тоді маємо) = $$\{\begin{array}{c}x\text{, якщо}{}_{п}(3x)V\text{та}x\text{парне,}\\ \text{невизначене інакше,}\end{array}$$ Звідси отримуємо Dп=Еп={x | x)| x парнe}.

Приклад 7. Існує РФ g (x) така: Dg (x)=Еg (x)={3g (x)+2x} для всіх х/p>

Функція h (t, x, y)= $$\{\begin{array}{c}y\text{, якщо}y=3t+2^x\text{,}\\ \text{невизначене інакше,}\end{array}$$ є ЧРФ за ТЧ. За s-m-n-теоремою існує РФ s (t, x) така: h (t, x, y)=, x)(y) для всіх t, x, yЗа теоремою 7.4.1 існує РФ g така, що)=(x), x) для всіх xТоді)(у)=(x), x)(у)=h (g (x), x, y)= $$\{\begin{array}{c}y\text{, якщо}y=3g(x)+2^x\text{,}\\ \text{невизначене інакше}\text{.}\end{array}$$ Звідси для кожного xмаємо Dg (x)=Еg (x)={3g (x)+2x}.

Теорема 4.4. Для кожної РФ f (x) iснує строго монотонна РФ така, що для кожного n маємо (n) =).

Наслiдок. Для кожної РФ f (x) та для кожного kiснує nтаке, що n>k та).

Розглянутi нами ефективнi нумерацiї ЧРФ неоднозначнi. Одно-значнi ефективні нумерацiї ЧРФ iснують [6], але немає в певному смислi «природних» однозначних ефективних нумерацiй ЧРФ.

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