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

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

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

*) В ней МОЖНО отождествить К* в Яа*.
ГЛ. 4. ВЫЧИСЛИМЫЕ ФУНКЦИИ
133
программы для нахождения правой или левой единицы ^го массива основного кода.
Определение. Решеткой с шагом I (?^2), называется последовательность ячеек ленты, номера которых сравнимы по модулю I. Всего имеется I решеток с шагом I.
Таблица 12
«1 я. я* я. я, я,0 Яц х1г
0 1 0 ?хе 15я2 0?Хд 1?х2 1 ?х2 1 Пщ 15ка 1?х8 1/^и 0Лси ПГх. < 1Яхи 0/?х12 0Ях12 1Лхи
Яч «15 я.« *10 У-м яг0 я32 я„ Яг«
0 1 ОД И] 6 1 ?*22 1/^15 0//Я) ^ 0/,я|е 1 />/чи 0 Еу.п 0?х2(| 0 ?хг0 16’х2 0 ?хи 0?х23 0Лх2,
Лемма 1 (о моделировании на решетке). Пусть Ш — произвольная машина Тьюринга с программой Т и I — произвольное целое число (1^2). Тогда можно построить машину Ш?, которая на решетке с шагом I работает так же, как исходная машина йй на всей ленте.
Доказательство. По таблице Т (см. табл. 13) строим таблицу Т, в которой к каждому состоянию У) добавлены вспомогательные состояния к], . предназначенные для прохождения ячеек
вне решетки и запоминания характера движения (см. табл. 14), где
щ при О = 5,
у] при В — Пщ
у] при В = Ь.
Из данной таблицы видно, что машина 2Я, находясь
в ячейке решетки и обозревая символ а в состоянии у{, заменяет, как и машина ЙЯ, символ а на с, совершает то
же движение В и переходит в состояние х?, Состояние и -
Уз зависит от характера движения: это будет щ при
В = 5, к] при В — Я и я] при О = Ь, В последних
134 Ч. I. ФУНКЦИОНАЛЬНЫЕ СИСТЕМЫ С ОПЕРАЦИЯМИ
двух случаях головка машины сходит с решетки и далее при движении вправо проходит СОСТОЯПИЯ V.}, Х],. . У.) *
1 »,/ +1 .2/—2 о
а при движении влево — состоянияИ;} , ...,Уц . 5а-
тем головка попадает на решетку в состоянии щ, сместившись по решетке на одну ячейку. Таким образом, в случае движепия В и В машина 991 делает на решетке
Таблица 13
*1 *1 К Лг
0

а г-Оя^

к — 1
то же самое, что и машина па всей лепте, но за I шагов.
Следствия. 1) Если С^[а)^а при а — 0, к— 1 и любом /, то машина 9Й вне решет ни не меняет записи ленты.
2) Если Сз(а) = 0 при а = 0, ..., к — 1 и любом ]', то машина Ш1 в пределах рабочей зоны производит очистку лепты.
3) Если 1 при а = 0, ..., к— 1 и любом /, то
машина 9Л в пределах рабочей зоны ставит 1, тем самым отмечает те ячейки вне решетки, в которых побывала головка.
4) Возможны смешанные ситуации, например, СЛ{а}~ ~Е21~2(а)= 1 яд« а = 0, ..., А’— 1 и С;(а) = а в остальных случаях. В этом случае машина 2)1 ставит 1 в пределах рабочей зоны на соседней решетке, являющейся сдвигом исходной решетки на единицу вправо, и не меняет содержимого ленты вне этих двух решеток.
Таблица 14
-5 *} 1 х^
0 С,(0) Ях] с9(0) Ях? ^г—1^) С,( 0) ?я|+1 с2г_2(0) ^



а сОхП С» Лх? С,(в) Лх? б^_-|(о) Ях^ С,(а) Ц+> ^2(—а(®) ^
* * ^

к — 1 С,(*г - 1) Як? С2(/с - 1) Ля? С(_](А—-1) Ях_, С((Л—1) ?х^+1 С2г_2(^-1)

136
Ч. I. ФУНКЦИОНАЛЬНЫЕ СИСТЕМЫ С ОПЕРАЦИЯМИ
Введем следующее обозначение. Если А есть некоторое преобразование на ленте, то А будет обозначать оператор, моделирующий А на некоторой решетке (его поведение вне решетки будет специально уточняться).
Перейдем теперь к описанию вспомогательных кодов. Мы различаем три вида вспомогательных кодов.
[?>
т-
Й-

?1-я решетна є миссивон из аг +1 единиц
2-я решетка с пассивом иг а2^1 единиц
3-я ре а вс?на с массивен из в.$+7единиц
Рис. 0
а) ^-кратный код определяется для произвольного набора сц, аг, ..., а. чисел из расширенного натурального ряда следующим образом:
...01...1171...117 ...1Т 1_-Л0 ...,
1(01+1)" Ч«2+1Г
где и — буферное слово длины I и II = 011', т. е. II начинается с нуля;
б) решетчатый код определяется для произвольного набора 0ц, аг, ..а, чисел из расширенного натурального ряда. Это запись на ленте, которую можно разложить с помощью « решеток (последовательностей ячеек ленты), имеющих период 5, на массивы из единиц, а именно: на первой решетке расположен массив из сц 4-1 единиц, на второй решетке расположен массив из а2 + 1 единиц и т. д., на 5-й решетке расположен массив из сц +1 единиц и начала этих массивов согласованы, т. е. идут на ленте подряд в соответствии с номерами решеток (см. рис. 6; на данном рисунке для наглядности каждая решетка изображена отдельно);
в) квазиосновной код определяется для произвольного ОСНОВНОГО кода где Ь1 = &у— 1, в виде следу-
ющей записи:
ь1и1ьги2...их-1к,
где
\иг\ =,..-1^1 =1-1 (1> 2),
ГЛ. 4. ВЫЧИСЛИМЫЕ ФУНКЦИИ
137
Таким образом, в квазиосновном коде на решетке с шагом I расположен основной код, внутренние промежутки заполнены словами Uu Иг, ..(7V~1, а остальная часть ленты — пустая.
С машинными кодами и их преобразованиями связан ряд лемм.
Лемма 2 (о преобразовании основного кода в i-кратный код). Пусть I — натуральное число (i?® 2). Тогда можно построить машину Тьюринга, преобразующую основной код в соответствующий l-кратный с некоторым заданным буферным словом U, где \U\=l и U 0?/'.
Доказательство. I этап. Искомая машина будет постепенно на ленте правее основного кода строить i-кратный код. Для этого просматриваются слева направо символы основного кода и каждый символ основного кода на некотором шаге заменяется нулем, а справа пристраивается либо массив из I единиц, если в основном коде была 1, либо слово U, если в основном коде был 0. В процессе этого построения на ленте будет появляться слово, в котором между двумя соседними единицами не может стоять более I нулей. Для таких слов можно (как для основных кодов) построить машину, находящую его левый (соответственно правый) конец. Обозначим соответствующие перемещения головки на ленте через L и R.
Предыдущая << 1 .. 33 34 35 36 37 38 < 39 > 40 41 42 43 44 45 .. 104 >> Следующая

Реклама

c1c0fc952cf0704ad12d6af2ad3bf47e03017fed

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

c1c0fc952cf0704ad12d6af2ad3bf47e03017fed