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

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

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

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

Кодувати дов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)) = 4n;

(S(n)) = 4n+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ншого боку, за кожним nN ефективно визначається МНР-програма P=(n). Справді, спочатку подамо число n+1 як суму зростаючих степенiв числа 2: n+1=++...+, де 0b1<...<bk. Далi визначимо послiдовнiсть чисел a1, ..., ak: a1=b1, ai+1=bi+1-bi-1 для 1<i<k. Тепер за числами a1, ..., ak як за кодами команд МНР вiдновимо вiдповiднi команди. Послiдовнiсть цих команд i є шуканою МНР-програмою P.

МНР-програму з кодом n позначатимемо Pn.

Приклад 1.1. Знайдемо код МНР-програми P, яка обчислює бінарну функцію х+у. Використаємо приклад 3 розділу 2.1. Маємо:

  1. J(1,2,5); (J(1,2,5))=4С(С(1,2),4)+3=4С(7,4)+3=473+3=295;

  2. S(0);(S(0))=40+1=1;

  3. S(2);(S(2))=42+1=9;

  4. J(0,0,1);(J(0,0,1))=4С(С(0,0),0)+3=4С(0,0)+3=40+3=3.

Тепер (P)= (295, 1, 9, 3) = 2295+2297+2307+23111.

Приклад 1.2. Знайдемо P5119 =(5119). Маємо 5119+1=5120=210+212, звiдки a1=10, a2=12-10-1 = 1. Але 10=2+4C(1,0), тому P5119 така:

1) T(1,0)

2) S(0).

Приклад2. Ефективну нумерацiю всiх МТ задамо на основi кодування МТ. Кожну МТ можна задати послiдовнiстю її команд такою, що 1-а команда мiстить в лiвiй частинi символ q0, остання команда мiстить в правiй частинi символ q*. Таке завдання неоднозначне, бо множину команд МТ можна впорядкувати у виглядi послiдовностi з вищевказаною властивiстю багатьма способами. Тому наша нумерацiя МТ неоднозначна.

Занумеруємо внутрiшнi стани МТ та символи стрiчки. Нехай Q={q1,..., qf}, T={a1,..., am}. Кодування  команд МТ задамо так:

(qiajqka1)= 3C4(i, j, k, l);

(qiajqka1L)= 3C4(i, j, k, l)+1;

(qiajqka1R)= 3C4(i, j, k, l)+2.

Таке  є бiєктивним вiдображенням множини всiх можливих команд машин Тьюрiнга на N. Використовуючи розглянуту вище бiєкцiю :→N, визначимо код МТ M, заданої послiдовнiстю команд I1I2...Iк , таким чином: (M)= ((I1),..., (Ik)). Але  та  бiєктивнi, тому  теж бiєкцiя. Тодi =-1  шукана однозначна нумерацiя послiдовностей команд МТ, але неоднозначна нумерацiя всiх МТ. Неважко переконатись, що така нумерацiя ефективна.

Приклад 2.1. Знайдемо код МТ М, яка обчислює бінарну функцію х+у. Вважаємо a0=, a1=|, a2=# та q*=q2 . Використаємо приклад 1 розділу 2.2. Маємо:

q0| q0|R; (q0| q0|R)=3C4(0,1,0,1)+2=3C(2,1)+2=38+2=26;

q0# q0|R; (q0# q0|R)=3C4(0,2,0,1)+2=3C(9,1)+2=364+2=194;

q0 q1L; (q0 q1L)=3C4(0,0,1,0)+1=3C(1,0)+1=32+1=7;

q1| q*; (q1| q*)=3C4(1,1,2,0)= 3C(25,0)=3350=1050.

Тепер (M)= (26, 194, 7, 1050) = 226+2221+2229+212801.

Приклад3. Ефективну нумерацiю  всiх т-арних ЧРФ задамо на основi кодування  операторних термiв алгебри ЧРФ. Завдання ЧРФ операторними термами неоднозначне, бо кожну ЧРФ можна описати нескiнченною кiлькiстю рiзних ОТ, тому нумерацiя  неоднозначна.

Кодування  операторних термiв задамо так:

(о) = 0; (s) = 4; (I) = 4(C(n, m)-2);

(Sn+1(t0, t1,..., tn)) = 4C(Cn+1((t0), (t1),..., (tn)), n-1)+1;

(R(t0, t1)) = 4C((t0), (t1))+2;

(M(t)) = 4(t)+3.

Число nN вважаємо номером ЧРФ f, якщо n є кодом якогось ОТ, i значенням цього ОТ є функцiя f. Числа, якi не є кодами ОТ, та коди тих ОТ, якi не задають ЧРФ, вважаємо номерами всюди невизначеної функцiї f. Зрозумiло, що за кожною ЧРФ можна ефективно знайти її номер. З iншого боку, за кожним nN ефективно визначається ЧРФ f така, що (n)=f : за n як за кодом будуємо ОТ; якщо ОТ з таким кодом iснує та задає ЧРФ, то (n)  саме така ЧРФ f ; якщо ОТ з таким кодом iснує, але не задає ЧРФ, то (n)=f ; якщо ОТ з таким кодом не iснує, то (n)= f . Отже,  є ефективною нумерацiєю всiх ЧРФ.

Loading...

 
 

Цікаве