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

Массовая проблема – бесконечный класс однотипных (индивидуальных) проблем.

Пример.

Индивидуальная проблема: Обладает ли заданным свойством Q конкретная частично-рекурсивная функция (ЧРФ).

Совокупность всех таких задач (для всех ЧРФ) образует массовую проблему распознавания свойства Q.

Будем рассматривать только задачи, дя которых имеет смысл ответ ДА или НЕТ.

Введем обозначения: п – индивидуальная проблема, П – массовая проблема, ,

f(п) – характеристическая функция.

Массовая проблема является алгоритмически разрешимой, если f(п) является вычислимой, т. е. существуют такие алгоритмы, с помощью которых можно решить любую индивидуальную проблему.

Решая конкретную массовую проблему, следует считаться с возможностью того , что она может оказаться алгоритмически неразрешимой, поэтому необходимо иметь представление о технике доказательства неразрешимости.

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

Пусть существуют две массовые проблемы П1 и П2. Пусть существует алгоритм А, который по всякой индивидуальной задаче строит индивидуальную задачу , такую, что выполняется:

имеет ответ «ДА» тогда и только тогда, когда имеет ответ «ДА». В этом случае говорят, что проблема П1 сводится к проблеме П2.

• Если проблема П1 неразрешима, то проблема П2 также неразрешима.

Доказательство (от противного).

Пусть проблема П2 разрешима. Тогда можно построить разрешающий алгоритм для проблемы П1. Берем произвольную индивидуальную задачу . Имея алгоритм А, строим индивидуальную задачу , . Применяем к задаче п2 существующий по предположению разрешающий алгоритм для проблемы П2. Если задача п2 имеет ответ «ДА», то для задачи п1ответ должен быть «НЕТ». Т. к. по

условию, проблема П1 неразрешима, то получим противоречие. Значит, проблема П2 неразрешима. Данное рассуждение называется методом сводимости, и его применение возможно, если уже имеется запас проблем, алгоритмическая неразрешимость которых

уже установлена.

Рассмотрим некоторые из таких проблем.

Проблема самоприменимости

Нумерация МТ

A={a0,..,ai,…} – внешний алфавит МТ (счетное множество).

Q={q0, q1, …, qj,…} – внутренние состояния МТ (счетное множество).

Пусть для всех МТ a0 – пустой символ, q0 – заключительное состояние, q1 – начальное состояние.

Каждому символу из множества {Л, П, С, a0, a1,…, ai,…, q0, q1, …qj… } поставим в соответствие двоичное число:

	Символ	Код	Число нулей в коде
Д	Л
П
С
А	а0
а1
…
ai	10………0	2i+4
….
Q	q0
q1
….
qj	10………0	2j+5
…

Команде МТ поставим в соответствие двоичное число:

.

Упорядочим команды МТ в соответствии с лексикографическим порядком левых частей команд q1a0, q1a1,…q2a0,…. и т. д. Получим последовательность команд I1,…In(m+1), где n – число символов в алфавите А, m – число состояний в множестве Q.

Тогда МТ можно поставить в соответствие двоичное число вида:

Код(Т)=Код(I1)Код(I2) …..Код(In(m+1)).

Пример.

A={a0,a1}

Q={q0,q1}

I1:q1a0→q0a0C

I2:q1a1→q0a1C

Тогда Код(Т)=

Такое кодирование является алгоритмической процедурой. Зная код МТ можно однозначно восстановить множество ее команд. Код МТ можно рассматривать как двоичную запись натурального числа. Такое число называется номером МТ.

Самоприменимость МТ

Рассмотрим машины Тьюринга, внешние алфавиты которых содержат символы 0,1 (наряду с другими). Для каждой машины Тьюринга Т построим Код(Т), который является (0,1)-словом, и запустим машину Т в начальной конфигурации q₁Код(Т). Если машина Т останавливается (т.е. попадает в заключительное состояние) через конечное число шагов, то она называется самоприменимой, в противном случае – несамоприменимой. Существуют как самоприменимые, так и несамоприменимые машины Тьюринга. Например, несамоприменимой будет машина Т1, у которой все команды имеют вид q_ia_j→q_ia_jС (в правых частях команд нет заключительного состояния), самоприменимой будет машина Т1, у которой все команды имеют вид q_ia_j→q₀a_jE (в правых частях всех команд имеется заключительное состояние). Проблема самоприменимости состоит в том, чтобы по любой машине Тьюринга Т определить, является ли она самоприменимой или нет. Будем считать, что машина Тьюринга М решает проблему самоприменимости, если для любой машины Т начальную конфигурацию q₁Код(Т) она переводит в q₀1,

если машина Т самоприменима, и в q₀0, если машина Т несамоприменима.

Теорема 1. Не существует машины Тьюринга М, решающей проблему самоприменимости, т.е. проблема самоприменимости алгоритмически неразрешима.

Доказательство (от противного).

Предположим противное, т.е. пусть существует машина Тьюринга М, решающая проблему самоприместимости в указанном выше смысле. Построим новую машину М₀, добавив новое состояние q₀* и объявив его заключительным, а также добавив новые команды для состояния q₀, которое было заключительным в М:

q₀1→q₀1С (1)

q₀0→q₀* 0С (2).

Рассмотрим теперь работу машины М₀.

Пусть Т – произвольная машина. Если Т – самоприменима, то начальная конфигурация q₁Код(Т) перейдет с помощью команд машины М через конечное число шагов в конфигурацию q₀1, далее применяется команда (1), и машина М₀ никогда не остановится. Если Т – несамоприменима, то начальная конфигурация q₁Код(Т) перейдет с помощью команд машины М через конечное число шагов в конфигурацию q₀0, далее применяется команда (2), и машина М₀ остановится.

Таким образом, машина М₀ применима к кодам самоприменимых машин Т и неприменима к кодам самоприменимых машин Т.

Теперь рассмотрим Код(М₀) и применим машину М₀ к начальной конфигурации q₁Код(М₀). Сама машина М₀ является либо самоприменимой, либо несамоприменимой. Если М₀ самоприменима, то по доказанному она никогда не остановится, начав с q₁Код(М₀), и потому она несамоприменима. Если М₀ несамоприменима, то по доказанному, она останавливается через конечное число шагов, начав с q₁Код(М₀), и потому она самоприменима. Получили противоречие, которое является следствием допущения существования машины М₀, решающей проблему самоприменимости, что и требовалось доказать.

Проблема останова

Проблема останова заключается в том, чтобы по любой машине Тьюринга Т и слову Р в ее внешнем алфавите узнать, применима ли Т к начальной конфигурации q₁Р. Проблема останова алгоритмически неразрешима, т.к. если бы она была разрешимой, то, взяв в качестве Р слово Код(Т), мы получили бы разрешимость проблемы самоприменимости.