Хопкрофт, Джон, Э., Мотвани, Раджив, Ульман, Джеффри, Д. - Введение в теорию автоматов, языков и вычислений (1082271), страница 85
Текст из файла (страница 85)
5. Выполнив инструкцию и выяснив, что она не является переходом, к счетчику инструкций на ленте 2 прибавляем 1 и вновь начинаем цикл инструкции. В имитации компьютера с помощью МТ есть и другие подробности. На рис. 8.22 изображена четвертая лента, содержащая имитируемый вход компьютера, поскольку компьютер должен читать из файла свой вход — слово, проверяемое на принадлежность языку, МТ вместо файла может использовать ленту. 370 ГЛАВА 8.
ВВЕДЕНИЕ В ТЕОРИЮ МАШИН ТЬЮРИНГА Показана также рабочая лента. Имитация некоторых инструкций компьютера может эффективно использовать рабочую ленту или ленты для вычисления таких арифметических операций, как умножение. Наконец, можно предполагать, что компьютер порождает выход, говорящий о допустимости входных данных. Для перевода этого действия в термины МТ предположим, что у компьютера есть "допускающая" инструкция, которая, возможно, соответствует функции, вызываемой компьютером для печати уев в выходном файле. Когда МТ имитирует выполнение этой инструкции компьютера, она переходит в собственное допускающее состояние и останавливается, Хотя представленная выше аргументация далека от полного формального доказательства того, что МТ может имитировать обычный компьютер, она достаточно подробна, чтобы убедить, что МТ является подходящим представлением действий компьютера.
Итак, в качестве формального представления того, что может быть вычислено на любом тиле вычислительных устройств, в дальнейшем будет использоваться только машина Тьюринга. 8.6.3. Сравнение времени работы компьютеров и машин Тьюринга Теперь обратимая к вопросу о времени работы на машине Тьюринга, имитирующей компьютер. Как и раньше, мы исходим из следующих утверждений. ° Вопрос о времени работы важен, поскольку МТ используется для исследования вопросов не только о том, что вообще можно вычислить, но и о том, что можно вычислить с эффективностью, достаточной для практического использования компьютерного решения проблемы. ° Проблемы делятся на легко разрешимые (нх можно решить эффективно) и трудно разреипкиые (они могут быть решены, но настолько медленно, что их решением нельзя воспользоваться) на основе того, что можно решить за полиномиальное время, и что требует времени большего, чем любое полиномиальное.
° Таким образом, нужно убедиться, что если проблему можно решить за полиномиалыюе время на обычном компьютере. то ее можно решить за полиномиальное время на машине Тьюринга, и наоборот. Вследствие этой полиномиальной эквивалентности наши выводы о том, что могут и чего не могут машины Тью- ринга, адекватно применимы и к компьютерам. Напомним; в разлеле 8,4.3 было определено, что разница между временем работы на одноленточной и многоленточной МТ является полиномиальной, точнее, квадратичной. Таким образом, достаточно показать, что все, что может сделать компьютер, может и многоленточная МТ, описанная в разделе 8.б.2, причем за время, полиномиальное относительно времени работы компьютера.
Тогда то же самое будет справедливо и для одно- ленточной МТ. 8.6. МАШИНЫ ТЬЮРИНГА И КОМПЬЮТЕРЫ 371 Перед тем как доказать, что машина Тьюринга, описанная выше, может имитировать н шагов компьютера за время 0(н ), нам нужно исследовать вопрос умножения как машинной инструкции. Проблема в том, что предельное число битов в одном машинном слове не было установлено. Если.
скажем, компьютер начал бы со слова, содержащего 2, и должен был бы и раз последовательно умножить это слово само на себя, то оно имело бы значение 2 . Это число требует 2' е 1 битов для представления, поэтому время, необходимое машине Тьюринга для имитации этих л инструкций, будет, как минимум, экспоненциальным. Один из подходов разрешения этой проблемы заключается в том, чтобы настаивать, что слова имеют фиксированную максимальную длину, скажем, 64 бит. Тогда умножения (или другие операции), порождающие слишком длинные слова, буду~ приводить компьютер к остановке, и машине Тьюринга не нужно будет имитировать его дальше.
Мы сделаем более вольное предположение — компьютер использует слова, длина которых может неограниченно возрастать, но одной компьютерной инструкции позволено породить слово, которое на один бит длиннее, чем ее операнды. Пример 8.)6. При действии последнего ограничения сложение является допустимой операцией, поскольку длина результата может быть лишь на один бит больше, чем максимальная длина сяагаемых. Умножение недопустимо, поскольку два т-битовых слова могут дать произведение длиной 2кь Однако умножение «мбитовых целых можно имитировать с помощью т последовательных сложений, перемежаемых сдвигами сомножителей на один бит влево (что является еще одной операцией, увеличиваюшей длину слова на )).
Таким образом, мы все еше можем умножать неограниченно длинные слова, но время, нужное компьютеру, пропорционально квадрату длины операндов, П Предположив, что при выполнении компьютерной инструкции длина возрастает не более, чем на один бит, можно доказать полиномиальную взаимосвязь между двумя временами работы. Идея доказательства — заметить, что после выполнения и инструкций количество слов, упоминаемых на ленте памяти МТ, есть 0(п), и каждое компьютерное слово требует О(п) клеток МТ для его представления.
Таким образом, лента содержит О(л') клеток, и МТ может найти конечное число слов, необходимое для выполнения одной инструкции компьютера, за время 0(и ). Сушествует, однако, одно дополнительное требование к инструкциям. Даже если ин- струкция не порождает длинное слово в качестве результата, она может занимать очень много времени для его вычисления.
Поэтому делается дополнительное предположение, что сама по себе инструкция, применяемая к словам длиной не более А, может быть выполнена за Оф) шагов на многоленточной машине Тьюринга, Несомненно, что обычные операции компьютера, такие как сложение, сдвиг или сравнение значений, могу~ быть выполнены за О()) шагов миоголенточной МТ, поэтому мы лаже слишком либеральны, допуская, что может делать компьютер в одной инструкции.
Теорема 8.! 7. Пусть компьютер обладает следующими свойствами. 372 ГЛАВА 8. ВВЕДЕНИЕ В ТЕОРИЮ МАШИН ТЬЮРИНГА 1. У него есть только инструкции, увеличивающие максимальную длину слова не более, чем на 1. 2. У него есть только инструкции, которые многоленточная МТ может выполнить на словах длиной 1г за 011г~) нли меньшее число шагов. Тогда машина Тьюринга, описанная в разделе 8,6.2, может имитировать п шагов компьютера за О(и ) своих шагов. Доказательство.
Начнем с замечания, что первая лента 1лента памяти) машины Тьюринга 1см. рнс, 8.22) вначале содержит только программу компьютера. Эта програмна может быть длинной, но длина ее фиксирована и является константой, не зависящей от л — числа шагов выполнения ее инструкций. Таким образом, существует некоторая константа с, представляющая собой наибольшее из компьютерных слов или адресов, встречающихся в программе. Существует также константа а' — количество слов, запиваемых программой. Итак, после выполнения л шагов компьютер не может породить слово длиннее, чем с+ л, и не может создать или использовать адрес, занимающий больше с+ и битов.
Каждая инструкция порождает не более одного нового адреса, получающего значение, поэтому общее число адресов после выполнения и инструкций не превышает Ы+ л. Поскольку любая комбинация "адрес-слово" требует не более 21с + и) + 2 разрядов, включая адрес, содержимое и два маркера для их разделения, общее число клеток, занятых после имитации л инструкций, не больше 21Ы+ п)1с+ л+ 1). Поскольку с и И вЂ” констанз ты, это число клеток есть О(п ), Нам известно, что каждый из фиксированного числа просмотров адресов, используемых в одной инструкции компьютера, может быть выполнен за время 01л ). Поскольку слова имеют длину 01п), допустим, что сами по себе инструкции могут быть выполнены з на МТ за время 0(н ).
Остается еше цена инструкции, которая составлена временем, необходимым машине Тьюринга для создания нового пространства, чтобы сохранить новое или расширенное слово. Однако сдвиг включает копирование данных объемом не более 0(л') с ленты 1 на рабочую ленту и обратно.
Таким образом, сдвиг также требует лишь О(л ) времени на одну инструкцию компьютера. Заключаем, что МТ имитирует один шаг компьютера за 01л ) своих шагов. Таким образом, как утверждается в теореме, и шагов компьютера можно проимитировать за 0(л ) шагов машины Тьюринга. П В заключение отметим, что возведение в куб числа шагов позволяет многоленточной МТ имитировать компьютер. Из материала раздела 8.4.3 известно, что одноленточная МТ может имитировать многоленточную не более, чем за квадрат числа шагов. Таким образом, имеет место следуюцгее утверждение.
Теорема 8.18. Выполнение л шагов работы компьютера типа, описанного в теореме 8.17, можно проимитировать на одноленточной машине Тьюринга с использованием не более 0(л') шагов, ь1 8.6. МАШИНЫ ТЬЮРИНГА И КОМПЬЮТЕРЫ 373 Резюме Машина Тьюринга. МТ представляет собой абстрактную вычислительную машину, мощность которой совпадает с мощностью как реальных компьютеров, так и других математических определений того, что может быть вычислено. МТ состоит из управления с конечным числом состояний и бесконечной ленты, разделенной на клетки.
Каждая клетка хранит один из конечного числа ленточных символов, и одна из клеток является текущей позицией ленточной головки. МТ совер- шает переходы на основе своего текущего состояния н ленточного символа в клетке, обозреваемой головкой. За один переход она изменяет состояние, переписывает обозреваемый символ и сдвигает головку на одну клетку вправо или влево. Дапускание машиной Тьюринга.
МТ начинает работу над входом, цепочкой входных символов конечной длины на ее ленте„причем остальные клетки на ленте заполнены пробелами, Пробел является одним из ленточных символов, и вход образуется из подмножества ленточных символов, не включающего пробел. Эти символы называются входными.
МТ допускает свой вход, попадая в допускающее состояние. Рекурсивна-перечислииые языки. Языки, допускаемые МТ, называются рекурсивно-перечнслимыми (РП-языками). Таким образом, РП-языки — это языки, которые могут быть распознаны или допущены вычислительным устройством какого- либо вида. Мгновенные описания МТ. Текущую конфигурацию МТ можно описать цепочкой конечной длины, которая включает все клетки ленты между крайними слева и справа значащими символами (отличными от пробела).
Состояние и позиция го- ловки указываются помещением состояния в последовательность ленточных символов непосредственно слева от обозреваемой клетки. Запоминание в конечном управлении. Иногда построение МТ для некоторого языка облегчается за счет того, что состояние представляется как имеющее несколько компонентов. Один из них является управляющим и функционирует, как состояние. Другие компоненты содержат данные, которые нужно запомнить машине.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
