Її використання

Tеза Чорча. Клас ЧРФ збігається з класом п-арних АОФ, заданих на множині натуральних чисел.

Поняття АОФ не є строго визначеним математичним поняттям, тому теза Чорча математичному доведенню не пiдлягає. Теза Чорча є природно-науковим фактом, що пiдтверджений такими результатами:

1) істотно рiзнi формальнi уточнення поняття АОФ, запропонованi piзними авторами в рiзний час, виявилися еквiвалентними в смислi завдання одного й того ж класу функцiй;

2) перехiд вiд завдання функцiї в одному формалiзмi до завдання цiєї ж функцiї в iншому формалiзмi конструктивний, тобто вiн здiйснюється певним алгоритмом (наприклад, за операторним термом алгебри ЧРФ ефективно будується МНР-програма, що задає ту ж функцiю);

3) для кожного з таких формалiзмiв усi заданi в ньому функцiї - алгоритмiчно обчислюванi в iнтуїтивному смислi;

4) всi вiдомi до цих пiр алгоритмiчно обчислюванi п -арні функцiї на N виявилися частково рекурсивними. Нiкому ще не вдалось навести приклад функцiї, яку можна було б вважати алгоритмiчно обчислюваною в iнтуїтивному смислi, але яка не є ЧРФ.

Із тези Чорча як наслiдок випливає, що клас РФ збігається з класом тотальних АОФ, заданих на множинi натуральних чисел.

Значення тези Чорча полягає в наступному.

1) Прийняття ТЧ перетворює iнтуїтивнi поняття алгоритму, обчислюваностi, розв’язностi в об’єкти математичного вивчення. Це дає можливiсть ставити i розв’язувати питання про алгоритмiчну обчислюванiсть функцiй, алгоритмiчну розв’язнiсть чи нерозв’язнiсть масових проблем.

2) Використання ТЧ як своєрiдної аксiоми дозволяє в багатьох випадках замiнити формальнi завдання алгоритмiв на неформальнi їх описи. Це дає iстотне спрощення доведень, дозволяє видiлити основну iдею доведення чи побудови, звiльняючи його вiд зайвих деталей. Проте доведення на основi ТЧ завжди має бути ретельно аргументованим! При виникненнi сумнiвiв треба бути здатним провести чисто формальне доведення. Таким чином, є всі підстави прийняти тезу Чорча.

ЛЕКЦІЯ 8

ПЛАН

1. Поняття геделевої нумерації, приклади геделевих нумерацій.

2. Геделеві нумерації ЧРФ.

1. Поняття геделевої нумерації, приклади геделевих нумерацій

Розглянемо приклади ефективних нумерацій формальних моделей алгоритмів та АОФ.

Приклад 1. Однозначну ефективну нумерацiю всiх МНР-програм задамо на основi кодування МНР-програм як скiнченних послiдовностей команд МНР. Кодування команд q задамо так:

q(Z (n)) = 4 × n;

q(S (n)) = 4 × n +1;

q(T (т,n)) = 4 × С (т,n)+2;

q(J (m,n, q +1))=4 × С (С (т,n), q)+3.

Зрозумiло, що q - бiєктивне вiдображення множини всiх команд МНР на N. Використовуючи розглянуту вище бiєкцiю n: → N, задамо кодування t усiх МНР-програм.

Якщо P - МНР-програма I ₁ I ₂... I_к , то t(P)= n(q(I ₁),..., q(I_k)). Але n та q бiєктивнi, тому t теж бiєкцiя. Тодi j=t^-1 - шукана однозначна нумерацiя.

Нумерацiя j ефективна. Справдi, за кожною МНР-програмою P ефективно обчислюється її номер t(P). З iншого боку, за кожним n Î N ефективно визначається МНР-програма P =j(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.

Для прикладу знайдемо P =j(5119). Маємо 5119+1=5120=2¹⁰+2¹², звiдки дістаємо a₁=10, a₂=12-10-1 = 1. Але 10=2+4× C (1,0), тому P має вигляд

1) T(1,0)

2) S(0).

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

m(q_ia_j ® q_ka₁)= 3 × C ⁴(i, j, k, l);

m(q_ia_j ® q_ka₁L)= 3 × C ⁴(i, j, k, l)+1;

m(q_ia_j ® q_ka₁R)= 3 × C ⁴(i, j, k, l)+2.

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

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

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

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

g(S ^{n +1}(t ₀, t ₁,..., t_n)) = 4 × C (C^{n +1}(g(t ₀), g(t ₁),..., g(t_n)), n -1)+1;

g(R (t ₀, t ₁)) = 4 × C (g(t ₀), g(t ₁))+2;

g(M (t)) = 4 × g(t)+3.

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

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

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

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

g(S ^{n +1}(t ₀, t ₁,..., t_n)) = 3 × C (C^{n +1}(g(t ₀), g(t ₁),..., g(t_n)), n -1)+1;

g(R (t ₀, t ₁)) = 3 × C (g(t ₀), g(t ₁))+2.

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

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

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

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

g(S ^{n +1}(t ₀, t ₁,..., t_n)) = 4 × C (C^{n +1}(g(t ₀), g(t ₁),..., g(t_n)), n -1)+1;

g(^N D (t ₀, t ₁, t ₂)) = 4 × C ³(g(t ₀), g(t ₁), g(t ₂))+2;

g(^N ☼ (t ₀, t ₁)) = 4 × C (g(t ₀), g(t ₁))+3.

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

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

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

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

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

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

n -арну ЧРФ із номером m позначатимемо j . У випадку n =1 уживатимемо також спрощене позначення j _m .

Область визначення і область значень функцiї j позначатимемо вiдповiдно D та E . У випадку n =1 уживатимемо також позначення D_m і E_m .

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

Маючи деякий iндекс ЧРФ f, можна ефективно знайти як завгодно великий iндекс тої ж функцiї f:

Твердження 1. Для кожної ЧРФ j та для кожного l Î N ефективно знаходиться k Î N, таке, що k>l і j = j .

Обмежимось розглядом випадку завдання нумерацiї n -арних ЧРФ кодами МНР-програм. У кiнець заданої МНР-програми P_m допишемо l команд вигляду T(0,0). Нехай k - код так отриманої МНР-програми. Зрозумiло, що k > l та j = j .

Перехiд вiд одної з описаних вище нумерацiй ЧРФ до iншої такої нумерацiї ефективний, тобто iснує алгоритм, який за номером функцiї f в одній нумерацiї j дозволяє знайти номер f в іншій нумерацiї y. Наприклад, алгоритм переходу вiд нумерацiї прикладу 6 до нумерацiї прикладу 8: за номером k як за кодом МНР-програми будуємо програму P_k; за P_k будуємо МТ, що задає ту ж функцiю; код такої МТ i є шуканим номером у нумерацiї прикладу 8.

Нумерації з описаною вище властивістю називають геделевими.

Поиск по сайту: