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

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

 

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

 

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

 

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

 

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

 

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

 

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

 

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

 

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

 

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

 

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

 

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

 

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

 

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

 

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

 

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

 

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

 

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

 

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

 

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

 

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

 

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

 

Первая неувязка разбивается  на две:

 

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

 

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

 

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

 

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

 

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

 

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

 

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

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.

 

Обозначим