13508-1 (Существование универсальных вычислителей. Алгоритмические проблемы и взаимосвязь алгоритмических систем.)

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

Существование универсальных вычислителей.

Теперь задумаемся вот о чём. Каждый раз, когда мы строили программу для новой Машины Тьюринга, даже если мы при этом использовали программы для других машин, не явно предполагалось, что как-то, где-то, кем-то строилась каретка, обладающая заданным набором состояний, способная распознавать и записывать символы из заданного алфавита и т.п. Построение такой каретки - сама по себе задача не из простых. Для каждого нового алгоритма мы вынуждены строить новый исполнитель. Это выглядит примерно так, как если бы для каждой новой программы нам надо было строить новый компьютер.

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

Итак, пусть нам надо построить Универсальную Машину Тьюринга, назовём её УМТ, для которой:

исходными данными являются программа другой машины, назовём её МТ, с исходными данными Д последней;

результат применения УМТ к этим исходным данным должен быть таким же, как применение МТ к её исходным данным, то есть

УМТ(МТ,Д)=МТ(Д).

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

Представим себя в качестве такой УМТ и опишем в интуитивной форме алгоритм своей работы. Состояние воображаемой каретки будем записывать под обозреваемой ячейкой ленты. Программу имитируемой МТ считаем пока заданной в виде таблицы.

Интерпретирующий алгоритм для УМТ:

Обозревай ячейку, под которой написана буква (состояние);

Отыщи в таблице строку, обозначенную этой буквой;

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

Замени букву в обозреваемой ячейке на первую букву тройки;

Если второй буквой тройки является “!”, то стоп;

Если в обозреваемой ячейке третья буква “Н”, то сотри букву под обозреваемой ячейкой и запиши туда вторую букву тройки (смена состояния);

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

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

Перейди к шагу 1.

Для того, чтобы преобразовать это описание в программу Машины Тьюринга, надо решить две основные проблемы:

Как задавать программу и конфигурацию имитируемой МТ на ленте?

Так как произвольная МТ может иметь произвольный алфавит, то какой алфавит должен быть у УМТ?

Первая проблема разбивается на две:

как задать программу на ленте?

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

Программу МТ будем записывать пятерками

qp , где ,D; p,qQ; {Л, П, Н},

здесь - символ , соответствующий строке таблицы;

q - столбцу таблицы.

На рисунке 4.1. показана линейная запись функциональной схемы для U₁(n).

Рис. 4.1. Линейная запись функциональной схемы МТ, вычисляющей U₁(n).

Такое представление программы обеспечивает взаимнооднозначное соответствие с табличной формой записи, а стало быть ничего из таблицы при этом не теряется и ничего не добавляется.

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

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

Теперь рассмотрим проблему алфавита. Напомним, эта проблема состоит в том, что УМТ должна иметь определенный алфавит, который не может изменяться. В то же время мы не можем знать заранее, с какими алфавитами будут работать МТ, которые будет интерпретировать наша УМТ. Решение этой проблемы - кодирование символов из алфавита МТ символами алфавита УМТ. При этом важно позаботиться о том, чтобы:

один и тот же символ из алфавита МТ всегда изображался одной и той же последовательностью символов из алфавита УМТ;

разные символы из алфавита МТ всегда изображались разными последовательностями символов из алфавита УМТ.

В качестве алфавита УМТ выберем алфавит {0,1}, расширенный небольшим количеством вспомогательных символов. Пусть нам надо закодировать символы МТ, у которой |D_МТ|=k; |Q_МТ|=m.

Возьмем 3+k+m слов вида 1000……01, т.е. последовательность нулей между единицами. Эти слова мы будем называть кодовыми группами (КП). На рисунке 4.2 показаны кодовые КП для символов из D, Q, и {Л, Н, П}

Рис. 4.2 Кодовые КП для символов из D, Q, и {Л, Н, П}

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

Обозревай в шифре конфигурации КП, расположенную левее КП, с нечётным числом нулей, т.е. код текущего состояния каретки (заметим, что такая КП в шифре конфигурации всегда одна. Убедитесь в этом).

Шаги 2 и 3 примут следующий вид:

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

Для каждого шага интерпретирующего алгоритма надо построить МТ с алфавитом {0,1}, после чего объединить их должным образом, с помощью операций , ||, if-then-else, while-do.

Обоснование закончено.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Доказательство: Для доказательства этой теоремы мы покажем, как для каждого правила apbqw машины 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_sb

{c_iq_s q_sc_i} , c_i ЄD_U