0qo1qsЛ
|
1qo2qsЛ
|
2qo3qsЛ
|
………
|
7qo8qsЛ
|
8qo9qsЛ
|
9qo0qoЛ
|
Lqo!Л®
|
®0qs0qsЛ
|
1qs1qsЛ
|
2qs2qsЛ
|
………
|
7qs7qsЛ
|
8qs8qsЛ
|
9qs9qsЛ
|
LqsL!Н
|
Рис. 4.1. Линейная запись функциональной схемы МТ, вычисляющей U1(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), где Р Є 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
Командам вида (3) - qja ® qsb
Командам вида (4) - qja a b.
Самым последним в системе правил подстановки НАМ будет начальное
правило
® qo , машины U.
где qo - начальное состояние U.
Замечание: Если а=L, т. е. командам Lqj ® bqsw надо будет сопоставлять правило qj ® qsb либо qj ® bqs в зависимости от
значения w. Все такие правила
подстановки надо собрать в конце схемы, сразу перед начальным правилом.
Обратите внимание, что если на вход N подать слово, к
которому U не применим, то N будет бесконечно долго подставлять qo в начало слова.
N применим к тем же словам, что и U.
Допустим существование слова Р, к которому U применим, а N - нет. Раз U применим, то пусть
его заключительной командой является команда aq ® b!H. Ей по построению N соответствует
терминальное правило подстановки, которое должно выполняться, т. к. в схеме N нет двух правил с
одинаковыми правыми частями..
Пришли к противоречию.
Доказательство теоремы 4.2 закончено.
Теорема 4.3. Для любого НАМ N существует машина
Тьюринга U такая, что
N(P)= U(P) для всех PЄDN*.
Алфавит U : DU = DNUWN.
Обозначим
U*(Р)=*Р, т. е. МТ , ставящую символ * перед обрабатываемым
символом.
U!(P)=P осталось без изменения слова.
|
|
1 || Q*aR если QaR=P
0 || P* если a не входит в P
|
mb (1||Q*aR)=QbR
U0 (0||P*)=P
Надеемся, что читателю будет не сложно построить функциональную
схему любой из этих машин.
Схема НАМ N состоит из правил либо вида a®b, либо aab, где
a,b Є (DUW)*.
Каждому правилу вида
ai®bi
сопоставим машину Ui c функциональной схемой вида
if then mbi(1||Q*aiR)o U*o U1
else Uоo U*o Ui+1 .
Каждому терминальному правилу вида
aiabi
сопоставим машину Ui c функциональной схемой вида
if then mbi(1||Q*aiR) o U!
else Uоo U*o Ui+1 .
Последнему правилу подстановки в схеме НАМ N вида
ak®bk
сопоставим машину Uk с функциональной схемой
if then mbk(1||Q*akR)o U*o U1
else Uоo U*o U! .
В части else появление машины U! связано с тем, что по определению НАМ завершается, если не
применимо ни одно из правил подстановки.
Функциональная схема искомой машины U будет иметь вид
U*(P)o U1o U2o … o Uk ,
где k - число правил подстановки в схеме НАМ N.
Доказательство теоремы 4.3 закончено.
Из теорем 4.2 и 4.3 следует, что если какая-то алгоритмическая
проблема разрешима в одной алгоритмической системе, то она автоматически
разрешима и в другой. Если предположить, что какая-то алгоритмическая проблема
неразрешимая в одной алгоритмической системе, но разрешима в другой, то придём
к противоречию. Действительно, согласно теоремам 4.2 и 4.3 если эта проблема
разрешима хотя бы в одной системе, то она разрешима и в другой.
Выводы :
Для любой алгоритмической системы существует универсальный
исполнитель, который есть интерпретатор множества действий заданной
алгоритмической системы.;
В силу тезиса Тьюринга, любой алгоритм реализуем в терминах
действий последовательной, параллельной композиций, выбора и цикла и базового
набора действий;
Проблема самоприменимости алгоритмической системы алгоритмически
не разрешима;
Если алгоритмическая проблема не разрешима, то она не разрешима в
любой другой эквивалентной алгоритмической системы;
Алгоритмические системы МТ и НАМ эквивалентны.
Вопросы :
Что такое интерпретация?
Что такое кодирование?
В чем проблема линеаризации Ф.с. для МТ?
Что такое универсальный исполнитель:
- он может исполнять заданный А в любой А.с.?
- он может исполнять любой А, выразимый в данной А.с.?
Как решается проблема произвольности алфавита в УМТ?
Что такое А.п.?
Самоприменимость - что это такое?
А.п. самоприменимости разрешима?
В МТ А не закончен если нет применимого правила, в НАМ в этом
случае А - закончен. Как это несоответствие решается при доказательстве
сводимости МТ к НАМ и наоборот?
Что означает запись:
Если Fa (*P), то M(1||Q*aR)o U*o U1 иначе U0o U*o Ui+1?
Список
литературы
Для подготовки данной работы были использованы материалы с сайта http://www.ergeal.ru/