Нумерації. Теореми про нерухому точку, Детальна інформація

Приклад 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.

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

((()=0;

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

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

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

((()=0;

.

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

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

-1.

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

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

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

\xF06B(xk)=7(k ;

\xF06B(ck)=7(k+1;

\xF06B(fk t1...tn)=7(C(Cn+1(k, \xF06B(t1),...,\xF06B(tn)), n\xF02D1)+2;

\xF06B(pk t1...tn)=7(C(Cn+1(k, \xF06B(t1),...,\xF06B(tn)), n\xF02D1)+3;

\xF06B((\xF046)=7(C(k,\xF06B(\xF046))+4;

\xF06B(\xF0DA\xF046()=7(C(\xF06B(\xF046), \xF06B(())+5;

\xF06B(\xF024xk\xF046)=7(C(k,\xF06B(\xF046))+6.

Номером (індексом) довiльної формули \xF046 вважатимемо її код \xF06B(\xF046). Вс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 таке, що \xF047(t, i)=bi для всiх i({0,...,n}.

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

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

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

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

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