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

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

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

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

Приклад 3.1. Знайдемо код ОТ алгебри п-арних ЧРФ для всюди невизначеної функцiї f. Згадуючи приклад 9 розділу 6.6, для f маємо ОТ М(s), звідки (M(s)) = 4(s)+3 = 44+3=19.

Приклад4. Ефективну нумерацiю всiх ПРФ задамо на основi кодування операторних термiв алгебри ПРФ. Така нумерацiя ПРФ неоднозначна. Кодування  ОТ алгебри ПРФ задамо так:

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

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

(R(t0, t1)) = 3C((t0), (t1))+2.

Число nN вважаємо номером ПРФ f, якщо n є кодом якогось ОТ та значенням цього ОТ є функцiя f. Числа, якi не є кодами ОТ, та коди тих ОТ, якi не задають ПРФ, вважаємо номерами функцiї о.

Приклад 4.1. Знайдемо код ОТ алгебри ПРФ для f(x1, x2)=x1+x2 . Згідно прикладу 2 розділу 6.6, для x1+x2 маємо ОТ R(I, S2(s, I)), звідки отримуємо (R(I, S2(s, I))) = 3C((I), (S2(s, I)))+2 =

= 3C(6, 3C(С((s), (I)), 0)+1)+2 = 3C(6, 3C(С(3, 24), 0)+1)+2 =.

= 3C(6, 3C(381, 0)+1)+2 = 3C(6, 373152+1)+2 = 3C(6, 219457)+2 =

= 324 082 113 916+2 = 72 246 341 748+2 = 72 246 341 750.

Приклад5. Ефективну нумерацiю всiх програмованих на Nn-арних функцiй задамо на основi кодування операторних термiв ППА-Ar-N. Зрозуміло, що така нумерацiя неоднозначна. Єдина iстотна вiдмiн-нiсть вiд нумерацiї прикладу 3  iнше кодування  операторних термiв ППА-Ar-N :

(о) = 0; (s) = 4; (+) = 8; () = 12; =16:

(I) = 4(C(n, m)+1);

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

(N(t0, t1, t2)) = 4C3((t0), (t1), (t2))+2;

(N(t0, t1)) = 4C((t0), (t1))+3.

Приклад6. Ефективну нумерацiю n всiх МНР-обчислюваних функцiй фіксованої арності п задамо на основi кодування МНР-програм (приклад 1). Hомеромn-арної МНР-обчислюваної функцiї f буде код МНР-програми, яка обчислює функцію f. Кожна n-арна МНР-обчислювана функцiя може задаватися нескiнченною кiлькiстю рiзних МНР-програм, тому така нумерацiя неоднозначна.

Приклад7. Ефективну нумерацiю всiх МНР-обчислюваних функцiй можна ввести на основі кодування МНР-програм. Hомеромn-арної функцiї f буде число С(k, n), де k  код МНР-програми для f.

Приклад 8. Ефективну нумерацiю всiх МТ-обчислюваних функцiй фіксованої арності п задамо на основi кодування МТ. Номеромn-арної МТ-обчислюваної функцiї f буде код МТ, яка обчислює f. Кожна n-арна МТ-обчислювана функцiя може задаватися нескiнчен-ною кiлькiстю рiзних МТ, тому така нумерацiя неоднозначна.

Приклад 9. Ефективну нумерацiю всiх обчислюваних за Тьюрiнгом функцiй введемо на основі кодування МТ. Hомером МТ-обчислю-ваної функцiї f арності п буде число С(k, n), де k  код МТ для f.

3. НУМЕРАЦІЇn-АРНИХ ЧРФ.УНІВЕРСАЛЬНІ ФУНКЦІЇ. s-m-n-ТЕОРЕМА

В силу спiвпадiння класiв ЧРФ, програмованих на N функцiй, МНР-обчислюваних функцiй та МТ-обчислюваних функцiй, нумерацiї прикладiв 5, 6 та 8 розділу 7.2 можна розглядати як ефек-тивні нумерацiї всiх n-арних ЧРФ для фіксованого п, а нумерацiї прикладiв 3, 7 та 9  як ефективні нумерацiї всiх n-арних ЧРФ.

Зафiксуємо для кожного n1 ефективну нумерацiю n-арних ЧРФ. Звичайно це буде нумерація на основі кодування МНР-програм (приклад 6), інколи нумерація на основі кодування МТ (приклад 8). Вказані нумерації назвемо стандартними нумераціямиn-арних ЧРФ. Для стандартних нумерацій введемо наступні позначення.

n-арну ЧРФ з номером m позначатимемо . У випадку n=1 вживатимемо спрощене позначення m.Область визначення та область значень функцiї  позначатимемо вiдповiдно D та E. У випадку n=1 вживатимемо позначення Dm та Em.

Номер функцiї назвемо також iндексом функцiї. Номер функцiї в стандартній намерації назвемо стандартним iндексом функцiї.

Нумерація  називається Гьодельовою, якщо існують рекурсивні функції f та g такі:

 для кожного тN = f(m);

 для кожного kN k = .

Це означає, що існує пара алгоритмів, перший з яких за стандартним індексом функції знаходить її -індекс, а другий за -індексом функції знаходить її стандартний індекс.

Нехай F  деякий клас функцій вигляду Х→Y, для якого задана нумерація : NF. З кожною такою нумерацією  зв'язана функція и: NХ→Y, що визначається умовою и(п, х) = п(х). Таку функцію и називають спряженою з нумерацією . Нумерація називається обчислюваною, якщо спряжена з нею функція є ЧРФ.

Для довiльного класу п-арних функцiй F клас всiх функцiй iз F фіксованої арності т будемо позначати Fт.

Функцiя и(y, x1, ...,xп) унiверсальна для класу Fп, якщо:

 для кожного значення m функцiя и(y, x1, ..., xп)Fп;

 для кожної fFп iснує таке m, що f(x1, ..., xn)=и(т, x1, ..., xп) для всiх значень x1, ..., xп .

Loading...

 
 

Цікаве