Введение в дискретную математику - Яблонский С.В.
Скачать (прямая ссылка):
а) Операторы в схеме «работают» в определенной последовательности. В данный момент начипает работать тот оператор, перед которым стоит символ *.
б) Пусть мы имеем *Л. Тогда запись на ленте, состояние машины и положение головки на ленте, имеющиеся к данному моменту, преобразуются оператором А в некоторую запись на ленте, некоторое состояние машины и некоторое положение головки. После этого фрагмент схемы *Л перейдет в фрагмент А*, что означает, что преобразуется также и операторная схема.
в) Пусть мы имеем *р! (или *р|). В этом случае происходит вычисление предиката р по имеющейся записи на ленте и состоянию машины. В случае, если р=1, то фрагмент преобразуется в /?!*, т. е. мы перейдем к выполнению следующего оператора; если р = 0, то
#
фрагмент *р\ преобразуется в р|, т. е. выполняется далее оператор, к которому ведет стрелка.
Для *р[ — аналогичное правило, здесь р — трехзначный предикат, и в зависимости от его значения по соглашению происходит одна из трансформаций
=> р\ ** *р\ =? р1 *р\ -> р\-
ГЛ. 4. ВЫЧИСЛИМЫЕ ФУНКЦИИ
123
г) Сочетание *(о обозначает конец преобразований или окончание работы.
Пример 3. Рассмотрим операторную схему
П
ъАцрА^.
Пусти операторы Л0 и А, обозначают преобразования записи ленты, состояний и положения головки, осуществляемые соответственно машинами ©1« и ©її. Предположим, что состояния машин ©С и'©її не пересекаются. Пусть, наконец, р — р(х) — предикат, определенный па номерах ячеек (т. о. совокупности пар (а, х)), на которых машина ©1« останавливается. 'Гогда операторная схема осуществляет следующее преобразование.
1. Имеем *Л,). Работает маліина ©ї0 до останова (если он происходит) в ячейке с номером, скажем, ц. Схема перейдет в
1“
Л0 * рА^о.
2. Имеем *р. Вычисляется предикат р и:
а) если р — 1, то получаем схему
А0р *
б) если р = 0, то получаем схему
П
АцрА1 * «.
3. а) Имеем *А1ш Работает машина ©11. В случае останова машины ©11, приходим к схеме
П
АьрАх * ы.
б) Имеем *о). Преобразование закопчено. Преобразование, осуществляемое данной операторной схемой, является преобразованием, осуществляемым последовательным подключением машины ©^ к ©10 относительно предиката р(х).
Пример 4. Легко видеть, что операторная схема
Г 1 « А^т
\2\ Ч, I. ФУНКЦИОНАЛЬНЫЕ СИСТЕМЫ С ОПЕРАЦИЯМИ
ыижот интерпретироваться как схема, задающая преобразование, которое получается при итерации машины относительно предиката р.
Теперь перейдем к описанию технологии программирования для машин Тьюринга, т. е. к описанию метода построения программы машины Тьюрипга, осуществляющей заданное преобразование. Этот метод параллельно будет иллюстрироваться одним примером. Весь процесс программирования разбивается на четыре этапа.
/5 <г
А- .. А_______
1 ! !*! ': ж
\
И и
V
с-/ Рис. 5
начальный помет гихлчсчеюельньш момент
I этап. Пусть задано некоторое преобразование записи на ленте и положения головки. Допустим, что существует машина Тьюринга, осуществляющая это преобразование. Сначала из неформальных соображений составляют план осуществления данного преобразования. При этом стараются данное преобразование расчленить на более «простые преобразования», т. е. такие, для которых либо мы уже ранее построили машину Тьюринга, либо ее легко можно построить.
Пример 5. Пусть к = 2. Предположим, что требуется построить машину Тьюринга, которая осуществляет сдвиг массива из а +1 единиц (ос = 0, 1, ...) влево на Р + 1 ячеек С? = ...) (вне массива лента пустая).
Величину сдвига [1 + 1 можно задать путем специальной установки головки в начальный момент. На рис. 5 изображены записи на ленте и положение головки в начальный и в заключительный моменты. Требуемое преобразование можно осуществить так:
1) Отмечаем пачальпую ячейку путем замены в ней символа 0 на символ 1. Оператор для этого преобразования обозначим через Ф(0;-?-11). В скобках показало, что символ 0 заменяется на 1 и головка остается на месте.
2) Движемся вправо (оператор А4) до левой единицы массива.
ГЛ. 4. ВЫЧИСЛИМЫЕ ФУНКЦИИ
123
3) Обозначим через а и а" соответственно символ, обозреваемый в данный момент, и символ, расположенный непосредственно справа от а. Здесь а = 1. Выясняем, является ли единица, т. е. а', последней единицей в массиве, Для этого вычисляем предикат р{&\ а"), где
|0 ири а" = О,
Р(в-Я) = и при а" — 1,
В случае р~\
4) Стираем а (оператор 0(0).
5) Возвращаемся влево до ближайшей единицы (оператор у12).
0) Приписываем справа от этой единицы еще одну единицу. Обозначим через Ф(11->-111) соответствующее преобразованпе.
7) Возвращаемся (оператор р0, Ри — предикат, равный тождественно пулю) к
В случае р = О
8) Массив состоит из одной единицы. Производим О (а') — стирание единицы.
9) Возвращаемся влево (оператор А2) до ближайшей едипицы.
10) Движемся влево (оператор Ь) через массив из едипиц и останавливаемся над левой единицей.
II этап. Переход от составленного плана преобразования к операторной схеме.
Продолжение примера 5. В нашем случае операторная схема имеет вид
*Ф (04-> I4) | Агр (а'а")ГО (н') Л,Ф(1 +-+ П 1} р0у* О(н') ЛгЫ.
