dzhon_khopkroft_radzhiv_motvani_dzheffri _ulman_vvedenie_v_teoriyu_avtomatov_yazy kov_i_vychisleniy_2008 (852747), страница 83
Текст из файла (страница 83)
Эта МТ имеет несколько лент, но с помощью построений из раздела 8.4.1 ееможно преобразовать в одноленточную. Первая лента представляет всю память компьютера. Мы использовали код, в котором адреса слов памяти в порядке их номеров перемежаются со значениями (содержимым) этих слов. И адреса, и значения записаны в двоичном виде. Маркеры * и # используются для того, чтобы легко было найти конец адресаи значения слова и различить, является ли двоичная цепочка адресом или значением.Еще один маркер, $, отмечает начало последовательности адресов и значений.Вторая лента представляет собой “счетчик инструкций”. Эта лента содержит однодвоичное целое, представляющее одну из позиций в памяти на первой ленте. Оно интерпретируется как адрес инструкции, которая должна быть выполнена следующей.Третья лента содержит “адрес памяти” или значение по нему после того, как этот адрес устанавливается на первой ленте.
Для выполнения инструкции МТ должна найти значение поодному или нескольким адресам памяти, где хранятся данные, участвующие в вычислении.Нужный адрес копируется на ленту 3 и сравнивается с адресами на ленте 1 до совпадения.Значение по этому адресу копируется на третью ленту и перемещается в нужное место, какправило, по одному из начальных адресов, представляющих регистры компьютера.КонечноеуправлениеПамять$ 0 ∗Счетчик инструкций10011Адрес памяти#1 ∗#10 ∗#11 ∗#100 ∗1101110Входной файл компьютераРабочая памятьРис. 8.22.
Машина Тьюринга, имитирующая обычный компьютер8.6. ÌÀØÈÍÛ ÒÜÞÐÈÍÃÀ È ÊÎÌÏÜÞÒÅÐÛСтр. 369369Наша МТ имитирует цикл инструкции (instruction cycle) компьютера следующимобразом.1.На первой ленте ищется адрес, совпадающий с номером инструкции на ленте 2. Начиная с маркера $, движемся вправо, сравнивая каждый адрес с содержимым ленты 2. Сравнить адреса на двух лентах легко, поскольку нужно лишь синхронно сдвигать ленточные головки вправо, проверяя совпадение обозреваемых символов.2.Обнаружив адрес инструкции, исследуем значение по нему. Предположим, что слово представляет инструкцию, его первые биты задают действие (например, копировать, прибавить, ветвиться), а оставшиеся биты кодируют адрес или адреса, используемые в этом действии.3.Если в инструкции используется значение по некоторому адресу, то этот адрес является частью инструкции.
Он копируется на третью ленту, а позиция инструкции отмечается с помощью второй дорожки первой ленты (не показанной на рис. 8.22), поэтому при необходимости к инструкции легко вернуться. Ищем адрес на первой ленте, и значение по нему копируем на ленту 3, хранящую адрес памяти.4.Выполняем инструкцию или ее часть, использующую данное значение.
С новымзначением можно сделать следующее:а) скопировать значение по другому адресу. Второй адрес извлекается из инструкции, помещается на ленту 3 и находится на ленте 1, как описано выше.Когда второй адрес найден, значение по нему копируется в пространство, зарезервированное для него.
Если для нового значения нужно больше илименьше памяти, чем для старого, доступное пространство изменяется путемсдвига (shifting over). Он осуществляется так.i. На рабочую ленту копируется вся значащая (без пробелов) часть ленты 1 справа от того места, куда нужно поместить новое значение.ii.
Новое значение записывается в пространство нужного объема.iii. Рабочая лента копируется обратно, на ленту 1, непосредственно справаот нового значения.В особых случаях адрес может не встретиться на первой ленте, поскольку неиспользовался ранее. Тогда на первой ленте находится место, к которому относится данный адрес, при необходимости делается сдвиг, и в это место записывается адрес и новое значение;б) прибавить найденное значение к значению по другому адресу. Для получения второго адреса возвращаемся к инструкции. Ищем адрес на ленте 1.
Выполняем двоичное сложение значения по этому адресу и значения, записанного на ленте 3. Сканируя два значения справа налево, МТ может выполнить370Стр. 370ÃËÀÂÀ 8. ÂÂÅÄÅÍÈÅ Â ÒÅÎÐÈÞ ÌÀØÈÍ ÒÜÞÐÈÍÃÀсложение с переносом. Если для результата нужно больше места, на ленте 1используется техника сдвига;в) перейти к выполнению инструкции по адресу, заданному значением на ленте 3. Для этого лента 3 просто копируется на ленту 2, и цикл инструкции начинается вновь.5.Выполнив инструкцию и выяснив, что она не является переходом, к счетчику инструкций на ленте 2 прибавляем 1 и вновь начинаем цикл инструкции.В имитации компьютера с помощью МТ есть и другие подробности.
На рис. 8.22 изображена четвертая лента, содержащая имитируемый вход компьютера, поскольку компьютер должен читать из файла свой вход — слово, проверяемое на принадлежностьязыку. МТ вместо файла может использовать ленту.Показана также рабочая лента. Имитация некоторых инструкций компьютера можетэффективно использовать рабочую ленту или ленты для вычисления таких арифметических операций, как умножение.Наконец, можно предполагать, что компьютер порождает выход, говорящий о допустимости входных данных.
Для перевода этого действия в термины МТ предположим, чтоу компьютера есть “допускающая” инструкция, которая, возможно, соответствует функции, вызываемой компьютером для печати yes в выходном файле. Когда МТ имитируетвыполнение этой инструкции компьютера, она переходит в собственное допускающеесостояние и останавливается.Хотя представленная выше аргументация далека от полного формального доказательства того, что МТ может имитировать обычный компьютер, она достаточно подробна,чтобы убедить, что МТ является подходящим представлением действий компьютера.Итак, в качестве формального представления того, что может быть вычислено на любомтипе вычислительных устройств, в дальнейшем будет использоваться только машинаТьюринга.8.6.3. Ñðàâíåíèå âðåìåíè ðàáîòû êîìïüþòåðîâ è ìàøèí ÒüþðèíãàТеперь обратимся к вопросу о времени работы на машине Тьюринга, имитирующейкомпьютер. Как и раньше, мы исходим из следующих утверждений.• Вопрос о времени работы важен, поскольку МТ используется для исследованиявопросов не только о том, что вообще можно вычислить, но и о том, что можновычислить с эффективностью, достаточной для практического использованиякомпьютерного решения проблемы.• Проблемы делятся на легко разрешимые (их можно решить эффективно) и трудно разрешимые (они могут быть решены, но настолько медленно, что их решением нельзя воспользоваться) на основе того, что можно решить за полиномиальное время, и что требует времени большего, чем любое полиномиальное.8.6.
ÌÀØÈÍÛ ÒÜÞÐÈÍÃÀ È ÊÎÌÏÜÞÒÅÐÛСтр. 371371• Таким образом, нужно убедиться, что если проблему можно решить за полиномиальное время на обычном компьютере, то ее можно решить за полиномиальное время на машине Тьюринга, и наоборот. Вследствие этой полиномиальнойэквивалентности наши выводы о том, что могут и чего не могут машины Тьюринга, адекватно применимы и к компьютерам.Напомним: в разделе 8.4.3 было определено, что разница между временем работы наодноленточной и многоленточной МТ является полиномиальной, точнее, квадратичной.Таким образом, достаточно показать, что все, что может сделать компьютер, может имноголенточная МТ, описанная в разделе 8.6.2, причем за время, полиномиальное относительно времени работы компьютера. Тогда то же самое будет справедливо и для одноленточной МТ.Перед тем как доказать, что машина Тьюринга, описанная выше, может имитироватьn шагов компьютера за время O(n3), нам нужно исследовать вопрос умножения как машинной инструкции.
Проблема в том, что предельное число битов в одном машинномслове не было установлено. Если, скажем, компьютер начал бы со слова, содержащего 2,и должен был бы n раз последовательно умножить это слово само на себя, то оно имелоnбы значение 22 . Это число требует 2n + 1 битов для представления, поэтому время, необходимое машине Тьюринга для имитации этих n инструкций, будет, как минимум,экспоненциальным.Один из подходов разрешения этой проблемы заключается в том, чтобы настаивать,что слова имеют фиксированную максимальную длину, скажем, 64 бит.
Тогда умножения (или другие операции), порождающие слишком длинные слова, будут приводитькомпьютер к остановке, и машине Тьюринга не нужно будет имитировать его дальше.Мы сделаем более вольное предположение — компьютер использует слова, длина которых может неограниченно возрастать, но одной компьютерной инструкции позволенопородить слово, которое на один бит длиннее, чем ее операнды.Пример 8.16. При действии последнего ограничения сложение является допустимойоперацией, поскольку длина результата может быть лишь на один бит больше, чем максимальная длина слагаемых.
Умножение недопустимо, поскольку два m-битовых словамогут дать произведение длиной 2m. Однако умножение m-битовых целых можно имитировать с помощью m последовательных сложений, перемежаемых сдвигами сомножителей на один бит влево (что является еще одной операцией, увеличивающей длину слова на 1). Таким образом, мы все еще можем умножать неограниченно длинные слова, новремя, нужное компьютеру, пропорционально квадрату длины операндов.
Предположив, что при выполнении компьютерной инструкции длина возрастает неболее, чем на один бит, можно доказать полиномиальную взаимосвязь между двумя временами работы. Идея доказательства — заметить, что после выполнения n инструкцийколичество слов, упоминаемых на ленте памяти МТ, есть O(n), и каждое компьютерноеслово требует O(n) клеток МТ для его представления. Таким образом, лента содержит372Стр. 372ÃËÀÂÀ 8. ÂÂÅÄÅÍÈÅ Â ÒÅÎÐÈÞ ÌÀØÈÍ ÒÜÞÐÈÍÃÀO(n2) клеток, и МТ может найти конечное число слов, необходимое для выполнения одной инструкции компьютера, за время O(n2).Существует, однако, одно дополнительное требование к инструкциям. Даже если инструкция не порождает длинное слово в качестве результата, она может занимать оченьмного времени для его вычисления.
Поэтому делается дополнительное предположение,что сама по себе инструкция, применяемая к словам длиной не более k, может быть выполнена за O(k2) шагов на многоленточной машине Тьюринга. Несомненно, что обычныеоперации компьютера, такие как сложение, сдвиг или сравнение значений, могут бытьвыполнены за O(k) шагов многоленточной МТ, поэтому мы даже слишком либеральны,допуская, что может делать компьютер в одной инструкции.Теорема 8.17. Пусть компьютер обладает следующими свойствами.1.У него есть только инструкции, увеличивающие максимальную длину слова не более, чем на 1.2.У него есть только инструкции, которые многоленточная МТ может выполнить насловах длиной k за O(k2) или меньшее число шагов.Тогда машина Тьюринга, описанная в разделе 8.6.2, может имитировать n шагов компьютера за O(n3) своих шагов.Доказательство.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
