- •Введение
- •Тема 1. Логика высказываний
- •1.1. Понятие высказывания
- •1.2. Логические операции
- •1. Отрицание или инверсия ( – не)
- •4. Импликация () “если а, то b”
- •6. Сумма по модулю два
- •7. Штрих Шеффера ( , обратная конъюнкция и – не)
- •8. Стрелка Пирса (, обратная дизъюнкция или – не )
- •1.3. Булевы функции
- •1.3.1. Некоторые определения из теории множеств
- •1.3.2. Булевы функции
- •1.4. Формулы
- •1.5. Равносильные формулы
- •1.6. Подстановка и замена
- •1.7. Формы представления высказываний
- •1.8. Минимизация сложных высказываний методом Квайна
- •1.9. Полные системы функций
- •1.9.1. Система функций {}
- •1.9.2. Замкнутые классы
- •1.9.3. Функциональная полнота
- •Тема 2. Логические исчисления
- •2.1. Интерпретация формул
- •2.2. Примеры тождественно истинных формул высказываний
- •2.3. Формальные теории
- •2.5. Интерпретация формальных теорий
- •2.6. Исчисление высказываний.
- •2.7. Производные правила вывода
- •2.8. Дедукция
- •2.9. Некоторые теоремы теории £
- •Тема 3. Логика и исчисление предикатов
- •3.1. Предикаты
- •3.2. Исчисление предикатов
- •3.3. Интерпретация
- •3.4. Основные равносильности для предикатов
- •3.5. Приведенная форма представления предикатов
- •Тема 4. Автоматическое доказательство теорем
- •4.1. Постановка задачи
- •4.2. Доказательство от противного
- •4.3.Правило резолюции для исчисления высказываний
- •4.4. Правило резолюции для исчисления предикатов
- •4.5. Основные положения мр (выводы)
- •4.6. Логическое программирование
- •Тема 5. Теория алгоритмов
- •5.1. Интуитивное понятие алгоритма
- •5.2. Конкретизация понятия алгоритма
- •5.2.1. Машины Тьюринга
- •5.2.3. Рекурсивные функции
- •5.2.3. Нормальные алгорифмы Маркова
- •5.3. Алгоритмически неразрешимые проблемы
- •5.3.1. Проблема самоприменимости
- •5.3.1.1. Нумерация мт
- •5.3.1.2. Самоприменимость мт
- •5.3.2. Проблема останова
- •5.3.3. Разрешимые и неразрешимые задачи математики
- •5.4. Характеристики сложности вычислений
- •5.5. Классы сложности задач
- •5.5.1. Р задачи
- •5.5.2. NPзадачи
5.3.1.2. Самоприменимость мт
Рассмотрим машины Тьюринга, внешние алфавиты которых содержат символы 0,1 (наряду с другими). Для каждой машины Тьюринга Т построим Код(Т), который является (0,1)-словом, и запустим машину Т в начальной конфигурации q1Код(Т). Если машина Т останавливается (т.е. попадает в заключительное состояние) через конечное число шагов, то она называется самоприменимой, в противном случае – несамоприменимой. Существуют как самоприменимые, так и несамоприменимые машины Тьюринга. Например, несамоприменимой будет машина Т1, у которой все команды имеют вид qiaj→qiajС (в правых частях команд нет заключительного состояния), самоприменимой будет машина Т1, у которой все команды имеют вид qiaj→q0ajE (в правых частях всех команд имеется заключительное состояние). Проблема самоприменимости состоит в том, чтобы по любой машине Тьюринга Т определить, является ли она самоприменимой или нет. Будем считать, что машина Тьюринга М решает проблему самоприменимости, если для любой машины Т начальную конфигурацию q1Код(Т) она переводит в q01,
если машина Т самоприменима, и в q00, если машина Т несамоприменима.
Теорема 1.Не существует машины Тьюринга М, решающей проблему самоприменимости, т.е. проблема самоприменимости алгоритмически неразрешима.
Доказательство (от противного).
Предположим противное, т.е. пусть существует машина Тьюринга М, решающая проблему самоприместимости в указанном выше смысле. Построим новую машину М0, добавив новое состояние q0* и объявив его заключительным, а также добавив новые команды для состояния q0, которое было заключительным в М:
q01→q01С (1)
q00→q0* 0С (2).
Рассмотрим теперь работу машины М0.
Пусть Т – произвольная машина. Если Т – самоприменима, то начальная конфигурация q1Код(Т) перейдет с помощью команд машины М через конечное число шагов в конфигурацию q01, далее применяется команда (1), и машина М0никогда не остановится. Если Т – несамоприменима, то начальная конфигурация q1Код(Т) перейдет с помощью команд машины М через конечное число шагов в конфигурацию q00, далее применяется команда (2), и машина М0 остановится.
Таким образом, машина М0применима к кодам самоприменимых машин Т и неприменима к кодам самоприменимых машин Т.
Теперь рассмотрим Код(М0) и применим машину М0к начальной конфигурации q1Код(М0). Сама машина М0 является либо самоприменимой, либо несамоприменимой. Если М0самоприменима, то по доказанному она никогда не остановится, начав с q1Код(М0), и потому она несамоприменима. Если М0 несамоприменима, то по доказанному, она останавливается через конечное число шагов, начав с q1Код(М0), и потому она самоприменима. Получили противоречие, которое является следствием допущения существования машины М0, решающей проблему самоприменимости, что и требовалось доказать.
5.3.2. Проблема останова
Проблема останова заключается в том, чтобы по любой машине Тьюринга Т и слову Р в ее внешнем алфавите узнать, применима ли Т к начальной конфигурации q1Р. Проблема останова алгоритмически неразрешима, т.к. если бы она была разрешимой, то, взяв в качестве Р слово Код(Т), мы получили бы разрешимость проблемы самоприменимости.