Необхідні поняття, факти і нотація із інших математичних дисциплін
Відношення і предикати
Коли <q; a1., am> – кінцевий стан, то
Аналгічно до класів KS-1 схем алгоритмів і ¶нтерпретацій KI-1 введемо, відпвидно, класи KS-2 і KI-2
Операторні та предикатні алгоритми -ІІ
Наслідок. Існує обчислювана функція h, для якої обидві проблеми «x Î Dom(h)» і «х Î Ran(h)» нерозв'язні
Теорема. Нехай c – довільне число. Наступні проблеми нерозв'язні
Логіка висловлень (пропозиційна логіка) [1] – одна з базових теорій математичної логіки, на якій базуються більш складні формальні логіки
Необхідно побудувати кон’юктивну нормальну форму для формули А логіки висловлень, де
Навигация
Наслідок. Існує обчислювана функція h, для якої обидві проблеми «x Î Dom(h)» і «х Î Ran(h)» нерозв'язні
Алгоритмічні проблеми
54576
знаков
5
таблиц
0
изображений
1.2. Наслідок. Існує обчислювана функція h, для якої обидві проблеми «x Î Dom(h)» і «х Î Ran(h)» нерозв'язні.
Доведення. Покладемо
x, якщо xÎ Wx
h(x)=
не визначена, якщо xÏ Wx
Тоді в силу тези Черча і обчислюваності універсальної функції yu функція h обчислювана (більш формально ми маємо h(x)@ x1 (yu(х, х)), а ця функція обчислювана як результат підстановки). Ясно, що x Î Dom(h)Û xÎ Wx Ûx Î Ran (h), так що обидві проблеми «x Î Dom(h)» і «х Î Ran(h)» нерозв'язні.
З теореми 1.1 виводиться ще одна важлива нерозв'язна проблема:
1.3. Теорема (проблема зупинки). Проблема «функція фx(у) визначена» (чи в еквівалентній формі «Рx(y)¯, чи «y Î Wx» нерозв'язна.
Доведення. Міркуючи неформально, ми відразу бачимо, що якби проблема «функція фx(у) визначена» була б розв'язна, то була б розв'язна і більш проста проблема «функція фx(х) визначена», що суперечить теоремі 1.1.
Щоб провести всі ці міркування більш докладно, розглянемо характеристичну функцію проблеми^ «функція фх(у) визначена», що має наступний вид:
1, якщо фх(у) визначена
g (x, y)=
0, якщо фх(у) не визначена
Якби функція g була обчислювана, то обчислюваною була б і функція f(x)=g (x, х), але f є характеристична функція проблеми «х Î Wx» і, отже, не обчислювана в силу теореми 1.1. Отже, функція g не обчислювана, і тим самим проблема «фx(y) визначена» нерозв'язна. ÿ
Теорему 1.3 часто інтерпретують як твердження про нерозв'язність проблеми зупинки (для МНР-программ), у якому говориться про те, що не існує ніякого ефективного загального методу установити, чи зупиниться деяка конкретна програма, запущена після введення в неї деякого конкретного набору початкових даних. Зміст цього твердження для теоретичного програмування очевидний: не існує зовсім загального методу перевірки програм на наявність у них нескінченних циклів.
Розглянута в теоремі 1.1 нерозв'язна проблема «х Î Wx» важлива з кількох причин. Одна з них полягає в тому, що нерозв'язність багатьох проблем можна довести, показавши, що вони принаймні не простіші, ніж ця. Саме таким шляхом ми довели, що проблема зупинки (теорема 1.3) нерозв'язна: цей процес називається зведенням однієї проблеми до іншої.
Узагалі розглянемо деяку проблему М (х). Часто вдається показати, що рішення загальної проблеми М (х) привело б до рішення загальної проблеми «х Î Wx», Тоді говорять, що проблема «х Î Wx» зводиться до проблеми М (х). Іншими словами, якщо мається дозволяюча процедура для проблеми М (x), то ми можемо дати і дозволяючу процедуру для проблеми «х Î Wx». Таким чином, з можливості розв'язання М(х) випливає можливість розв'язання «х Î Wx», звідки ми негайно робимо висновок, що М (х) нерозв'язна.
Для зведення проблеми «х Î Wx» до інших проблем часто використовується s-m-n-теорема, як показує, наприклад, доведення наступного результату.
1.4. Теорема. Проблема «фx=0» нерозв'язна.
Доведення. Розглянемо функцію f, визначену формулою
0, якщо х Î Wx
f (x, y)=
не визначена, якщо x Ï Wx
Цю функцію ми ввели для того, щоб далі скористатися s-m-n-теоремою. Тим самим ми розглядаємо х як параметр, і нас цікавлять функції gx, такі, що gx(y)@ f (x, у). При цьому ми вибрали f так, що gx=0Ûх Î Wx.
Теза Черча (чи підстановка з використанням 0 і yu) показує, що функція f обчислювана. Тому існує тотальна обчислювана функція k(x), що дається s-m-n-теоремо., така, що f (x, у)@fk(x); тобто fk(x)=gx. Таким чином, по визначенню
(*) х Î WxÛ fk(x)= 0
Отже, питання про те, чи вірно, що х Î Wx, можна вирішити, відповівши спочатку на питання: чи вірно, що fk(x)=0? Тим самим ми звели загальну проблему «х Î Wx» до загальної проблеми «фx=0»; оскільки перша з них нерозв'язна, те нерозв'язна і друга, що і було потрібно довести.
У зв'язку з тим що це перший приклад подібного роду, що зустрівся нам, розглянемо останню частину нашого міркування більш докладно. Нехай g-характеристична функція проблеми «фx=0», тобто
1, якщо фx=0
g(x)=
0, якщо фx¹0
Припустимо, що функція g обчислювана. Тоді обчислюваною буде і функція h (х) = g (k (х)). У той же час співвідношення (*) дає
1, якщо фk(x)=0, тобто xÎ Wx,
h(x)=
0, якщо фk(x)¹0, тобто xÏ Wx.
Тим самим у силу теореми 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-теоремою для зведення проблеми «х Î Wx».
Похожие работы
... число эпох функционирования алгоритма, или определение его сходимости, обычно путем сравнивания приспособленности популяции на нескольких эпохах и остановки при стабилизации этого параметра. 3. Непрерывные генетические алгоритмы. Фиксированная длина хромосомы и кодирование строк двоичным алфавитом преобладали в теории генетических алгоритмов с момента начала ее развития, когда были получены ...
... в состояние qj, заменяя содержимое ячеек соответственно символами аb1 - аbк, то после этого ленты соответственно сдвигаются в направлениях k1... kk. До сих пор принималось, что различные алгоритмы осуществляются на различных машинах Тьюринга, отличающихся набором команд, внутренним и внешним алфавитами. Однако, можно построить универсальную машину Тьюринга, способную выполнять любой алгоритм ...
... M2(n) = O(l n), C2(n) = O(l n). Оскільки l = log2n, M2(n)=O(n log2 n)), C2(n)=O(n log2 n), Але З(n) = C1(n) + C2(n), M(n) = M1(n) + M2(n). Тому що C1(n) < C2(n), M1(n) < M2(n), остаточно одержуємо оцінки складності алгоритму TreeSort за часом: M(n) = O(n log2 n), C(n) = O(n log2 n), У загальному випадку, коли n не є ступенем 2, сортуюче дерево будується трохи інакше. “Зайвий” елемент ...
... U4 сравнения двух целых чисел оставляем читателю в качестве упражнения. Замечание: исходное слово надо задать в форме * Для нормальных алгоритмов Маркова справедлив тезис, аналогичный тезису Тьюринга. Тезис Маркова: Для любой интуитивно вычислимой функции существует алгоритм, ее вычисляющий. Построение алгоритмов из алгоритмов. До сих пор, строя ту или иную МТ, или НАМ мы каждый раз ...
0 комментариев