Реферат на тему:
Нумерації. Теореми про нерухому точку
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<... a1 ... ak: ai ak i p. n pn. p j s p5119="((5119)." a2="12-10-1" t q0 q qf am k l m i1i2...i a0="(," . q1 t1 tn n-1 f f. : n- t2 h s-m-n- dm em. g x1 x xn u y z ds f-1 dt v y. a x. dn="En={n}." d dg>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 не є ЧРФ.
Нашли опечатку? Выделите и нажмите CTRL+Enter