37.Кодування. Нумерації, ефективні нумерації. Універсальні класи алгоритмів.

Під кодуванням множини А на множині В будемо розуміти ін’єктивне та сюр’єктивне відображення  : А→В таке, що існують алгоритми A та B:

для кожного аА A(а)(а);

для кожного bB B(b)= ^-1(b).

Нумерацiєю множини А називають сюр’єктивне функцiональне вiдображення : N →А.

Однозначною нумерацiєю множини А називають бієктивне вiдображення : N →А.

Нумерацiю : N →А називають ефективною, якщо iснують алгоритми A та B такі:

для кожного аА A(а)^-1(а);

для кожного nN B(п)=(п).

Нехай  – Х-А-алгоритм,  – Y-В-алгоритм,  – однозначне кодування X в Y,  – однозначне кодування A в B.

Алгоритми  та  назвемо еквівалентними з точністю до кодувань  та , якщо:

– для кожного хХ (х) = ^–1(((х)));

– для кожного yY (y) = ((^–1(y))).

Алгоритми  та  назвемо еквівалентними, якщо  та  еквівалентні з точністю до деяких кодувань  та .

Клас алгоритмів  називають універсальним, якщо кожний алгоритм еквівалентний деякому алгоритму із .

Таким чином, : N →А  ефективна нумерація  ^-1: А→N  кодування А на N.

Введемо однозначні ефективні нумерацiї пар та n-ок натуральних чисел, які називаються канторовими нумераціями.

Всi пари натуральних чисел розташуємо в послiдовнiсть так:

пара (x, y) передує парі (u, v)  x+y<u+v або (x+y = u+v та x<u).

Номер пари (x, y) в такiй послiдовностi позначають C(x, y) та називають канторовим номером пари (x, y).

Неважко переконатись, що C(x, y) = [(x+y+1)(x+y)/2]+x

Лiву та праву компоненти пари з номером n позначають вiдповiдно l(n) та r(n). Функцiї l(n) та r(n) називають вiдповiдно лiвою та правою координатними функцiями.

Функцiя C(x, y) задає бiєкцiю NN→N, пара функцiй (l(n), r(n)) задає бiєкцiю N→NN. При цьому функцiї C, l та r зв’язaнi такими тотожностями:

C(l(n), r(n)=n; l(C(x, y))=x; r(C(x, y))=y.

Маючи нумерацiю пар натуральних чисел, можна ввести нумерацiю n-ок натуральних чисел для довiльного n>2:

C^п(x₁, x₂,..., x_п)=C^п1(C(x₁, x₂), x₃,..., x_п)=C(...С(C(x₁, x₂), x₃),...), x_п).

Координатнi функцiї C_n1 , ..., C_nn вводимо так:

Нехай C^п(x₁, x₂,..., x_п)=m; тоді C_n1(m)=x₁; C_n2(m)=x₂; ... , C_nn(m)=x_n.

Для функцiй C^п, C_n1 , ..., C_nn справджуються такi тотожностi:

C^п(C_n1(x), ..., C_nn(x))=x;

C_nk(C^п(x₁, x₂,..., x_п))=x_k, 1kn.

Теорема 7.1.1. 1) Функцiї C(x, y), l(n) та r(n) є ПРФ.

2) Функцiї C^п, C_n1 , ..., C_nn є ПРФ.

38.Канторові нумерації. Функції Гьоделя. Елімінація примітивних рекурсії.

Кодування множини A на множині B – це ін'єктивне та сюр'єктивне відображення _: А→В таке, що існують алгоритми  та :

– для кожного аА (а)(а);

– для кожного bB (b) = ^–1(b).

Нумерацією множини А назвемо сюр'єктивне функціональне відобра-ження _: N →А. Однозначною нумерацією множини А назвемо бієктивне відображення _: N →А.

Нумерація _: N→А ефективна, якщо існують алгоритми  та :

– для кожного аА (а)^–1(а);

– для кожного nN (n) = (n).

Таким чином, _: N→А – ефективна нумерація  ^–1 : А→N – кодування А на N.

Введемо однозначні ефективні нумерації пар та n-ок натуральних чисел, які називаються канторовими нумераціями.

Всі пари натуральних чисел розташуємо в послідовність так:

пара (x, y) передує парі (u, v)  x+y<u+v або (x+y = u+v та x<u).

Номер пари (x, y) в такій послідовності позначають C(x, y) та називають канторовим номером пари (x, y).

Неважко переконатись, що C(x, y) = [(x+y+1)(x+y)/2]+x

Ліву та праву компоненти пари з номером n позначають відповідно l(n) та r(n). Функції l(n) та r(n) називають відповідно лівою та правою координатними функціями.

Функція C(x, y) задає бієкцію NN→N, пара функцій (l(n), r(n)) задає бієкцію N→NN. Функції C, l та r зв'язaні тотожностями:

C(l(n), r(n)) = n;

l(C(x, y)) = x;

r(C(x, y)) = y.

Маючи нумерацію пар натуральних чисел, можна ввести нумерацію n-ок натуральних чисел для довільного n>2:

Cⁿ(x₁, x₂,..., x_n) = C^n–1(C(x₁, x₂), x₃,..., x_n) = C(...С(C(x₁, x₂), x₃),...), x_n).

Координатні функції C_n1 , ..., C_nn вводимо так:

Нехай Cⁿ(x₁, x₂,..., x_n)=m; тоді C_n1(m)=x₁; C_n2(m)=x₂; ..., C_nn(m)=x_n.

Для функцій Cⁿ, C_n1 , ..., C_nn справджуються такі тотожності:

Cⁿ(C_n1(x), ..., C_nn(x)) = x;

C_nk(C^п(x₁, x₂,..., x_n)) = x_k, 1kn.

Теорема 3.1.1. 1) Функції C(x, y), l(n) та r(n) є ПРФ.

2) Функції Cⁿ, C_n1 , ..., C_nn є ПРФ.

Номером (індексом) довiльної формули  вважатимемо її код (). Всi тi натуральнi числа, якi не є кодами формул, вважатимемо номером формули x₀=x₀ .

Зрозуміло, що так введена нумерація  неоднозначна. Формулу з номером n позначатимемо _n .

Кодувати довiльну скiнченну послiдовнiсть натуральних чисел. дозволяє також функція Гьоделя (x, y) = mod(l(x), 1+(y+1)r(x)).

З визначення випливає, що (x, y) є ПРФ.

Теорема 7.1.2 (про основну властивість функції Гьоделя). Для довiльної скiнченної послiдовностi натуральних чисел b₀, b₁, ..,b_n існує натуральне число t таке, що маємо

(t, i)=b_i для всiх i{0,...,n}.

Використання функції Гьоделя дає змогу промоделювати операцiю примiтивної рекурсiї операціями суперпозиції та мінімізації:

Теорема 7.1.3.(про елімінацію операції примітивної рекурсії) Функцiя f=R(g, h) може бути отримана iз функцiй g, h, базових функцiй і функцiй +,  за допомогою скiнченної кiлькостi застосувань операцiй Sⁿ⁺¹ та М.

Наслiдок. Клас ЧРФ спiвпадає з класом функцiй, отриманих із функцій о, s, I , +,  за допомогою операцiй Sⁿ⁺¹ та M.