Разрешимость алгоритмических проблем.

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

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

Естественно возникает вопрос: Всякая ли алгоритмическая проблема разрешима? Вплоть до начала ХХ века среди математиков существовала уверенность в разрешимости любой математической проблемы. Как уже отмечалось во введении, Лейбниц был один из первых, кто пришёл к идее исчисления. Он считал, что решение математической проблемы сводится к манипуляции с символами с помощью специальным образом подобранными правилами вывода (замены одних комбинаций символов на другие). Проблема, по мнению Лейбница, состояла лишь в том, чтобы построить надлежащим образом систему этих правил. Более того - он считал, что можно построить универсальный набор правил для решения любой математической проблемы. Джонатан Свифт в своей книге “Приключения Гулливера” подшутил над этой идеей Лейбница в образе мудреца, вращающего колёса с табличками в поисках нужного решения.

Английский математик Чёрч первым дал пример неразрешимой поблемы, известной как проблема выводимости.

Проблема выводимости:

Дана система правил подстановки R и два слова W и S. Можно ли определить выводимо W из S с помощью R?

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

Другой известный нам пример неразрешимой алгоритмической проблемы - 10-я проблема Гильберта.

Определение 4.2. Алгоритм А называется самоприменимым, если он применим к слову, которое является его описанием.

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

Дано описание алгоритма А. Требуется построить такой алгоритм, который бы для описания любого алгоритма А определял, является ли алгоритм А самоприменимым или нет.

Теорема 4.1. Распознавание самоприменимости алгоритмически неразрешимо.

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

 

А(А)=		s - если А - самоприменим   t - если А - не самоприменим, где А - некоторый алгоритм

Построим, имея А, алгоритм В, который

 

В(А)=

не останавливается, если А самоприменим   t - если А - не самоприменим

Таким образом, В применим к самонеприменимым алгоритмам и не применим к самоприменимым.

Рассмотрим В(В), т. е. Применение В к самому себе. Если В(В) даёт t, следовательно, В - самоприменим, но по построению В даёт t только на не самоприменимых авлгоритмах. Если В(В) не останавливается, то это означает, что В - не самоприменим, но по построению в этом случае он должен дать t. Пришли к противоречию. Следовательно, такой алгоритм В не существует. Следовательно, не может существовать и алгоритм А. Отсюда - предположение о существовании алгоритма А, распознающего самоприменимость, неверно!

Доказательство закончено.

Замечание: обычно доказательство неразрешимости алгоритмической проблемы строится методом сведения. Идея этого метода состоит в том, что для исследуемой проблемы П доказывается, что она сводится к другой проблеме П^¢, о которой известно, что она неразрешима.

 

Взаимосвязь алгоритмических систем.

В связи с существованием неразрешимых алгоритмических проблем возникает вопрос:

А не может ли оказаться так, что алгоритмическая проблема, неразрешимая в одной алгоритмической системе, окажется разрешимой в другой? Например, какая-то проблема, не разрешимая в терминах машины Тьюринга, окажется разрешимой в терминах НАМ.

 

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

 

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

В этом разделе на примере МТ и НАМ мы покажем, что для эквивалентных алгоритмических систем, не может оказаться так, что какая-то алгоритмическая проблема, неразрешимая в МТ, окажется разрешимой в НАМ. Мы докажем, что для любой МТ U можно подобрать НАМ N такой, что

U(P)=N(P) и наоборот.

Отсюда и будет следовать, что если какая-то алгоритмическая проблема разрешима в МТ, то она автоматически разрешима в НАМ и наоборот.

 

Теорема 4.2 Для любой машины Тьюринга U существует НАМ N такой, что

U(P)=N(P), где Р Є D_U^*.

Доказательство: Для доказательства этой теоремы мы покажем, как для каждого правила ap®bqw машины U построить правило подстановки для НАМ N. Тем самым мы, зная функциональную схему U, построим систему правил для N.

В функциональной схеме машины U могут встретиться команды следующих видов:

aq_j ® bq_sЛ

aq_j ® bq_sП

aq_j ® bq_sН

aq_j ® b!{Л,П,Н}.

Рассмотрим сначала команды машины U вида (1), т. е. запись в текущую позицию вместо символа a символа b и сдвиг влево. В соответствующем НАМ N мы будем обрабатываемый символ в слове р метить слева символом состояния т. е. D_N=D_UUQ_UU{Ñ}. Тогда команде (1) сопоставим следующую группу правил подстановки:

q_ja ® q_sÑb

{c_iq_sÑ ® q_sc_i}, c_i ЄD_U

 

Здесь символ Ñ “экранирует” q от следующего за ним символа в обрабатываемом слове.

Командам вида (2) сопоставим правила подстановки вида

q_ja®bq_s

Командам вида (3) - q_ja ® q_sb

Командам вида (4) - q_ja a b.

 

Самым последним в системе правил подстановки НАМ будет начальное правило

® q_o, машины U.

где q_o - начальное состояние U.

Замечание: Если а=L, т. е. командам Lq_j ® bq_sw надо будет сопоставлять правило q_j ® q_sb либо q_j ® bq_s в зависимости от значения w. Все такие правила подстановки надо собрать в конце схемы, сразу перед начальным правилом.

Обратите внимание, что если на вход N подать слово, к которому U не применим, то N будет бесконечно долго подставлять q_o в начало слова.

N применим к тем же словам, что и U.

Допустим существование слова Р, к которому U применим, а N - нет. Раз U применим, то пусть его заключительной командой является команда aq ® b!H. Ей по построению N соответствует терминальное правило подстановки, которое должно выполняться, т. к. в схеме N нет двух правил с одинаковыми правыми частями..

Пришли к противоречию.

Доказательство теоремы 4.2 закончено.

 

Теорема 4.3. Для любого НАМ N существует машина Тьюринга U такая, что

N(P)= U(P) для всех PЄD_N^*.

Доказательство:

Алфавит U: D_U = D_NUW_N.

Обозначим

U*(Р)=*Р, т. е. МТ, ставящую символ * перед обрабатываемым символом.

U_!(P)=P осталось без изменения слова.

 

1 || Q*aR если QaR=P   0 || P* если a не входит в P

_b (1||Q*aR)=QbR

U₀ (0||P*)=P

 

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

Схема НАМ N состоит из правил либо вида a®b, либо aab, где
a,b Є (DUW)^*.

Каждому правилу вида

a_i®b_i

сопоставим машину U_i c функциональной схемой вида

 

if then _bi(1||Q*a_iR)o U^*o U₁

else U_оo U*o U_i+1 .

Каждому терминальному правилу вида

a_iab_i

сопоставим машину U_i c функциональной схемой вида

if then _bi(1||Q*a_iR) o U_!

else U_оo U*o U_i+1 .

Последнему правилу подстановки в схеме НАМ N вида

a_k®b_k

сопоставим машину U_k с функциональной схемой

if then _bk(1||Q*a_kR)o U*o U₁

else U_оo U*o U_! .

В части else появление машины U_! связано с тем, что по определению НАМ завершается, если не применимо ни одно из правил подстановки.

Функциональная схема искомой машины U будет иметь вид

U*(P)o U₁o U₂o … o U_k,

где k - число правил подстановки в схеме НАМ N.

Доказательство теоремы 4.3 закончено.

Из теорем 4.2 и 4.3 следует, что если какая-то алгоритмическая проблема разрешима в одной алгоритмической системе, то она автоматически разрешима и в другой. Если предположить, что какая-то алгоритмическая проблема неразрешимая в одной алгоритмической системе, но разрешима в другой, то придём к противоречию. Действительно, согласно теоремам 4.2 и 4.3 если эта проблема разрешима хотя бы в одной системе, то она разрешима и в другой.

 

 

Выводы:

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

В силу тезиса Тьюринга, любой алгоритм реализуем в терминах действий последовательной, параллельной композиций, выбора и цикла и базового набора действий;

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

Если алгоритмическая проблема не разрешима, то она не разрешима в любой другой эквивалентной алгоритмической системы;

Алгоритмические системы МТ и НАМ эквивалентны.

 

Вопросы:

Что такое интерпретация?

Что такое кодирование?

В чем проблема линеаризации Ф.с. для МТ?

Что такое универсальный исполнитель:
- он может исполнять заданный А в любой А.с.?
- он может исполнять любой А, выразимый в данной А.с.?

Как решается проблема произвольности алфавита в УМТ?

Что такое А.п.?

Самоприменимость - что это такое?

А.п. самоприменимости разрешима?

В МТ А не закончен если нет применимого правила, в НАМ в этом случае А - закончен. Как это несоответствие решается при доказательстве сводимости МТ к НАМ и наоборот?

Что означает запись:

Если F_a (*P), то M(1||Q*aR)o U^*o U₁ иначе U₀o U^*o U_i+1?

Список литературы

Для подготовки данной работы были использованы материалы с сайта https://www.ergeal.ru/