Введение в дискретную математику - Яблонский С.В.
Скачать (прямая ссылка):
§ 3. Машинные коды и их преобразования
В дальнейшем мы будем рассматривать только машины, у которых входной алфавит состоит из двух символов.
Работа машины Тьюринга зависит от характера исходной записи на ленте. Далее чаще будут употребляться специальные виды этих записей, называемые машинными кодами. Здесь мы различаем два типа кодов: основные и вспомогательные.
Основные машинные коды имеют следующий вид:
...01. ..10..,
а+1
— массив пз а + 1 единиц;
... 01 ... 101 ... 10 ... 01 ... 10 ...
<^+1 «2+1 ал-Н
— 5 массивов из СС| + 1, а2 + 1, ..а* + 1 единиц соответ-
ственно, разделенных одним нулем.
Основные машинные коды предназначены для задания чисел а и наборов чисел а,, аг, ..а, из расширенного натурального ряда (множество, содержащее натуральные числа и нуль). Здесь кодом нуля является запись на ленте, имеющая ровно одну единицу.
С основными кодами связан ряд задач. Мы рассмотрим одну из них, относящуюся к нахождению левой единицы в основном коде. Более точно: требуется построить машину, которая для любого основного кода и любого начального положения головки преобразует основной код в себя (оставляет его на том же месте) и встает над левой единицей кода.
Дадим подробное решение этой задачи.
I этап. План работы искомой машины. Пусть исходная запись на ленте имеет вид ... а0а1а2 ...
1) Выясняем, не пуста ли начальная ячейка, т. е. проверяем условие р(а1 Ф 0).
б С. В. Яблонский
130 ч. I. ФУНКЦИОНАЛЬНЫЕ СИСТЕМЫ С ОПЕРАЦИЯМИ
2) Пусть р{а± ?= 0)~ 1, т. е. в начальный момент головка обозревает символ 1. Тогда отыскиваем левый конец (т. е. левую единицу) основного кода (оператор АД и останавливаемся.
3) Пусть р(й1=^0) — 0. Тогда выясняем, будет ли пустой ячейка, расположенная непосредственно слева от щ, т. е. проверяем условие р(й0 = 0).
4) Если р («о = 0) = 0, то возвращаемся к выполнению оператора А1т
5) Если р(ао = 0)=1, т. е. йо = 0, то символы а0, щ заменяем на две едипицы и останавливаемся над левой из них (оператор Ф (йой1~^ Таким образом, вне
основного кода построен сегмент, концами которого являются едипицы. Первоначально длина его равна двум, но в дальнейшем мы будем его увеличивать путем смещения левой единицы влево, а правой — вправо.
6) Выясняем возможность смещения левой единицы сегмента влево на одну ячейку путем проверки условия ?л, где
1, если непосредственно слева от сегмента находится пустая ячейка,
0 в противном случае.
Пусть рл = 1. Тогда:
7) Осуществляем смещение левой единицы на одну ячейку влево и затем движемся вправо до правой единицы сегмента (оператор Аг).
8) Выясняем возможность смещения правой едипицы сегмента на одну ячейку вправо путем проверки условия Рп, ГДе
1, если непосредственно справа от сегмента находптся пустая ячейка,
0 в противном случае. •.
Если ра — 1, ТО
9) Осуществляем смещение правой единицы на одну ячейку вправо и затем движение влево до левой единицы (оператор Ая) и возвращаемся к 6).
Если рл = 0, то
(10) Левая единица касается массива из единиц. Идем направо и стираем обе единицы сегмента. После этого возвращаемся влево до правого конца массива (оператор П4) и затем переходим к А%.
ГЛ. 4. ВЫЧИСЛИМЫЕ ФУНКЦИИ
131
Если рм~ 0, то
И) Правая единица касается массива из едипиц. Идем влево, стираем обе единицы сегмента. После этого возвращаемся вправо до левого конца массива (оператор Аъ) и затем останавливаемся.
Таблица 10
А, У.я ХЭ *4
0 0?х8 01Ы4 0 Пщ
1 1Ьх2 \Г.щ
7>(о0=П) х* хв
0 1 0/ж6
Ф У-7 хе
0 1 1 Нх8 НиХ8
V. Хщ
0 1 1 Ьу.\{\
А г у-ч «I!
0 1 1 Пу.п 0 Ну,^ 0Як12
Г'п Х,4
0 1 1 Ру.^х
XI!
0 1?И]5 01>.1С
1 0/Ж] <з
А* К.7 Х18 «18 «20
0 0/уХ2О
1 0Дх,„ • ОЬ'Хоц
А6 х2, х,г Хгз х2<
0 О/Лет 0У?х21
1 1 ?х22 0//Х^д Ойху
II этап. Запись операторной схемы. В нашем случае она имеет вид
III этап. Составление программ для отдельных операторов (см. табл. 10). Здесь программы для А3, А6 двойственны соответственно р.ъ А Е, А1т 6*
132 Ч. I. ФУНКЦИОНАЛЬНЫЕ СИСТЕМЫ С ОПЕРАЦИЯМИ
По операторной схеме в программам для операторов составляем программу рассматриваемой задачи (см. табл. 11).
IV этап. Производим упрощение программы. Команды, расположенные в столбцах х5, х7, Хи, х17, хм,
Таблица 11
р(п,=А0) А, р(а,,=0) Ф(од^д1-* 1*1)
«1 «» и» х4 Х| X, х» и*
0 1 05и6 15*2 0 Ях4 Пхг 0Дх4 0 ?хе 05х7 15я2 1Яхя 11хя 15н9
Рл 4, Рп А *
Х,д «и х„ у- і» «14 я,,
0 1 ІІЯіо 05 Хц 15х,7 0 Дх18 1 05хи 16х81 1?х1В 0/.х16 0?х1в І5хв
А ^6
X,* «г. ^20 «її «!* «»4
0 1 1/ІХі9 0Лх1е 0Лу.]6 0 ІУщ 16 хг 1/.И.Д 0?хгя О/.Хрд 0йхе4 0Яки
можно изъять, так как в них мы попадаем непосредственно из 05х6, 05х7, 15хр, 15х13, 15хі7, 15х21. После этого МОЖНО опустить СОСТОЯНИЯ Х5, Х7, Х9, Х,э, х17, хаі. Мы получаем программу с 18 состояниями (см. табл. 12)*).
В дальнейшем, как правило, построение программ будет доводиться до II этапа — составления операторных схем, так как оставшаяся часть работы трудностей не вызывает.
Пользуясь принципом двойственности, легко построить программу, позволяющую находить правую единицу основного кода. Несколько усложняя идею, можно построить
