Алгоритмічні проблеми (стр. 5 из 7)

З теореми 1.1 виводиться ще одна важлива нерозв'язна проблема:

1.3. Теорема (проблема зупинки). Проблема «функція ф_x(у) визначена» (чи в еквівалентній формі«Р_x(y)¯, чи «y Î W_x» нерозв'язна.

Доведення. Міркуючи неформально, ми відразу бачимо, що якби проблема «функція ф_x(у) визначена» була б розв'язна, то була б розв'язна і більш проста проблема «функція ф_x(х) визначена», що суперечить теоремі 1.1.

Щоб провести всі ці міркування більш докладно, розглянемо характеристичну функцію проблеми^ «функція ф_х(у) визначена», що має наступний вид:

1, якщо ф_х(у) визначена

g (x, y)=

0, якщо ф_х(у) невизначена

Якби функція g була обчислювана, то обчислюваною була б і функція f(x)=g (x, х), але f є характеристична функція проблеми «хÎW_x» і, отже, не обчислювана в силу теореми 1.1. Отже, функція g не обчислювана, і тим самим проблема «ф_x(y) визначена» нерозв'язна. ÿ

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

Розглянута в теоремі 1.1 нерозв'язна проблема «хÎW_x» важлива з кількох причин. Одна з них полягає в тому, що нерозв'язність багатьох проблем можна довести, показавши, що вони принаймні не простіші, ніж ця. Саме таким шляхом ми довели, що проблема зупинки (теорема 1.3) нерозв'язна: цей процес називається зведенням однієї проблеми до іншої.

Узагалі розглянемо деяку проблему М (х). Часто вдається показати, що рішення загальної проблеми М (х) привело б до рішення загальної проблеми «хÎW_x», Тоді говорять, що проблема «хÎW_x» зводиться до проблеми М (х). Іншими словами, якщо мається дозволяюча процедура для проблеми М (x), то ми можемо дати і дозволяючу процедуру для проблеми «хÎW_x». Таким чином, з можливості розв'язання М(х) випливає можливість розв'язання «хÎW_x», звідки ми негайно робимо висновок, що М (х) нерозв'язна.

Для зведення проблеми «хÎW_x» до інших проблем часто використовується s-m-n-теорема, як показує, наприклад, доведення наступного результату.

1.4. Теорема.Проблема«ф_x=0»нерозв'язна.

Доведення. Розглянемо функцію f, визначену формулою

0, якщо х Î W_x

f (x, y)=

не визначена, якщо x Ï W_x

Цю функцію ми ввели для того, щоб далі скористатися s-m-n-теоремою. Тим самим ми розглядаємо х як параметр, і нас цікавлять функції g_x, такі, що g_x(y)@ f (x, у). При цьому ми вибрали f так, що g_x=0ÛхÎW_x.

Теза Черча (чи підстановка з використанням 0 і y_u) показує, що функція f обчислювана. Тому існує тотальна обчислювана функція k(x), що дається s-m-n-теоремо., така, що f (x, у)@f_k(x); тобто f_k(x)=g_x. Таким чином, по визначенню

(*) х Î W_xÛf_k(x)= 0

Отже, питання про те, чи вірно, що х Î W_x, можна вирішити, відповівши спочатку на питання: чи вірно, що f_k(x)=0? Тим самим ми звели загальну проблему «хÎW_x» до загальної проблеми «ф_x=0»; оскільки перша з них нерозв'язна, те нерозв'язна і друга, що і було потрібно довести.

У зв'язку з тим що це перший приклад подібного роду, що зустрівся нам, розглянемо останню частину нашого міркування більш докладно. Нехай g-характеристична функція проблеми «ф_x=0», тобто

1, якщо ф_x=0

g(x)=

0, якщо ф_x¹0

Припустимо, що функція g обчислювана. Тоді обчислюваною буде і функція h (х) = g (k (х)). У той же час співвідношення (*) дає

1, якщо ф_k(x)=0, тобто xÎ W_x,

h(x)=

0, якщо ф_k(x)¹0, тобто xÏ W_x.

Тим самим у силу теореми 1.1 функція h не є обчислюваною. Стало бути, і функція g не є обчислюваною, так що проблема «ф_x=0» нерозв'язна. ÿ

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

Простий наслідок теореми 1.4 показує, що питання про те, чи обчислюють дві програми ту саму одномісну функцію, нерозв'язне. Зміст цього результату для теоретичного програмування також очевидний.

1.5. Наслідок.Проблема «ф_x=ф_y» нерозв'язна.

Доведення. Легко переконатися в тому, що ця проблема складніша проблеми «ф_x=0». Нехай с – таке число, що ф_с=0. Якщо f (x, y) – характеристична функція проблеми ф_x = ф_у, то функція g (x)=f (х, с) є характеристична функція проблеми «ф_x=0». По теоремі 1.4 функція g необчислювана, так що необчислювана і функція f. Отже, проблема «ф_x=ф_y» нерозв'язна.

У наступних результатах ми знову скористаємося s-m-n-теоремою для зведення проблеми «хÎW_x».

1.6. Теорема.Нехай c – довільне число. Наступні проблеми нерозв'язні.

(а) (Проблема входу) «cÎW_x» (чив еквівалентному формулюванні «Р_x (с)¯», чи «c Î Dom (ф_x)»);

(b) (Проблема виходу) «cÎE_x» (чи в еквівалентному формулюванні «с Î Ran (ф_x)»).

Доведення. Ми можемо звести проблему «хÎW_x» до обох цих проблем одночасно. Розглянемо функцію f (х, у), визначену в такий спосіб:

y, якщо х Î W_x

f (x, y)=

не визначена в протилежному випадку

(Маючи на увазі використовувати s-m-n-теорему, ми будемо розглядати функції g_x, для яких g_x(y)@ f (x, у). Функцію f ми вибрали таким чином, що c Î Dom (g_x)ÛхÎW_xÛcÎRan(g_x).) У силу тези Черча функція f обчислювана, так що s-m-n-теорема дає тотальну обчислювану функцію k, таку, що f (х, у)@ ф_k(x)(y). З визначення f ми бачимо, що

x Î W_xÞW_k(x)=E_k(x)=N

так що c Î W_k(x) і c Î E_k(x),і

x Ï W_xÞW_k(x)=E_k(x)=Æ

так що c Ï W_k(x) і c Ï E_k(x). Тим самим ми звели проблему «x Î W_x» до кожної з проблем «c Î W_x » і «c Î E_x «.

Завершуючи Доведення пункту (а) більш докладно, ми бачимо, що якщо g-характеристична функція проблеми «c Î W_x », то

1, якщо x Î W_x,

g (k(x))=

0, якщо x Ï W_x

Ця функція не є обчислюваною (теорема 1.1), так що функція g теж не може бути обчислюваною. Отже, проблема «c Î W_x » нерозв'язна.

Докладне доведення пункту (Ь) проводиться аналогічно. ÿ

Ми закінчимо цей параграф одним дуже загальним результатом про нерозв'язність, з якого негайно випливають теореми 1.4 і 1.6. При цьому ми знову скористаємося для зведення проблеми «х Î W_x »

s-m-n-теоремою.

1.7. Теорема (теорема Райса). Нехай ВÍ b₁ і B¹Æ, b₁.Тоді проблема«ф_xÎ B»нерозв'язна.

Доведення. Співвідношення для розв'язних множин (теорема 2–4.7) показують, що проблема «ф_xÎ B» розв'язна тоді і тільки тоді, коли розв'язна проблема «ф_xÎ b₁\ B». Тому без втрати загальності ми можемо вважати, що ніде не визначена функція f_Æне належить B (якщо це не так, то твердження можна довести для b₁\ B).

Виберемо деяку функцію g Î B. Розглянемо функцію f (x, у), що задається так:

g(y), якщо x Î W_x,

f (x, y)@

не визначена, якщо x Ï W_x.

Користаючись s-m-n-теоремою, ми одержуємо тотальну обчислювану функцію k (x), таку, що f (x, у) @ ф_k(x) (y),). Таким чином, ми бачимо, що

x Î W_xÞ ф_k(x) =g, тобто ф_k(x)ÎB

x Ï W_xÞ ф_k(x) =f_Æ, тобто ф_k(x)ÏB

Це значить, що за допомогою обчислюваної функції k ми звели проблему «х Î W_x » до проблеми

«ф_хÎ В». Тепер уже стандартним чином можна покласти, що проблема «ф_хÎ В» нерозв'язна.

Теорема 1.4, наприклад, негайно випливає з теореми Райса, якщо взяти В ={0}, а теорема 1.6 (а) – якщо взяти В={g Î b₁:c Î Dom(g)}. Аналогічно можна скористатися теоремою Райса і у наступних вправах.

1.8. Вправи.

1. Покажіть, що наступні проблеми нерозв'язні.

(a) «х Î Е_х «. (Указівка. Скористайтеся діагональним методом чи зведіть до цієї проблеми проблему

«x Î W_x» за допомогою s – m- n – теореми.)