Звідності. Відносна обчислюваність , Детальна інформація

Теорема 10 (Майхiлл). Якщо L крeативна, то L m-повна.

Наслідок 1. Множина L крeативна \xF0DB множина L m-повна.

Наслідок 2. Нeхай множина L проста, b=dm(L). Тодi 0m
Приклад 18. Множина К={С(x, у) | х(Dу } креативна.

Нехай В \xF02D довільна РПМ, нехай т \xF02D її індекс, тобто В=Dт. Тоді х(В ( х(Dт ( С(x, т)(К. Отже, ін'єктивна РФ С(x, т) : В(1 К. Отже, РПМ К \xF02D т-повна, тому К креативна.

3. ФОРМАЛІЗАЦІЯ ВІДНОСНОЇ ОБЧИСЛЮВАНОСТІ. РЕЛЯТИВІЗАЦІЯ ТЕОРЕМ

Обмежимося розглядом вiдносної обчислюваності п-арних функцій на N, причому обчислюваності вiдносно тотальних функцiй.

Функцiя f обчислювана вiдносно тотальної функцiї (, яку називають оракулом, якщо iснує алгоритм для обчислення (, який може при необхiдностi брати потрiбнi значення функцiї (.

Формально поняття вiдносної обчислюваностi уточнимо через поняття МНР з оракулом (скорочено МНРО). Для МНРО додається новий тип команд O(n) \xF02D звернення до оракула. Для виконання таких команд МНРО мусить з’єднатися з певним оракулом (.

Виконання команди O(n) означає, що вмiст n-го регiстру заси-лається в оракул (, який повертає в n-й регістр значення функцiї ( від цього вмiсту. Пiсля виконання команди O(n) наступною виконується чергова за списком команда програми МНРО.

Програмою МНРО назвемо скiнченну послiдовнiсть команд МНРО. Смисл МНРО-програми залежить вiд конкретного оракула. МНРО-програму P, яка виконується МНРО з оракулом (, позначаємо P(.

МНРО-програма P обчислює функцiю f : Nn( N вiдносно оракула (, або (-обчислює функцiю f, якщо

f(a1 , a2 , ..., aп)=b ( P((a1 , a2 , ..., aп)(b.

Функцiя f МНРО-обчислювана вiдносно (, або (-обчислювана, якщо iснує МНРО-програма P, яка обчислює f вiдносно (.

та ( за допомогою скiнченної кiлькостi застосувань операцiй Sn+1, R та M.

Тeорeма 3.1. Функцiя f є (-ЧРФ \xF0DB f є МНРО-обчислюваною вiдносно (.

Вкажемо деякi елементарнi властивостi (-ЧРФ:

о1) ((ЧРФ( (тут ЧРФ( позначає клас всiх (-ЧРФ).

о2) Для довiльного оракула ( маємо ЧРФ (ЧРФ(.

о3) Якщо тотальна функцiя ( є (-ЧРФ, то ЧРФ( (ЧРФ(.

о4) Якщо ( рекурсивна, то ЧРФ( =ЧРФ.

Для вiдносно обчислюваних функцiй можна сформулювати релятивний аналог тези Чорча, який називають тезою Тьюрiнга:

Теза Тьюрінга. Клас (-ЧРФ співпадає з класом п-арних функцій на N, алгоритмічно обчислюваних відносно (.

Зрозумiло, що тезу Чорча можна розглядати як окремий випадок тези Тьюрiнга. Тезу Тьюрiнга скорочено позначатимемо ТТ.

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

((Z(n)) = 5(n;

((S(n)) = 5(n+1;

((T(т, n)) = 5(С(т,n)+2;

((J(m ,n, q+1)) = 5(С(С(т,n), q)+3;

((O(n)) = 5(n+4.