Хопкрофт, Джон, Э., Мотвани, Раджив, Ульман, Джеффри, Д. - Введение в теорию автоматов, языков и вычислений (1082271), страница 78
Текст из файла (страница 78)
8.15 слева от вызова подпрограммы; в них участвуют только состояния с!е и с!», Справа от вызова подпрограммы (см. рис. 8.15) представлены состояния с/~ 4м. Состояния с!ь !!» и !!, предназначены для получения управления после того, как Сору ско- пировала блок из и нулей и находится в МО 0 '1д,О"1О'". Эз.и состояния приводят к конфигурации !1,0" "1О"0~.
В этот момент опять начинается цикл, удаляется крайний слева О и вызывается Сору для нового копирования блока из и нулей. Как исключение, в состоянии г), МТ может обнаружить, что все гя нулей заменены пробелами, т.е. )г = гл. В данном случае производится переход в состояние г)м. Это состояние с помощью состояния дп заменяет символы 10" 1 в начале ленты пробелами, после чего достигается состояние останова !)м.
В этот момент МТ имеет МО дмО, и ее работа завершена. С) 8.3,4. Упражнения к разделу 8.3 8.3.1. (1) Переделайте ваши машины Тьюринга из упражнения 8.2.2, используя пре- имущества техники программирования, обсуждаемой в данном разделе. 8.3.2. (!) Обычные операции в программах типа машин Тьюринга используют "сдвиг" ("зЫО!пй огег'*). Предположим, в текущей позиции головки нужно создать дополнительную клетку, в которую можно было бы записать некоторый символ.
Однако изменять ленту таким способом нельзя. Придется сдвинуть содержимое ленты справа от головки на одну клетку вправо и затем вернуться к текущей позиции. Покажите, как выполнить данную операцию. Указание. Зарезервируйте специальный символ для отметки позиции, в которую нужно вернуться. 8.3.3. (к) Постройте подпрограмму перемещения головки МТ из ее текущей позиции вправо с пропуском нулей до достижения первой 1 или пробела. Если текущая позиция не содержит О, то МТ останавдивается.
Можно предполагать, что ленточными символами являются только О, 1 и В (пробел). Используйте полученную подпрограмму для построения МТ, допускающей все цепочки из 0 и 1, в которых нет двух ! подряд. 8.4. Расширения базовой машины Тьюринга В этом разделе представлены некоторые вычислительные модели, связанные с машинами Тьюринга и имеющие такую же мощность (в смысле распознавания языков), что и базовая модель МТ, с которой мы работали до сих пор. Одна из них, многоленточная МТ, позволяет легко имитировать работу компьютера или других видов машин Тьюринга. И хотя многоленточные машины не мощнее базовой модели, речь также пойдет об их способности допускать языки. Затем рассматриваются недетерминированные магцины Тьюринга — расширение основной модели, в котором разрешается совершать любой из конечного множества переходов в данной ситуации.
Это расширение в некоторых случаях также облегчает "программирование'* машин Тьюринга„не добавляя ничего к распознавательной мощности базовой модели. 346 ГЛАВА 8. ВВЕДЕНИЕ В ТЕОРИЮ МАШИН ТЬЮРИНГА 8.4Л. Многоленточные машины Тьюринга Многоленточная машина Тьюринга представлена на рис.
8.16. Устройство имеет конечное управление (состояния) и некоторое конечное число лент. Каждая лента разделена на клетки, и каждая клетка может содержать любой символ из конечного ленточного алфавита. Как и у одноленточных МТ, множество ленточных символов включает пробел, а также имеет подмножество входных символов, к числу которых пробел не принадлежит. Среди состояний есть начальное и допускающие.
Начальная конфи- гурация такова. 1. Вход (конечная последовательность символов) размещен на первой ленте. 2. Все остальные клетки всех лент содержат пробелы. 3. Конечное управление находится в начальном состоянии. 4. Головка первой ленты находится в левом конце входа. 5. Головки всех других лент занимают произвольное положение. Поскольку все ленты, кроме первой, пусты, начальное положение головок на них не имеет значения (все клетки "выглядят'* одинаково). Рис. В.!б. й1ногоаентоннан машина Тьюринга Переход многоленточной МТ зависит от состояния и символа, обозреваемого каждой головкой. За один переход многоленточная МТ совершает следующие действия. 1.
Управление переходит в новое состояние, которое может совпадать с предыдущим. 2. На каждой ленте в обозреваемую клетку записывается новый символ. Любой из них может совпадать с символом, бывшим там раньше. 8.4. РАСШИРЕНИЯ БАЗОВОЙ МАШИНЫ ТЬЮРИНГА 347 3. Каждая из ленточных головок сдвигается влево или вправо или остается на месте. Головки сдвигаются независимо друг от друга, поэтому разные головки могут двигаться в разных направлениях, а некоторые вообще оставаться на месте. Формальная запись переходов не приводится — ее вид является непосредственным обобщением записи дпя одноленточной МТ, за исключением того, что сдвиги теперь обозначаются буквами Е,?? или Я. Возможность оставлять головку на месте не была предусмотрена для одноленточных МТ, поэтому в их записи не было 5.
Постарайтесь сами представить подходящую запись МО 1конфнгураций) многоленточных МТ; формально она здесь также не приводится. Многоленточные МТ, как и одноленточные, допускают, попадая в допускающее состояние. 8.4.2. Эквивалентность одноленточных и многоленточных машин Тьюринга Напомним, что рекурсивно перечнслимые языки определяются как языки, допускаемые одноленточными МТ. Очевидно, что многоленточные МТ допускают все рекурсивно перечислнмые языки, поскольку одноленточная МТ является частным случаем многоленточной. Но существуют ли не рекурсивно перечислимые языки, допускаемые многоленточными МТ? Ответом является "нет", и мы докажем это, показав, как многоленточная МТ имитируется с помощью одноленточной. Теорема 8.9.
Каждый язык, допускаемый многоленточной МТ, рекурсивно перечислим. Доказательство. Идею доказательства иллюстрирует рис. 8,17. Предположим, что язык Е допускается А-ленточной МТ М. Она имитируется с помощью одноленточной МТ Л', лента которой состоит из 21г дорожек. Половина этих дорожек содержит ленты машины М, а каждая из дорожек второй половины содержит один-единственный маркер, указывающий позицию, в которой в данный момент времени находится головка соответствующей ленты. Рис. 8.17 соответствует тому, что?г = 2. Вторая и четвертая дорожки хранят содержимое первой и второй лент машины М, дорожка 1 хранит позицию головки на ленте 1, а дорожка 3 — позицию на ленте 2.
Для имитации перехода МТ М головка МТ У должна посетить 8 головочных маркеров. Чтобы не заблудиться", Л'должна помнить, сколько маркеров находятся слева от ее головки каждый раз; этот учет ведется с помощью компонента конечного управления Ф. После посещения каждого головочного маркера и запоминания обозреваемого символа в компоненте управления Л" знает, какие символы обозреваются каждой из головок М. Л' также знает состояние Лг, которое запоминается в конечном управлении Лг.
Таким образом, Л'знает, какой переход сделает М. Теперь Л" еще раз посещает каждый из головочных маркеров на своей ленте, изменяет символ в дорожке, представляющей соответствуют ленту, и при необходимости перемещает головочные маркеры влево или вправо. Наконец, Л' изменяет состояние И, записанное в конечном управлении Ф. В этот момент Лг проимитировала один переход М. 348 ГЛАВА 8. ВВедение В теорию мАшин тьюРинГА Риа 8.17.
Имитация доуллепточной Мрс помощью одиоленточпой В качестве допускающих состояний И выбираются все те ее состояния, в которых запомнено допускающее состояние М. Таким образом, как только имитируемая М допускает, %также допускает, и не допускает в противном случае. П Напоминание о конечности Обычное заблуждение — путать значение, конечное в каждый момент времени, с конечным множеством значений.
Конструкция сведения многих лент к одной помогает оценить разницу между этими "конечностями". В данной конструкции использованы дорожки на ленте для запоминания позиций ленточных головок. Почему нельзя записать эти позиции в виде целых чисел в конечное управление? Будучи небрежным, кто-то мог бы утверждать, что после и переходов головки МТ находятся в позициях, отличающихся не более, чем на и от начальной, и поэтому достаточно записать целые не больше и. Проблема состоит в том, что, хотя позиции конечны в каждый момент времени, все множество позиций может быть и бесконечным. Если состояние должно представлять любую позицию головки, то в состоянии должен быть компонент данных, имеющий любое целое в качестве значения.
Из-за этого компонента множество состояний должно быть бесконечным, даже если только конечное число состояний используется в любой конечный момент времени. Определение же машин Тьюринга требует, чтобы множество состояний бьшо конечным. Таким образом, запомнить позицию ленточной головки в конечном управлении нельзя.
8.4.3. Время работы и конструкция „много лент к одной" Здесь представлено понятие, которое в дальнейшем окажется чрезвычайно важным, а именно; "временная сложность", или "время работы" машины Тьюринга. Временем работы машины Тьюринга на входе щ называется число шагов, которые М совершает до 8.4. РАСШИРЕНИЯ БАЗОВОЙ МАШИНЫ ТЬЮРИНГА 349 останови Если М не останавливается на и, то время работы бесконечно.
Временная сложность МТ Месть функция 7(п), которая представляет собой максимум времени работы М на и по всем входам ж длины п. Для МТ, не останавливающихся на всех своих входах, 7(п) может быть бесконечным для некоторых или даже для всех л. Однако особое внимание будет уделено машинам Тьюринга, которые обязательно останавливаются на всех своих входах, и в частности, тем машинам, которые имеют полиномиальную временную сложность.
Они будут изучаться, начиная с раздела 10.! . Конструкция теоремы 8.9 кажется неуклюжей. Действительно, построенной одно- ленточной МТ может понадобится гораздо больше времени для работы, чем много- ленточной. Однако время работы этих двух машин соразмерно в том смысле, что время работы одноленточной МТ есть не более чем квадрат времени работы многоленточной, Хотя "возведение в квадрат" не является хорошей соразмерностью, оно сохраняет свойство времени работы быть полиномиальным. В главе 1О будут представлены следующие факты. 1.
Разница между полиномивльным временем и более высокими степенями его возрастания — это в действительности граница между тем, что можно решить с помошью компьютера, и тем, что практически нерешаемо. Несмотря на обширные исследования, время, необходимое для решения многих проблем, не удается определить точнее, чем "некоторое полиномиальное". Таким образом, когда изучается время, необходимое для решения некоторой проблемы, использование многоленточной или одноленточной МТ не явдяется критичным. Докажем, что время работы многоленточной МТ является не более чем квадратом времени работы одноленточной МТ.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
