Хопкрофт, Джон, Э., Мотвани, Раджив, Ульман, Джеффри, Д. - Введение в теорию автоматов, языков и вычислений (1082271), страница 84
Текст из файла (страница 84)
Таким образом„любая МТ М может быть пронмнтирована с помощью другой МТ М; использующей только ленточные символы О, 1 и В. Однако у М'должно быть очень много состояний, поскольку для имитации перехода М МТ М' должна сканировать ее ленточный символ и запомнить в своем конечном управлении все биты, показывающие, какой ленточный символ сканируется. Таким же образом мы сталкиваемся с огромными множествами состояний, и компьютер, который имитирует М; должен монтировать и демонтировать несколько дисков, решая, каким же является и каким будет следующее состояние М'. Естественно, о компьютерах, решающих задачи подобного рода, никто и не задумывается, поэтому обычные операционные системы не имеют поддержки для таких задач.
Однако при желании мы могли бы запрограммировать "голый", лишенный операционной системы компьютер, снабдив его соответствующими возможностями. К счастью, вопрос о том, как имитировать МТ с огромным числом состояний или ленточных символов, разрешим. В разделе 9.2.3 будет показано, что можно построить МТ, которая по существу есть МТ с "запоминаемой программой".
Эта МТ, называемая "универсальной", считывает функцию переходов любой МТ, закодированную в двоичном виде на ленте, и имитирует ее. Универсальная МТ имеет вполне разумное число состояний и ленточных символов. С помощью имитации универсальной МТ обычный компьютер может быть запрограммирован для допускания какого угодно рекурсивно перечнслимого языка без необходимости имитировать количества состояний, которые нарушают пределы того, что может быть записано на диске. Приведем реалистичную, хотя и неформальную, модель функционирования обычного компьютера. 1.
Предполагается, что память компьютера состоит из неопределенно длинной последовательности сдов, каждое из которых имеет адрес. В реальном компьютере слова были бы длиной 32 или б4 бит, но мы длину слова ограничивать не будем. В качест- 8.6. МАШИНЫ ТЬЮРИНГА И КОМПЬЮТКРЫ 367 ве адресов используются целые О, 1, 2 и т.д.
В реальном компьютере последовательными целымн нумеровались бы отдельные байты, поэтому адреса слов были бы кратны 4 или 8, но это различие несущественно. В реальном компьютере количество слов "памяти" также было бы ограничено, но мы хотим учесть солержимое произвольного числа дисков или других запоминающих устройств, поэтому предполагаем, что количество слов ничем не ограничено. 2.
Предполагается, что программа компьютера записывается в некоторые слова памяти. Каждое из этих слов представляет простую инструкцию, как в машинном или ассемблерном языке обычного компьютера. Г!римерами служат инструкции перемещения данных из одного слова в другое или прибавления одного слова к другому. Допускается "непрямая адресация", т.е.
инструкция может ссылаться на другое сло- во и использовать его содержимое в качестве адреса слова, к которому применяется операция. Эта возможность, обычная для современных компьютеров, нужна для доступа к массивам, для следования по связям списков и вообще для выполнения операций с указателями. 3. Предполагается, что каждая инструкция использует ограниченное (конечное) число слов и изменяет значение не более одного слова. 4. Обычный компьютер имеет регистры — слова памяти с особо быстрым доступом.
Часто такие операции, как сложение, применяются только к регистрам, но мы по- лобные ограничения не вводим и считаем, что с любым словом можно произвести любую операцию. Относительная скорость операций на различных словах значения не имеет, поскольку вообще не нужна при сравнении возможностей компьютеров н машин Тьюринга по распознаванию языков. Даже если нас интересует полнномнальная связь между временами работы, разница в скорости доступа к различным словам остается неважной, поскольку влияет "лишь" на константный сомножитель. Возможная конструкция машины Тьюринга для имитации компьютера представлена на рнс.
8.22. Эта МТ имеет несколько лент, но с помощью построений из раздела 8.4.1 ее можно преобразовать в одноленточную. Первая лента представляет всю память компьютера, Мы использовали код, в котором адреса слов памяти в порядке их номеров перемежаются со значениями (содержимым) этих слов. И адреса, и значения записаны в двоичном виде. Маркеры.' и Ф используются для того, чтобы легко было найти конец адреса н значения слова и различить, является лн двоичная цепочка адресом нлн значением.
Еще один маркер, 3, отмечает начало последовательности адресов и значений. Вторая лента представляет собой "счетчик инструкций", Эта лента содержит одно двоичное целое, представляющее одну из позиций в памяти на первой ленте. Оно интерпретируется как адрес инструкции, которая должна быть выполнена следующей.
Третья лента содержит "адрес памятн" или значение по нему после того, как этот адрес устанавливается на первой ленте. Для выполнения инструкции МТ должна найти 368 ГЛАВА 8. ВВЕДЕНИЕ В ТЕОРИЮ МАШИН ТЬЮРИНГА значение по одному или несколькнлт адресам памяти, где хранятся данные, участвующие в вычислении. Нужный адрес копируется на ленту 3 и сравнивается с адресами на ленте 1 до совпадения, Значение по этому адресу копируется на третью ленту и пере- мешается в нужное место, как правило, по одному из начальных адресов, представляющих регистры компьютера.
Память Счетчик инструкций Адрес памяти Входной файл компьютера Рабочая память Рис. 8.22 Мишино Тьюринга, имитирующая обычный компьютер Наша МТ имитирует цикл инструкции (1пягтост1оп сус1е) компьютера следующим образом. 1. На первой ленте ищется адрес, совпадающий с номером инструкции на ленте 2.
Начиная с маркера 5, движемся вправо, сравнивая каждый адрес с содержимым ленты 2. Сравнить адреса на двух лентах легко, поскольку нужно лишь синхронно сдвигать ленточные головки вправо, проверяя совпадение обозреваемых символов. 2. Обнаружив адрес инструкции, исследуем значение по нему. Предположим, что слово представляет инструкцию„его первые биты задают действие (например, копировать, прибавить, ветвиться), а оставшиеся биты кодируют адрес илн адреса, используемые в этом действии. 8.6. МАШИНЫ ТЬЮРИНГА И КОМПЬЮТЕРЫ 369 3. Если в инструкции используется значение по некоторому адресу, то этот адрес является частью инструкции.
Он копируется на третью ленту, а позиция инструкции отмечается с помощью второй дорожки первой ленты (не показанной на рис. 8.22), поэтому при необходимости к инструкции легко вернуться. Ищем адрес на первой ленте, н значение по нему копируем на ленту 3, хранящую адрес памяти. 4.
Выполняем инструкцию илн ее часть, использующую данное значение. С новым значением можно сделать следующее: а) скопировать значение по другому адресу. Второй адрес извлекается из инструкции, помещается на ленту 3 и находится на ленте 1, как описано выше. Когда второй адрес найден, значение по нему копируется в пространство, зарезервированное для него.
Если для нового значения нужно больше или гяеньше памяти, чем для старого, доступное пространство изменяется путем сдвига (яЫй1п8 огег). Он осуществляется так. На рабочую ленту копируется вся значащая (без пробелов) часть ленты 1 справа от того места, куда нужно поместить новое значение. й. Новое значение записывается в пространство нужного объема.
!й. Рабочая лента копируется обратно, на ленту 1, непосредственно справа от нового значения. В особых случаях адрес может не встретиться на первой ленте, поскольку не использовался ранее. Тогда на первой ленте находится место, к которому относится данный адрес, при необходимости делается сдвиг, и в это место за- писывается адрес и новое значение; б) прибавить найденное значение к значению по другому адресу. Для получения второго адреса возвращаемся к инструкции. Ищем адрес на ленте 1. Вы- полняем двоичное сложение значения по этому адресу и значения, записанного на ленте 3. Сканируя два значения справа налево, МТ может выполнить сложение с переносом. Если для результата нужно больше места, на ленте 1 используется техника сдвига; в) перейти к выполнению инструкции по адресу, заданному значением на ленте 3. Для этого лента 3 просто копируется на ленту 2, и цикл инструкции на- чинается вновь.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
