Языки и трансляции. Мартыненко Б.К. - 98 стр.

UptoLike

ВУЗ: 

СПбГУ | Санкт-Петербург

Составители: 

Рубрика: 

97
Чтобы моделировать движение машины T
1
, машина T
2
должна посетить
каждую ячейку с маркером головки, регистрируя по очереди символ,
сканируемый соответствующей головкой T
1
. Когда машина T
2
проходит через
маркер головки, она должна уточнять направление, в котором следует искать
этот маркер. После сбора всей необходимой информации машина T
2
определяет
движение машины T
1
. Затем машина T
2
посещает по очереди каждый из
маркеров головок снова, изменяя маркированные ячейки и сдвигая маркеры на
одну ячейку, если необходимо. Конечно, если новое состояние является
принимающим, то машина T
2
принимает входную цепочку.
Пример 6.7. Посмотрим, насколько легче многоленточной машине
Тьюринга распознать язык L =
{ww
R
| w∈{0, 1}
*
}, чем одноленточной.
Чтобы распознать язык L на одноленточной машине Тьюринга, её головка
ленты должна двигаться вперед и назад по ленте, отмечая и сравнивая символы
с обоих концов. Это подобно процессу из примера 6.4.
Чтобы распознать язык L с помощью двухленточной машины Тьюринга,
входная цепочка копируется на вторую ленту. Затем цепочка на одной ленте
сравнивается с её копией на другой ленте в обратном порядке, и её длина
проверяется на чётность.
Заметим, что для распознавания языка L одноленточная машина делает
O(n
2
) движений, где n — длина входной цепочки, тогда как двухленточной
машине достаточно совершить только O(n) движений.
6.4.3. Недетерминированная машина Тьюринга есть устройство с
конечным управлением и одной бесконечной в обе стороны лентой. Для
данного состояния и ленточного символа, сканируемого головкой ленты,
машина имеет несколько вариантов для следующего движения. Каждый
вариант состоит из нового состояния, ленточного символа, который печатается,
и направления движения головки. Недетерминированная машина Тьюринга
принимает входную цепочку, если какая-нибудь последовательность вариантов
движений приводит к принимающему состоянию.
Теорема 6.3. Если язык L принимается недетерминированной машиной
Тьюринга T
1
, то он принимается некоторой детерминированной машиной
Тьюринга T
2
.
Доказательство. Для любого состояния и ленточного символа машины T
1
имеется конечное число вариантов для выбора следующего движения.
Варианты могут быть занумерованы числами 1, 2, ... . Пусть r — максимальное
число вариантов для любой пары (состояние — ленточный символ). Тогда
любая последовательность вариантов движений конечной длины может быть
представлена последовательностью цифр от 1 до r. Не все такие
последовательности могут представлять варианты движений, поскольку в
некоторых конфигурациях вариантов может быть меньше, чем r.
Можно построить детерминированную машину Тьюринга T
2
, моделирую-
щую машину T
1
. Снабдим её тремя лентами. Первая будет содержать входную
цепочку. На второй машина T
2
будет систематически генерировать последова-
тельность цифр от 1 до r. Конкретно, последовательности будут генерировать-

Страницы