Научная литература
booksshare.net -> Добавить материал -> Математика -> Яблонский С.В. -> "Введение в дискретную математику " -> 40

Введение в дискретную математику - Яблонский С.В.

Яблонский С.В. Введение в дискретную математику — Наука , 1986. — 384 c.
Скачать (прямая ссылка): vvedenievdiskretnuyum1986.djvu
Предыдущая << 1 .. 34 35 36 37 38 39 < 40 > 41 42 43 44 45 46 .. 104 >> Следующая

Таким образом, работу машины можно описать более точно:
1) выходим на правый конец основного кода (оператор Я);
2) отступая две клетки вправо, выписываем массив из I единиц. Данное преобразование обозначим через Ф -*? -?а001 ... 1*);
* i ”
3) возвращаемся на левый конец основного кода (оператор L);
4) просматривая первые три символа а'а"ат с левого конца основного кода (а в последующем — в оставшейся части основного кода), вычисляем трехзначныи преди-
/ / tr *** \
кат р(а , а , а ).
Если а'а" а'" = 11а“', то имеем I режим и переходим к преобразованию, которое указывается стрелкой t (р1).
Если а'а'/а"' = 101, то имеем II режим и переходим к оператору, следующему за р.
Если а'а"а'"*= 100, то имеем III режим и переходим к преобразованию, коюрое указывается стрелкой i (р,).
1'!Я Ч. І. ФУНКЦИОНАЛЬНЫЕ СИСТЕМЫ С ОПЕРАЦИЯМИ
I режим.
5) Стираем симіюл аг (оператор 0(а'))';
6) Выходим на правый конец слова (оператор Л);
7) Пристраиваем непосредственно справа от слова
массив из I единиц (оператор Ф (я* -*? а 1 . .. 1*));
. -
8) Возвращаемся на левый конец слова (оператор Ь) и переходим к 4).
II р ежим (первый символ а' — последний в массиве единиц основного кода, но имеется по крайней мере один не обработанный массив из единиц в основном коде),
9) Стираем символ а (0(а'));
10) Выходим на правый конец слова (оператор Л);
11) Пристраиваем непосредственно справа от слона буферное слово и и еще I единиц (оператор Ф (я^ ->?
аи 1 Л . И));
' 1
12) Возвращаемся на левый конец слова (оператор Ь) и переходим к 4).
III режим (первый символ а' является последним в основном коде).
13) Стираем символ а' (О(я'));
14) Двигаясь вправо, выходим на левый конец построенного /-кратного кода и останавливаемся.
II этап. Мы получаем следующую операторную схему:
Реализация операторов этой схемы не вызывает затруднений и по схеме легко может быть построена программа машины.. Лемма доказана.
Лемма 3 (о преобразовании решетчатого кода в основной) . Пусть $ — натуральное число, 5^2. Тогда можно построить машину Тьюринга, которая преобразует произвольный решетчатый код с параметром з в соответствующий основной код,
ГЛ. 4. ВЫЧИСЛИМЫЕ ФУНКЦИИ 139
Доказательство. I этап. Сначала опишем идею работы машины. Обозревая в начальный момент левую единицу решетчатого кода, машина отступает далее влево на определенное расстояние и постепенно справа налево формирует там основной код путем «перетаскивания» кодов с решеток, начиная с s-й и кончая 1-й решеткой (c-м. рис. 7).
5
1... 101 ... 10...01... fldi?f ...
ч--------v------------------ .V-v--
оснидксй код решетчатый код
Гис. 7
Более точно преобразование можно характеризовать так: разобьем его на последовательность более простых преобразований
* А „Л, ...Ai м.
Преобразование А0 (предварительная подготовка ленты). 1) Отступаем от начальной ячейки (левая единица решетчатого кода) влево на s ячеек (оператор ^1)*).
2) Непосредственно слева за этим промежутком вписываем единицу (оператор Ф(а1На)). Преобразование закончено.
Преобразование Л, («перетаскивание» массива единиц с s-n решетки). 1) От ячейки, в которой оператор Л о поставил 1, смещаемся вправо на 2s ячеек (оператор R\*). Мы попадаем па левый конец массива, расположенного па s-й решетке. Пусть а', а" — первые два символа на s-й решетке (а7 —левый конец).
2) Выясняем, является ли а одновременно и правым концом кода путем вычисления предиката а")
(с возвращением к а') :
}{а’3 а") -
!0 цри а" = 0 (а/ — правый конец массива)',
1 при а" = 1 {а' — не есть правый конец массива).
*) В решетчатом коде подряд может стоять s — 1 пулей.
140 ч. I- ФУНКЦИОНАЛЬНЫЕ СИСТЕМЫ С ОПЕРАЦИЯМИ
Если р = 1 (а' — не правый конец массива па 5-й решетке), то:
3) Движемся до правого конца массива на этой решетке (оператор Я).
4) Стираем последний символ а в массиве (оператор 0(а)).
5) Возвращаемся на левый копец массива (оператор Г).
6) Смещаемся влево еще на 2$ ячеек (оператор Р'і) — мы попадаем на правый конец основного кода (вернее — построенного куска основного кода) .
7) Выходим на левый копец основного кода (оператор Ь).
8) Приписываем слева к основному коду символ 1 (оператор Ф (й1 1;д)).
9) Возвращаемся на правый конец основного кода (оператор Л), после чего переходим к 1).
Если р = 0 (а — правый конец массива на 5-й решетке), то:
10) Стираем символ а' (оператор 0(а'))\
11) Смещаемся влево на 2з ячеек (оператор ЛГХ мы попадаем на правый конец основного кода.
12) Выходим на левый конец основного кода (оператор Л).
13) Приписываем слева к основному, коду символы 10 (оператор Ф(а; -*? НОй)),
14) Возвращаемся на правый конец основного кода (Л).
Преобразование закончено.
Преобразование А{ (1<Кі| («перетаскивание» массива единиц с і-п решетки). Выполняется так
же, как и А і с заменой операторов Щ* и Ь\* соответственно на И\+і и 1\+ *4 что обеспечивает попадание на І-ю решетку.
Преобразова ние А1 («перетаскивание» массива единиц с 1-й решетки). Выполняется так же, как и А, с заменой операторов и соответственно на Щ+1 и Ц*1 и изъятием операторов Ф(аі-»-110а) и Л (см. п.п. 13) и 14)), поскольку э,ти операторы осуществляют подготовку к следующему преобразованию, а А і является последним.
Предыдущая << 1 .. 34 35 36 37 38 39 < 40 > 41 42 43 44 45 46 .. 104 >> Следующая

Реклама

c1c0fc952cf0704ad12d6af2ad3bf47e03017fed

Есть, чем поделиться? Отправьте
материал
нам
Авторские права © 2009 BooksShare.
Все права защищены.
Rambler's Top100

c1c0fc952cf0704ad12d6af2ad3bf47e03017fed