Введение в дискретную математику - Яблонский С.В.
Скачать (прямая ссылка):
{F(а, щ), В, G(а, х,)}.
Эта тройка называется командой. Машина выполняет команду следующим образом: если головка обозревает на ленте символ а и машина к этому моменту находится в состоянии x.j, то в рассматриваемый момепт в ячейку вместо символа а записывается символ F(a, Xj), а машина переходит в состояние G(a, Xj) и передвигает головку 8*
110 ч. I. ФУНКЦИОНАЛЬНЫЕ СИСТЕМЫ С ОПЕРАЦИЯМИ
по ленте на одну ячейку вправо (Я). Если читаемым символом является символ Л, то в соответствующей клетке таблицы стоит «пустая» команда, что рассматривается как команда остановки машины. Очевидно, что программа машины полностью определяется каноническими уравнениями для <р(я).
Т а б л п ц а I
*х кі хг
Л
0
а {Л Я, Сі
N - 1
Данный тип машин можно обобщить, допуская более широкий класс программ и более сложное взаимодействие автомата с лентой.
Так, приведенная на рис. 3 машина (обозначим ее через 2Л) состоит из бесконечной (но уже в обе сторо-
-I
-10 1 t
і
Рис. 3
ны) ленты и автомата (см. рис. 3). Ячейки ленты нумеруются целыми числами ..., —I, ..., —1, 0, 1, I, в ячейки вписываются символы из алфавита (0, 1, ...
1) (Он дальнейшем будет играть также роль пустого символа); автомат обладает головкой, способной
ГЛ. 4. ВЫЧИСЛИМЫЕ ФУНКЦИИ
117
совершать один из актов: Я — сдвигаться на одну ячейку вправо, Ь — сдвигаться на одну ячейку влево и 5 — продолжать обозревать ту же ячейку. Символы яь ..яг обозначают состояния автомата. Работа машины характеризуется программой Т (см. табл. 2). В пей часть клеток может быть незаполненной, т. е. содержать пустые
Таблица 2
*1 X,
0
. . . ? * * ? • •
а
? • *
к — 1
команды, а остальная часть заполняется тройками символов, представляющими команды машины. Например, в клетку, расположенную в строке с номером а и ;-м столбце (см. табл. 2), вписана тройка с ?>я. В команде: с —символ из алфавита (0, 1, к — 1}, Б— символ из алфавита (Я, Я, ?} им — одно из состояний (я,, ..., яЛ.
Пусть головка машины обозревает символ а, находясь в состоянии я.,-, тогда:
а) если в клетке (а, Я;) находится комапда (с?>я), то машипа заменит в этой ячейке символ са на с, перейдет в состояние я, осуществит движение О и приступит к выполнению следующей команды;
б) если в клетке (а, я^) стоит пустая команда, машина останавливается.
В начальный момент головка установлена над некоторой ячейкой ленты (начальной ячейкой) и машина находится в состоянии ях (соответствующем левому столбцу программы Т).
Таким образом, машина, начиная из исходной ситуации (начального состояния и печальной ячейки), осуществляет переработку исходной записи на лепте в соответ-
118 Ч. I. ФУНКЦИОНАЛЬНЫЕ СИСТЕМЫ С ОПЕРАЦИЯМИ
ствии с программой Т. Имеются две возможности: а) при работе машины появится пустая комапда — машина останавливается н мы получаем заключительную запись на ленте (состояния, в которых машина останавливается,
Т а б л и 1 а 3 будем называть заключительными); ц б) при работе машины пустая команда
не появится — машина не остановится.
Введенные нами машины называются машинами Тьюринга.
II р и мер 1. Пусть к ~ 2. Рассмотрим машину, которая в произвольной записи, начиная из любой ячейки, двигаясь вправо, находит первый нуль. Очевидно, она может быть задана программой, записанной в табл. 3.
В самом деле, возможны три случая.
1) В начальный момент головка видит символ 0. Машина сразу останавливается.
2) В начальный момент головка видит символ 1 и справа от начальной ячейки запись содержит хотя бы
один 0. Машина переместит | головку через массив из еди-
II ~ ниц вправо и остановится
над первым нулем.
Гис* 4 3) В начальный момент
головка видит символ 1 и справа от начальной ячейки запись состоит сплошь из единиц. Машина будет перемещать головку через массив единиц вправо, не останавливаясь.
Теперь введем, ряд обозначений и понятий, связанных с записью на лепте. Будем изображать при помощи стрелки положение головки на ленте в рассматриваемый момент времепи (см. рис.. 4).
То же можно записать еще и так:
4
* * ? * ? *
Здесь стрелка относится к символу щ, расположенному непосредственно деЕее стрелки, и обозначает, что головка в данный момент обозревает символ а±.
Если лепта заполпена сплошь нулями, то иногда будем говорить, что мы имеем пустую ленту. Для ячейки,
XI
0
1
ГЛ. 4. ВЫЧИСЛИМЫЕ ФУНКЦИИ
119
в которой записан символ 0, будет употребляться также термин пустая ячейка.
Наконец, совокупность ячеек, которые посетит головка, двигаясь из начальной ячейки до данного момента I, называется рабочей зоной ленты в момент времени Ь.
В дальнейшем нам придется строить машины Тыорипга, обладающие опре- Таблица 4 деленными специфическими свойствами. При этом удобно строить машины, исходя из уже построенных машин.
Для этого мы введем принцип двойственности и два типа композиции машин.
Принцип двойственности для программ (машин). Пусть Т — произвольная программа. Обозначим через Т* программу, которая получается из Т, если всюду в Т заменить в командах Я на Ь и Ь на Л. Программа Т* называется двойственной к Т.
