Предыдущая страница реферата | 1  2  3  4  5  6  7  8 | Следующая страница реферата

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

 aqj ® bqsЛ

 aqj ® bqsП

 aqj ® bqsН

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

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

qja ® qsÑb

{ciqsÑ ® qsci} ,  ci ЄDU

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

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

qja®bqs

Рекомендуем скачать другие рефераты по теме: сочинения по русскому языку, контрольные работы по алгебре.





Предыдущая страница реферата | 1  2  3  4  5  6  7  8 | Следующая страница реферата