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

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

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

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

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

??для кожного b(B B(b)=( -1(b).

Нумерацiєю множини А називають сюр’єктивне функцiональне вiдображення
(: N ?А.

Однозначною нумерацiєю множини А називають бієктивне вiдображення (:
N ?А.

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

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

??для кожного n(N B(п)=((п).

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

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

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

пара (x, y) передує парі (u, v) ( x+y2:

Cп(x1, x2,…, xп)=Cп?1(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(k(n.

Теорема 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)(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.

?N таких послідовностей:

((()=0;

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

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

?N всіх скiнченних послiдовностей:

((()=0;

.

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

?N, що є модифікацією кодування (:

-1.

Обернене відображення (=(-1 ? шукана однозначна нумерацiя.

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

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

?(xk)=7(k ;

?(ck)=7(k+1;

?(fk t1…tn)=7(C(Cn+1(k, ?(t1),…,?(tn)), n?1)+2;

?(pk t1…tn)=7(C(Cn+1(k, ?(t1),…,?(tn)), n?1)+3;

?((?)=7(C(k,?(?))+4;

?(??()=7(C(?(?), ?(())+5;

?(?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ї операціями суперпозиції та мінімізації:

за допомогою скiнченної кiлькостi застосувань операцiй Sn+1 та
М.

за допомогою операцiй Sn+1 та M.

2. ЕФЕКТИВНІ НУМЕРАЦІЇ ФОРМАЛЬНИХ МОДЕЛЕЙ АЛГОРИТМІВ ТА АОФ

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

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

((Z(n)) = 4(n;

((S(n)) = 4(n+1;

((T(т,n)) = 4(С(т,n)+2;

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

?N, задамо кодування ( всiх МНР-програм так.

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

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

, де 0(b1<...k та (n=(f(n).

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

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

Похожие записи