Существование универсальных вычислителей. Алгоритмические проблемы и взаимосвязь алгоритмических систем.
Существование универсальных вычислителей. Алгоритмические проблемы и взаимосвязь алгоритмических систем.Существование универсальных вычислителей.Теперь задумаемся вот о чём. Каждый раз, когда мы строили программу для новой Машины Тьюринга, даже если мы при этом использовали программы для других машин, не явно предполагалось, что как-то, где-то, кем-то строилась каретка, обладающая заданным набором состояний, способная распознавать и записывать символы из заданного алфавита и т.п. Построение такой каретки - сама по себе задача не из простых. Для каждого нового алгоритма мы вынуждены строить новый исполнитель. Это выглядит примерно так, как если бы для каждой новой программы нам надо было строить новый компьютер.А нельзя ли построить такой исполнитель, который был бы способен выполнить любой алгоритм, заданный в виде программы для Машины Тьюринга? Положительный ответ на этот вопрос являлся бы математическим обоснованием существования универсального вычислителя, т.е. способного выполнить любой должным образом записанный алгоритм, вычислить любую вычислимую функцию.Итак, пусть нам надо построить Универсальную Машину Тьюринга, назовём её УМТ, для которой:исходными данными являются программа другой машины, назовём её МТ, с исходными данными Д последней;результат применения УМТ к этим исходным данным должен быть таким же, как применение МТ к её исходным данным, то естьУМТ(МТ,Д)=МТ(Д).Из-за чисто технической громоздкости мы не будем давать полного доказательства существования УМТ, а дадим лишь обоснование её существования. В этом обосновании мы покажем основную идею доказательства.Представим себя в качестве такой УМТ и опишем в интуитивной форме алгоритм своей работы. Состояние воображаемой каретки будем записывать под обозреваемой ячейкой ленты. Программу имитируемой МТ считаем пока заданной в виде таблицы.Интерпретирующий алгоритм для УМТ:Обозревай ячейку, под которой написана буква (состояние);Отыщи в таблице строку, обозначенную этой буквой;В найденной строке обозревай тройку символов, которая стоит на пересечении со столбцом, обозначенным буквой, вписанной в обозреваемую ячейку;Замени букву в обозреваемой ячейке на первую букву тройки;Если второй буквой тройки является “!”, то стоп;Если в обозреваемой ячейке третья буква “Н”, то сотри букву под обозреваемой ячейкой и запиши туда вторую букву тройки (смена состояния);Если в обозреваемой тройке третья буква “Л”, то сотри букву под обозреваемой ячейкой, сдвинься влево и запиши под этой ячейкой вторую букву тройки;Если в обозреваемой тройке третья буква “П”, то сотри букву под обозреваемой ячейкой, сдвинься вправо и запиши под этой ячейкой вторую букву тройки;Перейди к шагу 1.Для того, чтобы преобразовать это описание в программу Машины Тьюринга, надо решить две основные проблемы:Как задавать программу и конфигурацию имитируемой МТ на ленте?Так как произвольная МТ может иметь произвольный алфавит, то какой алфавит должен быть у УМТ?Первая проблема разбивается на две:как задать программу на ленте?как задать конфигурацию, чтобы отмечать текущее положение каретки имитируемой МТ (решение в виде символа под текущей ячейкой не годится).Программу МТ будем записывать пятеркамиqp , где ,D; p,qQ; {Л, П, Н},здесь - символ , соответствующий строке таблицы;q - столбцу таблицы.На рисунке 4.1. показана линейная запись функциональной схемы для U1(n).Рис. 4.1. Линейная запись функциональной схемы МТ, вычисляющей U1(n).Такое представление программы обеспечивает взаимнооднозначное соответствие с табличной формой записи, а стало быть ничего из таблицы при этом не теряется и ничего не добавляется.Как задать на ленте конфигурацию имитируемой машины? Напомним, что под конфигурацией Машины Тьюринга мы понимаем слово на ленте и положение каретки по отношению к слову. Здесь основная трудность: где записывать символ текущего состояния каретки. Будем записывать символы исходного слова на ленте через ячейку. В образовавшиеся пустые ячейки ленты будем записывать справа от обозреваемого символа текущее состояние каретки.Теперь рассмотрим проблему алфавита. Напомним, эта проблема состоит в том, что УМТ должна иметь определенный алфавит, который не может изменяться. В то же время мы не можем знать заранее, с какими алфавитами будут работать МТ, которые будет интерпретировать наша УМТ. Решение этой проблемы - кодирование символов из алфавита МТ символами алфавита УМТ. При этом важно позаботиться о том, чтобы:один и тот же символ из алфавита МТ всегда изображался одной и той же последовательностью символов из алфавита УМТ;разные символы из алфавита МТ всегда изображались разными последовательностями символов из алфавита УМТ.В качестве алфавита УМТ выберем алфавит {0,1}, расширенный небольшим количеством вспомогательных сим...
Другие файлы:
Алгоритмическое моделирование элементов экономических систем. Практикум
Рассматриваются основы алгоритмического моделирования и подробно описываются процессы разработки ряда алгоритмических моделей экономических систем. Пр...
Алгоритмические машины
Происхождение и сущность понятия "алгоритм". Основные требования к алгоритмам. Роль абстрактных алгоритмических систем. Алгоритм как абстрактная машин...
Теория и применение алгоритмических измерений
Изложены современные методы и алгоритмы аппаратно-программной реализации цифровых алгоритмических измерений, закладываемых на стадии создания информац...
Взаимосвязь открытых систем (основы теории и практики)
Данное учебное пособие соответствует практической части предмета «Взаимосвязь открытых систем» и представляет собой курс семинарских и лабораторных за...
Конгруэнции Фраттини универсальных алгебр
Исследование самых абстрактных алгебраических систем, в частности, универсальных алгебр. Основные определения, обозначения и используемые результаты....
