Войти на сайт

или
Регистрация

Навигация


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

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

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

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


y, якщо х Î Wx

f (x, y)=

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

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

x Î WxÞWk(x)=Ek(x)=N

так що c Î Wk(x) і c Î Ek(x)

x Ï WxÞWk(x)=Ek(x)

так що c Ï Wk(x) і c Ï Ek(x). Тим самим ми звели проблему «x Î Wx» до кожної з проблем «c Î Wx » і «c Î Ex «.

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

1, якщо x Î Wx,

g (k(x))=

0, якщо x Ï Wx

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

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

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

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

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

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

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

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

f (x, y)@

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

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

x Î Wx Þ фk(x) =g, тобто фk(x) Î B

x Ï Wx Þ фk(x) =fÆ, тобто фk(x) Ï B

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

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

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

1.8. Вправи.

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

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

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

(b) «Wx=Wy «. (Указівка. Зведіть до цієї проблеми проблему «функція фx тотальна».)

(c) «фx(х)=0».

(d) «фx(y)=0».

(e) «х Î Еу «.

(f) «функція фx тотальна і постійна».

(g) «Wx=Æ».

(h) «множина Еx нескінченна».

(i) «фх=g», де g є будь-яка фіксована обчислювана функція.

2. Покажіть, що не існує тотальної обчислюваної функції f (x, у), що володіє наступними властивістями: якщо програма Рх(у) зупиняється, те це відбувається за f (x, у) чи менше кроків (Указівка. Покажіть, що якби така функція існувала, те проблема зупинки була б розв'язна.)

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

Виявленню розв'язних і нерозв'язних проблем у самих різних математичних ситуаціях присвячено багато досліджень.

6. Дані і знання. Логіка висловлень (ЛВ) в представленні знань
Информация о работе «Алгоритмічні проблеми»
Раздел: Математика
Количество знаков с пробелами: 54576
Количество таблиц: 5
Количество изображений: 0

Похожие работы

Скачать
33080
5
4

... число эпох функционирования алгоритма, или определение его сходимости, обычно путем сравнивания приспособленности популяции на нескольких эпохах и остановки при стабилизации этого параметра. 3. Непрерывные генетические алгоритмы. Фиксированная длина хромосомы и кодирование строк двоичным алфавитом преобладали в теории генетических алгоритмов с момента начала ее развития, когда были получены ...

Скачать
18213
1
5

... в состояние qj, заменяя содержимое ячеек соответственно символами аb1 - аbк, то после этого ленты соответственно сдвигаются в направлениях k1... kk. До сих пор принималось, что различные алгоритмы осуществляются на различных машинах Тьюринга, отличающихся набором команд, внутренним и внешним алфавитами. Однако, можно построить универсальную машину Тьюринга, способную выполнять любой алгоритм ...

Скачать
26020
3
4

... 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, сортуюче дерево будується трохи інакше. “Зайвий” елемент ...

Скачать
10075
2
1

... U4 сравнения двух целых чисел оставляем читателю в качестве упражнения. Замечание: исходное слово надо задать в форме  * Для нормальных алгоритмов Маркова справедлив тезис, аналогичный тезису Тьюринга. Тезис Маркова: Для любой интуитивно вычислимой функции существует алгоритм, ее вычисляющий. Построение алгоритмов из алгоритмов. До сих пор, строя ту или иную МТ, или НАМ мы каждый раз ...

0 комментариев


Наверх