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

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

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

1) - индивидуальная проблема

для – это массовая проблема

2) Для функции :

индивидуальная проблема

массовая проблема

Будем рассматривать алгоритмические проблемы, которые дают ответ «Да» или «Нет». Такие задачи называют задачами распознавания.

С каждой задачей распознавания может быть связана характеристическая функция.

, где - набор параметров из П – массовая проблема

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

 

Способы доказательства алгоритмической неразрешимости

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

Пусть есть некоторая машина Тьюринга: Т

Применима ли машина к конфигурации Код(Т)

Пример самоприменимой МТ:

Пример не самоприменимой МТ:

 

Проблема заключается в определении для любой машины по её коду является ли она самоприменимой или нет.

Докажем что не существует МТ способной это определить.

Доказательство: будем доказывать от противного. Пусть существует машина Тьюринга М которая решает проблему самоприменимости.

Сконструируем машины которая будет включать в себя все команды машины М + ещё две новых команды:

, где - новое заключительное состояние

Т.е. машина будет применима к не самоприменимым и никогда не остановится если машина Т будет самоприменимой.

Является ли машина самоприменимой?

Пусть самоприменима, тогда:

получили противоречие

Тогда предполагая, что машина не самоприменима

Из этого следует что машины существовать не может начальное предположение о существовании машины М решаемой проблему самоприменимости ложно не существует машин решаемых проблему самоприменимости.

 

2.Сводимость проблем

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

Тогда говорят, что задача(проблема)

Тогда справедлива следующая теорема:

Если задача сводится к задаче и задача алгоритмически неразрешима, то и задача также алгоритмически неразрешима.

Доказательство: Пусть задача не разрешима, а задача - разрешима, тогда для справедливо:

– вычислима

И по определению сводимости имеем для задачи :

- снова вычислима

Таким образом получили противоречие. Следовательно, алгоритмически не разрешима.

 

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

Есть произвольная машина Т и произвольное слово Р

Остановится ли машина с начальной конфигурацией

Проблема самоприменимости сводится к проблеме останова т.к. выбрав в качестве слова Р=Код(Т) получим проблему самоприменимости. Т.к. проблема самоприменимости является не разрешимой, то и проблема оснатова также является алгоритмичести не разрешимой.

11.3 Проблема «x Î W_x»

 

· Определить для произвольного числа X принадлежит ли оно области определения ЧРФ стоящей под номером X.

Доказательство: Рассмотрим характеристическую функцию

И функцию следующего вида:

- вычислима если – не вычислима

Пусть g(x) вычислима, тогда она стоит в ряде ЧРФ под некоторым номером n т.е.

Определена ли функция g(x) в точке n?

Пусть g(n) определена, это значит что:

Т.е. получили противоречие.

Если предположить, что g(n) не определена тогда:

т.е. g(n) определена Снова получили противоречие.

Следовательно исходная посылка, что g(n) вычислима не верна и функция g(n) не вычислима, а это значит, что функция f(x) также не вычислима.

 

· Рассмотрим две функции отвечающие двум проблемам:

- отвечает проблеме

- отвечает проблеме

Обе эти функции не вычислимы. Рассмотрим функции вида:

- также является не вычислимой

 

- данная функция уже является вычислимой

В этом случае считается, что функция g(x) является более невычислимой, чем f(x), а проблема является полувычислимой проблемой.