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

Приклад 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.

\x2192N, задамо кодування ( всiх МНР-програм так.

Якщо P \xF02D МНР-програма I1I2...Iк , то ((P) = ((((I1),..., ((Ik)).

Відображення ( та ( бiєктивнi, тому ( теж бiєкцiя. Тодi (=(-1 \xF02D шукана однозначна нумерацiя.

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

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

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

S(0); ((S(0))=4(0+1=1;

S(2); ((S(2))=4(2+1=9;

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\xF02D1.

Приклад 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}. Кодування ( команд МТ задамо так:

((qiaj(qka1) = 3(C4(i, j, k, l);

((qiaj(qka1L) = 3(C4(i, j, k, l)+1;

((qiaj(qka1R) = 3(C4(i, j, k, l)+2.

\x2192N, визначимо код МТ M, заданої послiдовнiстю команд I1I2...Iк , таким чином: ((M) = ((((I1),..., ((Ik)). Але ( та ( бiєктивнi, тому \xF072 теж бiєкцiя. Тодi (=(-1 \xF02D шукана однозначна нумерацiя послiдовностей команд МТ, але неоднозначна нумерацiя всiх МТ. Неважко переконатись, що така нумерацiя ефективна.

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

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

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

q0(( q1(L; ((q0(( q1(L)=3(C4(0,0,1,0)+1=3(C(1,0)+1=3(2+1=7;

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