WWW.REFERATCENTRAL.ORG.UA - Я ТУТ НАВЧАЮСЬ

... відкритий, безкоштовний архів рефератів, курсових, дипломних робіт

ГоловнаМатематика, Геометрія, Статистика → Нумерації. Теореми про нерухому точку - Реферат

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


Реферат на тему:
Нумерації. Теореми про нерухому точку
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+yCп(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.
Приклад 3. Задамо однозначну ефективну нумерацiю всiх скiнченних послiдовностей натуральних чисел на основі наступного кодування : ?N таких послідовностей:
( )=0;
(а1, ..., ап)= C(Cп(а1, ..., ап), п-1)+1.
Зрозуміло, що таке відображення бієктивне. Тепер обернене відображення ?= -1 шукана однозначна нумерацiя.
Приклад 4. Однозначну ефективну нумерацiю всiх скiнченних послiдовностей натуральних чисел можна задати на основі такого кодування : ?N всіх скiнченних послiдовностей:
( )=0;
(а1, ..., ап)= + +...+ .
Бiєктивнiсть вiдображення випливає iз однозначностi подання кожного натурального числа в двiйковiй системi числення. Обернене відображення = -1 шукана однозначна нумерацiя.
Приклад 5. Однозначну ефективну нумерацiю всiх непорожніх скiнченних послiдовностей натуральних чисел задамо на основі кодування : ?N, що є модифікацією кодування :
(а1, ..., ап)= + +...+ -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ї операціями суперпозиції та мінімізації:
Теорема 1.3. Функцiя f=R(g, h) може бути отримана iз функцiй g, h, базових функцiй і функцiй +, за допомогою скiнченної кiлькостi застосувань операцiй Sn+1 та М.
Наслiдок. Клас ЧРФ спiвпадає з класом функцiй, отриманих із функцій о, s, I , +, за допомогою операц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.
Зрозумiло, що бiєктивне вiдображення множини всiх команд МНР на N. Використовуючи розглянуту вище бiєкцiю : ?N, задамо кодування всiх МНР-програм так.
Якщо P МНР-програма I1I2...Iк , то (P) = ( (I1),..., (Ik)).
Відображення та бiєктивнi, тому теж бiєкцiя. Тодi = -1 шукана однозначна нумерацiя.
Нумерацiя ефективна. Справдi, за кожною МНР-програмою P ефективно обчислюється її номер (P). З iншого боку, за кожним n N ефективно визначається МНР-програма P= (n). Справді, спочатку подамо число n+1 як суму зростаючих степенiв числа 2: n+1= + +...+ , де 0 b1<...Приклад 1. Залежнiсть функцiї s вiд n можна зняти, якщо для завдання ЧРФ використати МТ.
Справді, за z визначаємо МТ з кодом z для функцiї . Задамо нову МТ M, яка злiва вiд початкового вмiсту стрiчки дописує
Loading...

 
 

Цікаве