Введение в дискретную математику - Яблонский С.В.
Скачать (прямая ссылка):
Пример 2. Программа Т*, задаваемая табл. 4, очевидно, будет двойственной к программе Т из предыдущего примера.
Очевидно, что (71*)* = 77, т. е. понятие двойственности программ является взаимным. В последующем мы будем также машины 2Я и 2Я*, соответствующие программам Т и Т*, называть двойственными машинами. Легко видеть, что двойственные машины ЗЯ и ЙЯ* в некотором смысле функционируют симметричным образом, а именно: если в начальный момент на ленте имеется запись
I
... йг аг ... (1)
и машина ЙЯ в момент I ее переработала в запись
I
С3 ... Се , (2)
щ
0
1
то машнна ЙЯ* запись
(3)
имеющуюся в начальный момепт и симметричную (1)
1;Ч> 4.1. ФУ П1 ЩИ ОН А Л ЬпЫЕ СИСТЕМЫ С ОПЕРАЦИЯМИ
относительно аи перерабатывает в момент I в запись
*
,.. с* ... с2сг .. .л (4)
симметричную (2) относительно С(.
Например, программа Т* (см. пример 2) в силу этого замечания должна, двигаясь влево, отыскивать первый нуль, в чем также можно убедиться непосредственной проверкой.
1-Й тип композиции — последовательное подключение одной машины к другой. Пусть Ш10 и — две
Таблица 5
К| ^ » •*» > ^г0 Г Г г *1 Х7И * * *Г,
0 а к — 1
произвольные машины Тьюринга над одним и тем же 'входным алфавитом (0, — 1}, множества состояний
которых не пересекаются. Перенумеруем числами 0, 1, 2, ..., / — 1 все пустые клетки (команды) программы Т„ машины 5Ш0- Пусть р(х)—произвольный предикат*) на множестве (0, 1, 2, ..., /—1). Построим машину которую и будем называть последовательным подключением машины 2И, к (относительно предиката р{#)). Для этого из таблиц Д в ^ машин 2й0 и 3^1 построим новую таблицу Т (см. табл. 5). В ней первая половина совпадает с таблицей Г0 для тех клеток из Т0, в которых стоит непустая команда. В тех клетках Ц, для которых р(г])=1, в таблице Т стоит команда о,8'лх (где а — номер строки, в которой находится эта клетка ц, а *1 — начальное состояние машины З^). 13 тех клетках ц, для которых р(ц)=0, в таблице Т стоит также пустая команда. Вторая половина таблицы Т полностью совпадает с таблицей Ти
*) Предикат р(лг) на {0, 1, ..., I — 1} — специальная функция из Рь В дальнейшем встречаются двухзначные и трехзначные предикаты. Они соответственно принимают значения из множеств (О, 1} в {0, 1, 2},
ГЛ. 4, ВЫЧИСЛИМЫЕ ФУНКЦИИ
121
Очевидно, что работа машины 5Ш состоит в следующем: исходная запись ленты сначала перерабатывается машиной 2Я0, и если машина Ш10 заканчивает работу иа команде г] такой, что р(г|)=1, то содержимое ленты перерабатывается машиной 2^. При этом начальной ячейкой для машины Sfti будет ячейка, в которой остановилась машина Таким образом, машина Ш в некотором смысле осуществляет последовательную работу машин 2?0 и 5Pit.
2-й тип композиции — итерация машины. Пусть ЙЯ„— произвольная машина Тыорипга и числами 0, 1, 2, ».1—1 занумерованы пустые клетки ее программы Т0. Пусть р (я) — произвольный предикат иа множество (О, 1, 2, ..I— 1). Построим машину 9Я, которую будем называть итерацией машины 2Яи относительно предиката р[х). Для зтого по таблице Т0 построим таблицу Т машины Ш. Таблица Т совпадает с Т0 вне клеток, являющихся пустыми для Гс. В тех клетках г\ таблицы Г01 для которых р(ц) = 0, в таблице Т стоит команда aS%i (где а — номер строки, в которой находится эта клетка ц, а X, — начальное состояние машины 2Яй). В клетках ц таблицы Т0, для которых р(ц)=1, в таблице Т стоит также пустая команда.
Легко видеть, что машина Ш в определенном смысле является итерацией машины 5Ш0, т. е. ее работа эквивалентна многократной работе машины 5й0.
§ 2. Один метод построения машин Тьюринга
Здесь будет описан способ построения машин Тьюринга, который использует композиции машин и специальный операторный язык для записи алгоритмов. Этот язык впервые был предложен А. А. Ляпуновым в 1953 г. (см. [21]). Поскольку сам язык носит вспомогательный характер, то не имеет смысла давать его строгое формально-логическое определение. Мы остановимся лишь на кратком описании операторного языка и рассмотрим серию примеров.
1. Исходными объектами являются операторы, которые подразделяются на три группы:
а) операторы, осуществляющие преобразование записи ленты, состояний машины и перемещение головки машины. Эти операторы обозначаются заглавными латинскими буквами Л} В, (иногда снабженными индексами);
122 Ч, I. ФУНКЦИОНАЛЬНЫЕ СИСТЕМЫ С ОПЕРАЦИЯМИ
б) операторы проверки логических условий, обозначаемые символами р\ или р\ и иногда снабженные индексами;
и) специальные операторы, обозначаемые символами
* И (й.
2. Из операторов по определенным правилам строятся операторные схемы. Операторная схема представляет собой некоторую последовательность операторов, в которой для всех стрелок в операторах проверки логических условий указаны операторы, к которым эти стрелки ведут. Например, выражение
П
*Л{)рА{о
будет операторной схемой.
3. Каждой операторной схеме сопоставляется некоторый алгоритм, характеризующий преобразование записи ленты, состояний машины и перемещение головки машины. Последние осуществляются при помощи следующих правил.
