Реферат: Существование универсальных вычислителей. Алгоритмические проблемы и взаимосвязь алгоритмических систем.

Дана система правил подстановки 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 ^* .