39.Кодування та нумерації мнр-програм, мт, операторних термів відповідних алгебр.

Однозначну ефективну нумерац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х команд МНР на N. Використовуючи розглянуту вище бiєкцiю : →N, задамо кодування  всiх МНР-програм так.

Якщо P  МНР-програма I₁I₂...I_к , то (P) = ((I₁),..., (I_k)).

Відображення  та  бiєктивнi, тому  теж бiєкцiя. Тодi =^-1  шукана однозначна нумерацiя.

Нумерацiя  ефективна. Справдi, за кожною МНР-програмою P ефективно обчислюється її номер (P). З iншого боку, за кожним nN ефективно визначається МНР-програма P=(n). Справді, спочатку подамо число n+1 як суму зростаючих степенiв числа 2: n+1= + +...+ , де 0b₁<...<b_k. Далi визначимо послiдовнiсть чисел a₁, ..., a_k: a₁=b₁, a_i+1=b_i+1-b_i-1 для 1<i<k. Тепер за числами a₁, ..., a_k як за кодами команд МНР вiдновимо вiдповiднi команди. Послiдовнiсть цих команд i є шуканою МНР-програмою P.

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

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

Занумеруємо внутрiшнi стани МТ і символи стрiчки. Нехай Q={q₁,..., q_f}, T={a₁,..., a_m}. Кодування  команд МТ задамо так:

(q_ia_jq_ka₁) = 3C⁴(i, j, k, l);

(q_ia_jq_ka₁L) = 3C⁴(i, j, k, l)+1;

(q_ia_jq_ka₁R) = 3C⁴(i, j, k, l)+2.

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

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

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

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

(Sⁿ⁺¹(t₀, t₁,..., t_n)) = 4C(Cⁿ⁺¹((t₀), (t₁),..., (t_n)), n-1)+1;

(R(t₀, t₁)) = 4C((t₀), (t₁))+2;

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

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

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

(о) = 0;

(s) = 3;

(I ) = 3(C(n, m)-2);

(Sⁿ⁺¹(t₀, t₁,..., t_n)) = 3C(Cⁿ⁺¹((t₀), (t₁),..., (t_n)), n-1)+1;

(R(t₀, t₁)) = 3C((t₀), (t₁))+2.

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

Приклад 5. Ефективну нумерацiю всiх програмованих на N n-арних функц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);

(Sⁿ⁺¹(t₀, t₁,..., t_n)) = 4C(Cⁿ⁺¹((t₀), (t₁),..., (t_n)), n-1)+1;

(^N(t₀, t₁, t₂)) = 4C³((t₀), (t₁), (t₂))+2;

(^N☼(t₀, t₁)) = 4C((t₀), (t₁))+3.