Учебное пособие: Алгоритмічні проблеми

Тепер можна поширити визначення Мнр-обчислюваності на область D, рахуючи функцію f обчислюваною, якщо f^* –обчислювана функція натуральних чисел.

Приклад. Розглянемо область Z. Явне кодування можна задати функцією α, де

2n, якщо n ³ 0,

α^- (n) =

-2n-1, якщо n < 0.

Тоді α^-1 задається так:

(1/2) m, якщо m парне,

α^-1 (m) =

(-1/2) (m+1), якщо m непарне.

Тепер розглянемо функцію х- 1 на Z; позначаючи цю функ-ю через f, одержуємо f*:N →N, що задається:

1, якщо x:==0 (тобто х=α(0)),

f^* (x)= х- 2, якщох> 0 і х парне (тобто х=а(п), п>0),

х +2, якщо х непарне (тобто х=α(n), п < 0).

Написання програми, що обчислює f*, є рутинною вправою; отже, х- 1 є обчислювана функція на Z.

Приведене вище визначення очевидним образом розширюється на n-місцеві обчислювальні функції на області D і розв'язні предикати на D.

5. Алгоритмічні проблеми для L

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

1, якщо M(x) правдиве,

C_m (x) =

0, якщо M(x) неправдиве

обчислювана. Це рівносильно твердженню про те, що предикат М (х) рекурсивний Предикат М (х) називається нерозв'язним, якщо він не є розв'язним. У літературі використовуються наступні терміни, еквівалентні твердженню про те, що предикат М (х) розв'язний:

М (х) рекурсивний,

М (х) має рекурсивну проблему дозволу,

М (х) рекурсивно розв'язний,

М (х) обчислювальний.

Алгоритм, що обчислює с_м , називається обчислювальною процедурою, для M(x).

1. Нерозв'язні проблеми в теорії обчислюваності

У більшості випадків докази нерозв'язності ґрунтуються на діагональному методі, як, наприклад, у наступному важливому прикладі.

1.1. Теорема. Проблема «x Î W_x » (чи, що еквівалентно, «функція f _x (х) визначена», чи «Р_x (х) ¯ », чи «функція y _u (х,х)визначена») нерозв'язна.