5.4. Алгоритмически неразрешимые проблемы.

Тьюрингом был выдвинут тезис: каждый алгоритм может быть реализован с помощью машины Тьюринга. Это даёт точное определение алгоритма, которое может быть использовано для доказательства алгоритмической неразрешимости ряда проблем.

Как ранее указывалось, при соответствующей кодировке задачи можно считать функциями, определёнными на неотрицательных целых числах и принимающими такие же значения. Приняв тезис Тьюринга, получаем, что алгоритмически разрешимым задачам соответствуют вычислимые на МТ функции.

Существование алгоритмически неразрешимых проблем можно усмотреть уже из мощностных соображений, так различных МТ – счетное число, а функций - значительно больше. В самом деле, имеется конечное число МТ с m + 1 внутренними состояниями и внешним алфавитом из заданных n + 1 символов, а именно, не более [3(m+1)(n+1)]^(m+1)(n+1) поэтому всех МТ – счётное число. В то же время даже функций вида f: N → {0,1} имеется более чем счётное число, так как каждую такую функцию можно рассматривать как характеристическую функцию некоторого подмножества натуральных чисел, а множество подмножеств всегда имеет мощность, большую мощности самого множества.

На языке МТ можно указать и содержательные неразрешимые проблемы. Рассмотрим алгоритмическую проблему самоприменимости, состоящую в следующем. Так как всех МТ – счётное число, то множество МТ можно закодировать, присвоив каждой МТ в качестве идентифицирующего кода натуральное число n (m). При этом всё множество МТ разобьётся на 2 класса: МТ, применяемых к собственному номеру, т.е. к слову 1^n(m), и неприменимых. Назовём МТ первого класса самоприменимыми, а второго – несамоприменимыми.

Некоторая МТ решает проблему самоприменимости, если по коду произвольной машины она определяет, самоприменима она или нет. Докажем, что такой МТ не существует. Допустим противное. Пусть такая МТ имеется и на коде самоприменимой машины она завершает работу в конфигурации ...q₀ 1... , а на коде несамоприменимой - ...q₀ 0... . Тогда, сделав незначительные изменения в программе, легко добиться того, чтобы МТ останавливалась на кодах несамоприменимых машин и не останавливалась на кодах самоприменимых машин.

Для этого считаем, что состояние q₀ не заключительное состояние, а в качестве в качестве заключительного введем новое состояние и добавим в программу МТ две новые команды:

Зададимся теперь вопросом, применима ли эта МТ к своему собственному коду. Если применима, то она применима к коду самоприменимой машины, а это невозможно. Полученное противоречие и является доказательством алгоритмической неразрешимости проблемы самоприменимости.

Теперь можно рассмотреть и более содержательную проблему применимости данной МТ к заданному слову Р. Допустим, что существует МТ, которая по коду n(M) и слову Р решает, применима ли данная машина к слову Р. Тогда, если в качестве слова Р взять код машины n(M), то наша МТ будет решать проблему самоприменимости, а это невозможно. Поэтому проблема алгоритмически неразрешима.

Контрольные вопросы.

1. Дайте определение понятия «алгоритм».

2. Опишите суть алгоритма Евклида для нахождения наибольшего общего делителя двух многочленов.

3. Что будет, если с помощью алгоритма Евклида находить общую меру стороны и диагонали квадрата?

4. Опишите суть модели алгоритма, называемой машиной Тьюринга.

5. Что называется конфигурацией?

6. Что значит, что машина Тьюринга применима к данному слову?

7. Какие алгоритмически неразрешимые проблемы вы знаете?

Тест V

1) Для нахождения (48,27) алгоритма Евклида выполнит

а) 2 шага; б) 3 шага; в) 4 шага.

2) Наибольший общий делитель многочленов x²-3x+2 и x²-4x+3 равен

а) x+1; б) x-1; в) x²-1.

3) Применима ли к слову 1¹⁰⁰ машина Тьюринга, задаваемая программой

q₁1 → q₁0R

q₁0 → q₂1L

q₂1 → q₀1C

q₂0 → q₁0R

а) применима; б) не применима.

4) Корнями уравнения являются числа

а) б)в)г)

5) Среди трех монет одна фальшивая. В результате какого наименьшего числа взвешиваний можно определить фальшивую монету

а) одного; б) двух; в) трех.

Задачи для самостоятельного решения.

1). Доказать с помощью законов алгебры множеств следующие тождества:

а)

б)

в) .

2) Доказать, что из иследует =

3) Доказать следующие соотношения для мощностей конечных множеств:

а)

б)

4) Доказать счётность множества рациональных чисел, указав способ их перечисления.

5). Установить взаимно однозначное соответствие между заданными множествами, указав соответствующую биекцию:

а) [0;1] и [0;2];

б) (-1;1) и (-∞; ∞).

6). Отношение R на множестве Z определяется следующим образом:

делится на 3.

Показать что R есть отношение эквивалентности, найти число классов эквивалентности и описать их.

7). На системе множеств {a},{a,b},{b,c},{a,c},{a,b,c} с частичным порядком по включению указать минимальные, максимальные, наименьший и наибольший элементы.

8).Показать, что отношение “х делит y” является отношением частичного порядка на множестве N.

9). Построить таблицу умножения в кольце классов вылетов:

а) по модулю 5;

б) по модулю 6.

В чём принципиальное различие колец а) и б) ?

10). Булева функция от трёх переменных задана таблицей:

x1 x2 x3	F(x1 x2 x3)
0 0 0	1
0 0 1	0
0 1 0	1
0 1 1	1
1 0 0	1
1 0 1	1
1 1 0	0
1 1 1	1

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

11).Построить таблицу истинности для высказывания:

а) (P  (Q  R))  ((P  Q)  (P  R));

б) (P  (Q  )) (( P)  Q) .

12).Число А называется пределом функции y = f (x) при x  a, если для любого сколь угодно малого ε  0 существует δ  0 такое, что при выполнении неравенства  δ выполняется неравенство

ε.

Запишите это определение на языке предикатов и кванторов.

13). Проверить правильность следующего рассуждения. Если Джонс не встречал этой ночью Смита, то либо Смит был убийцей, либо Джонс лжёт.

Если Смит не был убийцей, то Джонс не встречал Смита этой ночью, и убийство имело место после полуночи. Если убийство было совершено после полуночи, то либо Смит был убийцей, либо Джонс лжёт. Следовательно, Смит был убийцей.

14). «Вернувшись домой, Мегрэ позвонил на набережную Орфевр.

- Говорит Мегрэ. Есть новости ?

- Да, шеф. Поступили сообщения от инспекторов. Торранс установил, что если Франсуа был пьян, то либо Этьен убийца, либо Франсуа лжёт. Жуссье считает, что или Этьен убийца, или Франсуа не был пьян и убийство произошло после полуночи. Инспектор Люка просил передать Валг, что если убийство произошло после полуночи, то либо Этьен убийца, либо Франсуа лжет.

- Немедленно задержите Этьена.»

Логически обоснуйте действия комиссара Мегрэ, принимая во внимание наряду с полученной от инспекторов информацией также известный Мегрэ факт, что трезвый Франсуа никогда не лжет.

15). Среди n монет имеется одна фальшивая вес которой меньше. Результатом взвешивания является определение, что на одной из чашек весов находится больший или меньший вес, или веса одинаковы. Указать алгоритм, гарантирующий нахождения фальшивой монеты за не более ]log₃ n[ взвешиваний.

16). Выяснить, применима ли машина Тьюринга, задаваемая программой

q₁ 1 q₂ 1 R

q₁ 1 q₁ 0 R

q₂ 0 q₃ 1 R

q₂ 1 q₃ 0 L

q₃ 0 q₁ 0 R

q₃ 1 q₀ 1 C,

к слову Р.

а) Р=10³1

б) Р=[10]²1.

17). Построить в алфавите {0,1} машину Тьюринга, которая применима к словам вида и, но не применима к словам вида 1^2m01^2n-1 и 1^2n-101^2m . К словам иного вида машина может быть как применима, так и не применима.