С.В. Яблонский - Введение в дискретную математику (1060464), страница 21
Текст из файла (страница 21)
Поэтому первый столбец программы может быть заменен на следующий (см. табл. 8). После этого можно отождествить состояния и, и х„так как в ячейках (1, х,) и (О, х,) стоят пустые комапды и в нпх машина никогда не попадает. Аналогичное преобразоваппо можно проделать со столбцамн для х, и х,: изъять команду 1Лх, п отождествить состояния х, и х,. Наконец, в столбце х„ команда ОЯх, никогда не работает н ве ьюжпо изъять, а 18х4 монсно клетки, в которые машина никогда не попадает. Пусть для каждой строки существует пустая клетка данного вида (по крайней мере в одном из указанных столбцов).
Легко видеть, что тогда мол<но состояния х' и х" отождествить. Другой тип упрощений связан с операторами проверки логических условий. Мы поясним его на нашем примерв. Продолжение примера 5. Состояния х, и х, связаны с командами, которые осуществляют только пе- реходы к другим состояниям. Их мож- Т а б л и ц а Н но исключить, скорректировав коман- ды для х,.
Х4 Кще одна возмо>кность упрощений связана с командами, содержащими символ движения Я. Пусть в клетке 1лх4 (с, х) находится команда с'Рх'. Тогда, если к атой команде можно непосредственно перейти только от команд сЯх, и она не работает в начальный момент, то команду с'Рх' в клетке (с, х) можно изъять, а все команды сЯх заменить на с'Рх'. Продолжение примера 5. В программе из табл. 7 к команде 18х4, находящейся в клетке (1, х,), можно непосредственно попасть только нз команды 1Ях, !29 гл. 4. Вычислимые Функции также изъять, внеся необходимые изменения в столбец для н„.
Мы приходим к программе (см. табл. 9), содержащей 10 состояний. $ 3. Машинные коды и пх преобразования В дальнейшем мы будем рассматривать только машины, у которых входной алфавит состоит из двух символов. Работа машины Тьюринга зависит от характера исходной записи на ленте. Далее чаще будут употребляться специальные виды этих записей, называемые машинными кодами. Здесь мы различаем два типа кодов: основные и вспомогательные. Основные машинные коды имеют следующий вид: ...О!...10.. а+! — массив из а + 1 едннпц; ...О! ...101...10...01...10.. ау+5 а Еу а,+5 — з массивов из и, + 1, с5а + 1, .
„ а, + 1 единиц соответственно, разделенных одним нулем. Основные машинные коды предназначены для задания чисел а и набоРов чисел ссь с5ь ..., тх, из РасшиРенного натурального ряда (множество, содержащее натуральные числа и нуль). Здесь кодом нуля явллется запись на ленте, имеющая ровно одну едпницу. С основными кодами связан ряд аадач. Мы рассмотрим одну из них, относящуюся к нахождению левой единицы в основном коде. Более точно: требуется построить машину, которая для любого основного кода н любого начального положения головки преобразует основной код в себя (оставляет его на том же месте) и встает над левой единицей кода. Дадим подробное решение этой задачи.
1 этап. План работы искомой машины. Пусть исходная закист, ва лепте имеет впд ... а,а, а, ... 5 1) Выясняем, не пуста ли начальная ячейка, т. е. провернем условие р(а, ч" 0). 5 Ваеиеиие а еиекуетную математику 13о ч. 1. ФункцпонАльные с!!степы с опеРАцпямп 2 ) Пусть р(а, чАО)=1, т. е. в начальный ьщмент головка обозревает символ 1.
Тогда отыскиваем левый конец (т. е. левую единицу) основного кода (олератор А) и останавливаемся. 3) Пусть р(а,чьО)=0. Тогда выясняем, будет ли пустой ячейка, расположенная непосредственно слева от ао т. е. проверяем условие р(а, = 0). 4) Если р(а, = 0) = О, то возвращаемся к выполнению оператора Аь 5) Если р(ао= 0)= 1, т. е. а. = О, то символы а„а, заменяем на две единицы и останавливаемся над левой из них (оператор Ф(азв1-+.1 1)). Таким образом, вне У 1 ! основного кода построен сегмент, концами которого являются единицы.
Первоначально длина его равна двум, но в дальнейшем мы будем его увеличивать путем смещения левой единицы влево, а правой — вправо. 6) Выясняем возможность смещения левой единицы сегмента влево на одну ячейку путем проверки условия рл, где 1, если непосредственно слева от сегмента находится пустая ячейка, Ра 0 в противном случае. Пусть рл 1.
Тогда: 7) Осуществляем смещение левой единицы на одну ячейку влево и затем движемся вправо до правой единицы сегмента (оператор А,). 8) Выясняем возможность смещения правой единицы сегмента на одну ячейку вправо путем проверки условия р„где 1, если непосредственно справа от сегмента находится пустая ячейка, 0 в противном случае.
Если р.=1, то 9) Осуществляем смещение правой единицы на одну ячейку вправо и ватем движение влево до левой единицы (оператор А,) и возвращаемся к 6). Если рл О, то (10) Левая единица касается массива из единиц. Идем направо и стираем обе единицы сегмента. После этого возвращаемся влево до правого конца массива (оператор А1) и затем переходим к А,.
гл. ь Вычислимые Функции Табл ппа 10 вмав=п] р(а,вв01 хв х, Обх ОВхв 0 Обмв 1ьх, ОВх, 1Т,хв хх х„ х, ОВх,в 1Вхп ОВн, 0 1Вхв 1в™в 1бхвв рп х„ х„ х„ Оьхвв 1Гзхм 11ахвв 1лх„ хвв вьг хвв ОВхв, ОЕмвв 1бми П эта п. Запись операторной слепы. В нашем случае она имеет вид 1 4 1 аР(ав ~ 0) 1 Авва Р (ав ~) 1Ф (ава1 х ) Ра 1 ~вРа1 вРв влвРв 1 А ва 1П этап. Составление программ для отдельных операторов (см. табл. 10). Здесь программы для р„А„А, двойствеины соответственно рл, Ав, Ав.
Если р,=О, то 11) Правая единица касается массива из единиц. Идем влево, стираем обе единицы сегмента. После этого возвращаемся вправо до левого конца массива (оператор А,) и затем останавливаемся. ~З2 ч. ь фгпкцпоплльпык спсткмы с опю лцпямп По операторпой схеме и программам для операторов составляем программу рассматриваемой задачи (см. табл. 11). 1Ч з т а п. Производим упрощение программы. Команды, расположенные в столбцах х„х„х„хм, хоч хм, Таблица И Ф(ае~ъ 1~1) иы„-ю и<а,:из~ О ОЮ $15 можно изъять, так как в ппх мы попадаем кепосредствепно из ОЯхь ОЯхп 15хь 18хо, 18хп, 18х21 После этого мол~но опустить состояния х„х„х,, хио хго и„. з)ы получаем программу с 18 состояниями (см.
табл. 12)*). В дальнейшем, как правило, построение программ будет доводиться до 11 этапа — составлеппя операторных схем, так как оставшаяся часть работы трудностей не вызывает. Пользуясь принципом двойствепности, легко построить программу, позволяющую находить правую единицу осиовиого кода. Несколько усложпяя идею, можно построить и) В вей можно отождествить и< в их Гл. ь Вычислимые Функции программы для нахождения правой нли левой единицы 1-го массива основного кода. Определение.
Решеткой с шагом 1 (1>2), называется последовательность ячеек ленты, номера которых сравнимы по модулю й Всего имеется 1 решеток с шагом й Таблвцв 12 Лемма 1 (о моделпрованки на ре|петке). Пусть у)1 — произвольная мишина Тьнрннси с прогрокмой Т .и Ю вЂ” произвольное целое число (Е- 2). Тогда ложно состроить маисинр Й, которая на решетке с шагом 1 работает так же, как исходная маишнв !Я на всей ленте, Дока ветел ьство. 11о таблице Т (см. табл.
13) строим таблицу Т, в которой к ка;кдому состоянию х, 1 1-1 добавлены вспомогательные состояния х,г ..., х> х;, ..., х,', предназначенные для прохождения ячеек вне решетки и запоминания характера движения (см. табл. 14), где х; при Р=Я, х~ = х, при,Р П, и хг при Р Р. Иа данной таблицы видно, что машина й, находясь в ячейке решетки и обозревая символ а в состоянии хь заменяет, как и машина йя', символ а на с, совершает то же движение Р и переходит в состояние х; .
Состояние 'о р х> зависит от характера движения: это будет х, прн Р Б, х~ при Р гг и к; прп Р=Ь. В последних !В4 ч. ь инкцпонлльныв спствмы с опггэлппямп двух случаях головка машины сходит с решетки и далее 1 т 1-1 при движении вправо проходит состояния нз, н;... н; ! !+1 ау-а а при движении влево — состояниями х;, ..., х; Затем головка попадает на решетку в состоянии кь сместившись по решетке на одну ячейку. Таким образом, в случае движения В и Ь машина ак делает на решетке Табл лпа !3 то же самое, что и мапшна Й на всей ленте, но за ! шагов. Следствия. 1) Если С,(а)=а при а=О, ..., к — 1 и любом 1, то машина Й вне решетки не меняет записи ленты.
2) Если С,(о) О при а О, ..., 1с — 1 и любом 1, то маишна Й в пределах рабочей зоны производит очистку ленты. 3) Коли С,(а) 1 при а=О, ..., й — 1 и любом 1, то машина И в пределах рабочей зопы ставит 1, тем самы.ч отмечает те ячейки вне решетки, в которых побывала еоловка. 4) Возможны смешанные ситуации, например, С,(а) ° С„,(а) 1 при а О, ..., )с — 1 и С~(а)=а в остальных случаях.
В этаж случае машина ач ставит 1 в преде,лах рабочей зоны на соседней решетке, являющейся сдвигом исходной решетки на единицу вправо, и не меняет содержимого ленты вне этих двух решеток, 13а ч. ь ФункцпонАльные системы с опвэлцпям>1 Введем следующее обозначение. Если А есть некоторое преобразование на ленте, то Л будет обозначать оператор, моделирующий А на некоторой решетке (его поведение вне решетки будет специально уточняться).
Перейдем теперь к описанию вспомогательных кодов. Мы различаем три вида вспомогательных кадое, ссссо сгиба Рис. 6 а) 1-зратный код определяется для произвольного набора ао а„..., и, чисел из расширенного натурального ряда следующим образом: ...01...101...1У...У1...10..., >(а>+0 >(аз+0 >(ас.») где П вЂ” буферное слово длпны 1 и 0= 0(>", т, е. Ь> начинается с нуля; б) решетчатый код определяется для произвольного набора >хо а„ ..., >х, чисел из расширенного натурального ряда. Это запись на ленте, котору>о >кожно разложить с помощью в решеток (последовательностей ячеек ленты), имеющих период и, на массивы из единиц, а именно: иа первой решетке расположен массив из а, + 1 единиц, на второй решетке расположен массив из с>>+1 единиц и т. д., на з-й решетке расположен массив иа а.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
