Нумерації. Теореми про нерухому точку, Детальна інформація

Тепер ((M) = ((26, 194, 7, 1050) = 226+2221+2229+21280\xF02D1.

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

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

) = 4((C(n, m)-2);

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

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

\xF067(M(t)) = 4(\xF067(t)+3.

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

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

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

) = 3((C(n, m)-2);

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

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

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

)))+2 =

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

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

= 3(24 082 113 916+2 = 72 246 341 748+2 = 72 246 341 750.

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

=16:

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

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

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

\xF067(N\x263C(t0, t1)) = 4(C(\xF067(t0), \xF067(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 \xF02D код МНР-програми для 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 \xF02D код МТ для 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 \xF02D як ефективні нумерацiї всiх n-арних ЧРФ.