q10
q11
q12
x1 = y2 (q11, q11)
ha (x1) (q22, q12)
hb (x1) (q22, q28)
q22
q23
q24
ha (y2) (q23, q25)
x2 = con (x2, a) (q24, q24)
y2 = del (y2) (q22, q22)
q25
q26
q27
q28
hb (y2) (q26, q10)
x2 = con (x2, b) (q27, q27)
y2 = del (y2) (q25, q25)
z = x2 (Я, Я)
4. Операторні та предікатні Алгоритм-ІІ
В
(Рекурсівні Функції на областях, что відмінні від N)
Оскількі БРМ працює Тільки з натуральними числами, наше визначення обчіслюваності и возможности розв'язання застосовано Тільки до функцій и предікатів від натуральних чисел. Ці Поняття легко пошірюються на Другие види об'єктів (тоб цілі числа, поліномі, матріці и т.д.) помощью кодування.
кодування области D об'єктів назівається Явне ї Ефективне відображення О±: D в†’ N. Мі будемо Говорити, что об'єкт О± € D кодується натуральним числом О± (d). Припустиме, что f є функцією з D в D; тоді f природно кодується функцією f * з N в N, что відображає код шкірного об'єкта d € Dom (f) у код об'єкта f (d). У явному віді це можна записатися як
В
f * = О± В· F В· a -1
Тепер можна пошіріті визначення Мнр-обчіслюваності на область D, рахуючи функцію f обчислюваного, ЯКЩО f * -обчіслювана функція натуральних чисел.
Приклад. Розглянемо область Z. Явне кодування можна Задати функцією О±, де
2n, ЯКЩО n Ві 0,
О± - (n) = p>-2n-1, ЯКЩО n <0.
Тоді О± -1 задається так:
(1/2) m, ЯКЩО m хлопця,
О± -1 (M) =
(-1/2) (M +1), ЯКЩО m непарний. br/>
Тепер розглянемо функцію х- 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). p> 1. Нерозв'язні проблеми в Теорії обчіслюваності
У більшості віпадків докази нерозв'язності грунтуються на діагональному методі, як, Наприклад, у Наступний ВАЖЛИВО прікладі.
1.1. Теорема. Проблема В«x ГЋ W x В» (Чі, что еквівалентно, В«функція f x (х) ВизначиВ», чі «Рx (х) ВЇ В», чі В«функція y u (х, х) Визначи В») нерозв'язна.
Доведення. характеристичностью функція цієї проблеми задається Наступний формулою:
1, ЯКЩО xГЋ W x
f (x) = 0, ЯКЩО xГЏ W x
Припустиме, что функція f обчіслювана, и пріведемо це припущені до протіріччя. Саме за помощью діагонального методу ми побудуємо обчислюваного функцію g, таку, что Dom (g) В№ W x (= Dom (ф x )), при всех х, чого, мабуть, буті НЕ может.
Як всегда при вікорістанні діагонального методу, ми будемо прагнуті до того, щоб мн...
