Нумерації. Теореми про нерухому точку, Детальна інформація
Нумерації. Теореми про нерухому точку
Тип документу: Реферат
Сторінок: 7
Предмет: Математика
Автор: Олексій
Розмір: 58.5
Скачувань: 1191
Приклад 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. ЕФЕКТИВНІ НУМЕРАЦІЇ ФОРМАЛЬНИХ МОДЕЛЕЙ АЛГОРИТМІВ ТА АОФ
Розглянемо приклади ефективних нумерацій формальних моделей алгоритмів та алгоритмічно обчислюваних функцій.
\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. ЕФЕКТИВНІ НУМЕРАЦІЇ ФОРМАЛЬНИХ МОДЕЛЕЙ АЛГОРИТМІВ ТА АОФ
Розглянемо приклади ефективних нумерацій формальних моделей алгоритмів та алгоритмічно обчислюваних функцій.