4. Теорія програмування та обчислень

9. Функції складності (сигналізуючі) за часом та за пам’яттю. Теорема про прискорення.

В теорії складності обчислень розглядаються обчислювальні задачі чи задачі розпізнавання (аналізу) і досліджуються питання складності розв’язку цих задач на відповідних обчислювальних пристроях. Основний інтерес представляє отримання оцінок складності задач по часу і по пам’яті. Відповідно при розгляді обчислень на машинах Тьюрінга вводяться поняття часової сигналізуючої і сигналізуючої по пам’яті.

Нехай A=(K ,Σ, A`, H, q₀, q*)- машина Тьюрінга, що розпізнає мову L(A) , де L(A) Σ*. Вважається, що при довільному вхідному слові w є Σ* машина Тьюрінга A , розпочавши роботу в конфігурації q₀w , зупиниться через скінченну кількість кроків (через t_A(w) кроків) і при цьому вона використає l_A(w) комірок робочої стрічки.

При цьому якщо вона зупиниться в кінцевому стані q* , то маємо, що w є Σ* , а в іншому випадку, маємо, що Σ ∉ w . Тепер визначимо для машини Тьюрінга A часову сигналізуючу T_A(x) і сигналізуючи по пам’яті L_A(x) .

Покладемо, що

T_A(x)=max{t_A(w)|wє Σ* , |w|<=x}

L_A(x)=max{t_A(w)|wє Σ* , |w|<=x}

Будемо говорити, що задача розпізнавання w є Σ* має верхню (часову) оцінку (в.о.) T(x) , якщо існує машина Тьюрінга A , що розпізнає мову L і T_A(x) <= T(x)для всіх натуральних чисел x .

Будемо говорити, що задача розпізнавання w є Σ*має нижню (часову) оцінку (н.о.) T(x) , якщо доведено, що для довільної машини Тьюрінга A , що розпізнає мову L виконується співвідношення T (x) <= T_A (x) для всіх натуральних чисел x .

Будемо говорити, що задача розпізнавання w є Σ* має оптимальну (часову) оцінку (о.о.) T(x) , якщо функція T(x) є одночасно н.о. і в.о. для цієї задачі.

Теорема про прискорення. Нехай деяка задача розв’язується на МТ A з часовою сигналізуючою T_A (x), де T_A (x) ≥ x² . Нехай c - довільне натуральне число і c ≥ 2 . Тоді існує МТ B , яка розв’язує ту ж задачу з часовою сигналізуючою T_B(x), де T_B(x) <= 1/c T_A(x) для майже всіх x .

Доведення. Ідея доведення полягає в укрупненні комірок.

Нижня квадратична оцінка тут важлива, бо на перебудову слова в алфавіті Σ потрібний квадратичний час, якщо Σ≥|2|.

Якщо ж вхідні і вихідні слова представлені в однобуквеному алфавіті, то в формулюванні теореми замість нижньої оцінки x² можна взяти оцінку xlog x.

4. Теорія програмування та обчислень

10. Функції, елементарні за Кальмаром

Функція f(х,у) отримується з функції g(х,у) за допомогою операції сумування, якщо для всіх х, у є N маємо .

Функція f(х,у) отримується з функції g(х,у) за допомогою операції мультиплікації, якщо для всіх х, у є N маємо .

Функція f(x₁, ..., x_n) елементарнa (елементарнa за Кальмаром), якщо вона може бути отримана з функцій s, I , + та за допомогою скінченної кількості застосувань операцій суперпозиції, сумування і мультиплікації.

Наступні співвідношення встановлюють елементарність відомих функцій:

1) о(x) = х х;

2) ;

3) (х) = s(о(х));

4) =

5) sg(x) = x (х 1);

6) nsg(x) = 1(х) х;

8) mod(х, у) = х (у х / у])

9)C(x, y)=[((x+y)² + 3*x+y)/2];

10) x! =^x∏_i=1 i

11) x^y=^y∏ _i=1 I²₁(x,i).

Нехай f(х) отримана за допомогою операції кускового завдання з функцій g₁(x), ..., g_n(x) та допоміжних функцій α₁(x), ..., α_n(x): f(х) = g₁(x)nsg(α₁(x))+...+g_n(x)nsg(α_n(x)).

Тоді f(х) – елементарна функція, якщо функції g_i(x), α_i(x), де 1 i n, елементарні.

Нехай f(х) = μ_yα(x)(g(х, у)=0) отримана за допомогою операції обмеженої мінімізації. Тоді функцію f(х) можна задати у вигляді f(х)=h(х,α(x)), де .

Звідси f(х) елементарна функція, якщо функції g(х,у) та α(x) елементарні.

Кажуть, що функція f(х,у) отримується за допомогою операції обмеженої рекурсії з функцій g(х), h(х, у, z) та φ(х, у), якщо:

1. функція f(х, у) задається схемою примітивної рекурсії f(х, 0) = g(х), f(х, у) = h(х, у 1), f(х, у 1)),

2. для всіх х, уєN маємо f(х, у)φ (х, у).

Теорема. Нехай функція f(х, у) отримана за допомогою операції обмеженої рекурсії з функцій g(х), h(х, у, z) та φ(х, у), причому функції g(х), h(х,у,z) та φ(х,у) – елементарні. Тоді f(х, у) також елементарна.

Визначимо операцію обмеженої рекурсії в загальному випадку. Нагадаємо, що є скороченим позначенням послідовності x₁, ..., x_n

Скажемо, що функція f( , у) отримана за допомогою операції обмеженої рекурсії з функцій g( ), h( , у, z) та φ( , у), якщо вона задана схемою примітивної рекурсії

f( , 0) = g( ), f( , у) = h( ,у 1), f( ,у 1)),

причому для всіх єNⁿ та уєN маємо f( , у)  φ( , у).

Має місце природне узагальнення теореми 9.1.1.

Теорема. Нехай функція f( , у) отримана за допомогою операції обмеженої рекурсії з елементарних функцій g( ), h( , у, z) та φ( , у). Тоді функція f( , у) також елементарна.