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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

aqbp*, где a,bÎD; p,qÎQ; *Î{Л, П, Н},

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

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

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

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

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

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

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

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

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

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

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

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

Л	101
Н	1001
П	10001
	100001 Здесь число нулей всегда четно. M нулей
	1000001 Здесь всегда нечетное число нулей M нулей

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

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

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

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

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

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

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

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

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

Определение 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_U
UQ_U
U{Ñ}. Тогда команде (1) сопоставим следующую группу правил подстановки:

q_j
a®q_s
Ñb

{c_i
q_s
Ѯq_s
c_i
} , c_i
ЄD_U

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

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

q_j
a®bq_s

Командам вида (3) - q_j
a®q_s
b

Командам вида (4) - q_j
aab.

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

®q_o
, машины U.

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

Замечание: Если а=L, т. е. командам Lq_j
®bq_s
w надо будет сопоставлять правило q_j
®q_s
b либо 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_N
UW_N
.

Обозначим

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

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

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

m_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 m_b
i
(1||Q*a_i
R)o U^*
o U₁

else U_о
o U*o U_i+1
.

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

a_i
ab_i

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

if then m_b
i
(1||Q*a_i
R) o U_!

else U_о
o U*o U_i+1
.

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

a_k
®b_k

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

if then m_b
k
(1||Q*a_k
R)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
?