Алгоритмічні проблеми (стр. 4 из 7)
Введемо на E* деякі стандартні функції і предикати. Якщо w = x1x2..xm і v = y1y2..yk – слова iз E*, то
а) con (w, v) = wv = x1x2..xmy1y2..yk, con (e, v) =con (v, e) = v;
б) del(w) = d(w) = x2x3..xm, del(e) = e;
в) для всіх літер ai із E предикат hai(w) = T (істино), коли x1 = ai, і hai(w) = F (хибно), коли перша літера x1 у слові w не дорівнює ai (1 <= i <= m), причому для всіх i
hai(e) = F.
Якщо а – довільна літера із E*, то через (a^n) позначається слово, що склдається із n літер a.
Клас схем програм KS-2 містить (n + 1) унарних функціональних символів fa1, fa2., fan, g, один константний символ b і n унарних предикатних символів pa1, pa2., pan,
В класі інтерпретацій KI-2 схем із KS-1 множина D завжди співпадає з множиною E* всіх слів в алфавіті E, а кожне відображення I із KI-2 задовільняє наступним вимогам:
1) I(b) = е;
2) I (fai(x)) = con (I(x), 'ai')= I(x) ai для всіх літер ai із E;
3) I (g(x)) = del (I(x));
4) I (pai(x)) = hai (I(x)) для всіх літер ai із E;
5) I(xi) єE* для всіх вхідних змінних СОА і СПА виду (6), (7), і I(y) = e для всіх інших змінних із пам'яті вищезгаданих схем алгоритмів.
Замінивши у (5) сімволи fai, g, b і hai згідно з інтерпретацією I із класу KI-2 ми отримаємо програмноподібну структуру, рядки якої будемо називаті командами. Тому схеми алгоритмів (6) і (7) iз класу KS-2 далі інтерпретуються, як відповідні алгоритми (програми) iз класу прграм KП-2, функціонування яких подібно до функціонування програм, що написані на мовах програмування типу Паскаль, коли ці програми працюють на даних типу string. Ясно, що функціонуваня команд програм із класу КП-2 аналгічно, з точністю до інтерпретації символів її схеми, до функціонуваня команд програм із класу КП-1, яке було описано вище.
Зауважимо також, що по аналогії з N-БРМ БN можна ввести E-БРМ БE, що реалізує програму із КП-2, а також NE-БРМ БNE. БNE можна розглядати як «об'єднання» програм ПN i ПE для БN i БE в тому сенсі, що множини регістрів БN i БE не перетинаються, але вони мають загальний блок управління (i спільні мітки), в якій поміщена спільна програма ПNE, в яку входять всі команди, як із ПN так і із ПE.
Часткові або всюдиозначенні функцію g: E*вх –>E*вх, яка задана на множині слів довільного алфавіту E, або предикат P: E* –> T, F, будемо називати E – рекурсивною функцією (предикатом), або RE-функцією (RE-предикатом), якщо існує програма із класу КП-2 П1g, що обчислює g (P).
Як відомо [1], [2], за допомгою кодуючої функції доводиться, що, в певному сенсі, клас R-функцій (R-предикатів) і клас RE-функцій (RE-предикатів) є еквівалентні.
Приклади доведення по побудові RE-рекурсивності функцій і предікатьв наведені далі.
Побудуємо алгоритм, що обчислює функцію
z:= f1 (x, y) = x + y.
x, y! z
| q10q11q12q13q14q15q16q17q18q19 | x1 = x (q11, q11)y1 = y (q12, q12)z1 = 0 (q13, q13)P0 (x1) (q16, q14)z1 = z1 + 1 (q15, q15)x1 = x1 -^ 1 (q13, q13)P0 (y1) (q19, q17)z1 = z1 + 1 (q18, q18)y1 = y1 -^ 1 (q16, q16)z = z1 (Я, Я) |
Побудуємо алгоритм (не оптимальний), що заносить в z значення функції добутку x i y, тобто z:= f1 (x, y) = x * y.
x, y! Z
| q20q21q22q23 | x2 = x (q21, q21)y2 = y (q22, q22)z2 = 0 (q23, q23)P0 (y2) (q25, q10) |
| q10q11q12q13q14q15q16q17q18q19 | x1 = z2 (q11, q11)y1 = x (q12, q12)z1 = 0 (q13, q13)P0 (x1) (q16, q14)z1 = z1 + 1 (q15, q15)x1 = x1 -^ 1 (q13, q13)P0 (y1) (q19, q17)z1 = z1 + 1 (q18, q18)y1 = y1 -^ 1 (q16, q16)z2 = z1 (q24, q24) |
| q24q25 | z2 = z1 (q23, q23)z = z2 (Я, Я) |
Нехай алфавіт Е = a, b. Побудуємо алгоритм, що обчислює предикат Pe(w), де Pe(w) = T тоді і тільки тоді, коли w є пусте слово із E*, тобто w = e.
x! q [.t.], q [.f.]
q10 x1 = x (q11, q11)
q11 ha(x1) (q [.f.], q12)
q12 hb(x1) (q [.f.], q [.t.])
Побудуємо алгоритм (не оптимальний), що заносить в z значення функції con (x, y) = xy, тобто z:= g1 (x, y) = con (x, y) = = xy для слів із Е = a, b.
x, y! Z
| q20q21q22 | x2 = x (q21, q21)y2 = y (q22, q22)z2 = e (q10, q10) |
| q10q11q12 | x1 = y2 (q11, q11)ha(x1) (q22, q12)hb(x1) (q22, q28) |
| q22q23q24 | ha(y2) (q23, q25)x2 = con (x2, a) (q24, q24)y2 = del(y2) (q22, q22) |
| q25q26q27q28 | 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) =
-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) правдиве,Cm (x) =
0, якщо M(x) неправдиве
обчислювана. Це рівносильно твердженню про те, що предикат М (х) рекурсивний Предикат М (х) називається нерозв'язним, якщо він не є розв'язним. У літературі використовуються наступні терміни, еквівалентні твердженню про те, що предикат М (х) розв'язний:
М (х) рекурсивний,
М (х) має рекурсивну проблему дозволу,
М (х) рекурсивно розв'язний,
М (х) обчислювальний.
Алгоритм, що обчислює см, називається обчислювальною процедурою, для M(x).
1. Нерозв'язні проблеми в теорії обчислюваності
У більшості випадків докази нерозв'язності ґрунтуються на діагональному методі, як, наприклад, у наступному важливому прикладі.
1.1. Теорема.Проблема «x ÎWx» (чи, що еквівалентно, «функція fx(х) визначена», чи «Рx(х)¯», чи «функціяyu(х,х)визначена») нерозв'язна.
Доведення. Характеристична функція цієї проблеми задається наступною формулою:
1, якщо xÎ Wxf(x)=0, якщо xÏ Wx
Припустимо, що функція f обчислювана, і приведемо це припущення до протиріччя. Саме за допомогою діагонального методу ми побудуємо обчислювану функцію g, таку, що Dom(g)¹Wx(= Dom(фx)), при всіх х, чого, мабуть, бути не може.
Як завжди при використанні діагонального методу, ми будемо прагнути до того, щоб множина Dom(g) відрізнялося від Wx у njxці х. Тому будемо домагатися того, щоб
x Î Dom (g)Ûx ÏWx
Визначимо тепер функцію g у такий спосіб:
g(x)=0, якщо xÏ Wx (тобто якщо f(x)=0),
не визначена, якщо xÎ Wx (тобто якщо f(x)= 1).
Оскільки функція f обчислювана, то (по тезі Черча) обчислювана і функція g, що і дає необхідне протиріччя. (Більш докладно, оскільки функція g обчислювана, візьмемо таке т, що g=fm, тоді тÎWmÛтÎ Dom (g)ÛтÏWm, чого не може бути.)
Отже, ми робимо висновок, що функція f не є обчислюваною, і, отже, проблема «x ÎWx» нерозв'язна. ÿ
Зауважимо, що ця теорема зовсім не затверджує, що ми не можемо для будь-якого конкретного числа а сказати, чи буде визначене значення fa (a). Для деяких чисел зробити це дуже просто. Наприклад, якщо ми написали програму Р, щообчислює тотальну функцію, і Р=Рa, то ми відразу знаємо, що значення fa (a) визначено. Теорема говорить лише, що не існує єдиного загального методу рішення питання про те, чи буде fx(х) визначено; іншими словами, не існує методу, що працює при всіх х.
Простий наслідок цього результату полягає в наступному.
1.2. Наслідок.Існує обчислювана функція h, для якої обидві проблеми «x Î Dom(h)» і «х Î Ran(h)» нерозв'язні.
Доведення. Покладемо
x, якщо xÎ Wxh(x)=
не визначена, якщо xÏ Wx
Тоді в силу тези Черча і обчислюваності універсальної функції yu функція h обчислювана (більш формально ми маємо h(x)@ x1 (yu(х, х)), а ця функція обчислювана як результат підстановки). Ясно, що x Î Dom(h)Û xÎ WxÛx Î Ran (h), так що обидві проблеми «x Î Dom(h)» і «х Î Ran(h)» нерозв'язні.