Введение в дискретную математику - Яблонский С.В.
Скачать (прямая ссылка):
При рассмотрении операций Пр и р мы будем иметь дело с анализом и преобразованиями кодов, расположенных на решетках с некоторым шагом I. В связи с этим рассмотрим три оператора, которые содержательно можно охарактеризовать так:
оператор р>(р, Р') производит сравнение двух чисел Р и р' (Р^Р'), расположенных на двух решетках;
[1 при р> р',
ГЛ. 4. ВЫЧИСЛИМЫЕ ФУНКЦИИ
155
оператор Щг, У) осуществляет перепое (без стирания) основного кода с і-й решетки на «пустую» решетку с номером /;
оператор ПДг, /) переносит (со стиранием) заданный код числа / с г-й решетки на решетку располагая его через нулевой, промежуток левее основного кода, который находится на /-й решетке.
Б дальнейніем будут рассматриваться решетки с тагом 3 и 4. Ниже доказываются леммы для случая, когда берутся решетки с шагом 4 и специальных значений параметров і и /. Соответствующие утверждения для других случаев доказываются аналогично.
Лемма 8. Пусть оператор /?>(р, [5') сравнивает числа р и р' (р>р'), расположенные соответственно на 1-й и 2-й решетках, причем начало кода р' находится в ячейке, лежащей непосредственно справа от ячейки, в которой начинается код р. Пусть, далее, е начальный лш.ненг головка обозревает начало кода р, а в заключительный — ту же самую ячейку. Наконец, пусть преобразование не меняет всей записи на ленте и завершается в состоянии у\ если р> = 1, и в у", если р> — 0. Тогда существует машина Тьюринга, реализующая оператор
ЫЬ п.
Таблица 18
к. У-1 в*
0 0Нх4 0 Нх1
і 1Вхэ П!х4 і/їх,
Доказательство. Рассмотрим табл. 18. Очевидпо, что эта машина останавливается при р > р' в состоянии У.2 И при р = р' В СОСТОЯНИИ У.1. Для того чтобы построить искомую машину, необходимо вернуть головку данной машины в исходное положение. Лемма доказана.
Лемма 9. Пусть П(2, 3) осуществляет перенос (без стирания) основного кода со 2-й решетки па «пустую» решетку с номером 3, причем в начальный момент обозревается левая единица основного кода на 2-й решетке, в конце преобразования—некоторая ячейка 2-й решетки, и запись на остальных решетках не меняется. Тогда мож-
156 Ч. I. ФУНКЦИОНАЛЬНЫЕ СИСТЕМЫ С ОПЕРАЦИЯМИ
по построить машину Тьюринга, реализующую оператор П(2, 3).
Доказательство. Рассмотрим табл. 19. Она, очевидно, определяет машину, реализующую 11(2,3). После переноса машина останавливается на 2-й решетке правее основного кода в состоянии х9. Лемма доказана. *
Таблица 19
*1 «а к» х. к, *1 X,
0 1 Як3 0 Ян< 0Л*И 0Ях6 0Нк7 0 ОЯк«
1 1 1«х, иы5 15'х, 1Д*а 1Дкв 15к,
Лемма 10. Пусть оператор П}(3, 1)' осуществляет перенос кода / (массив из единиц) с 3-й решетки на первую, располагая его через нулевой промежуток левее основного кода, причем в начальный момент обозревается левая единица основного кода, расположенного на
1-й решетке, в конце преобразования — левая единица построенного основного кода на 1-й решетке и код / на 3-й решетке стирается, а запись основного кода на
2-й решетке не меняется. Пусть, далее, на 4-й решетке в начальный момент находится массив из единиц, который захватывает все точки этой решетки в пределах кодов первых трех решеток (см. рис. 8), и в конце преобразования имеем на 4-й решетке массив из единиц, также захватывающий все точки решетки, но в пределах построенных кодов на первых трех решетках. Тогда можно построить машину Тьюринга, реализующую оператор
пдз, 1).
Доказательство. 1) Оператор ста-
вит на первой решетке слева от основного кода символы 10.
2) Смещаемся влево на единицу (оператор 1ц), попадаем на 4-ю решетку.
кед
код
1
код
3
“ 4
- ч^
цсссид из единиц Рис. 8
ГЛ. 4. ВЫЧИСЛИМЫЕ ФУІШЦИИ
157
3) Оператор ?iv отыскивает левый конец массива из единиц на 4-й решетке.
4) Смещаемся влево на единицу (оператор попадаем па 3-ю решетку.
5) Оператор Lui находит левый конец кода / па 3-й решетке (движение вправо).
6) Анализируем начало а а" кода на 3-й решетке, вычисляя предикат
~ ..~ _ (° при а” - о.
U upn а = 1.
Если р — 1, то:
7) Стираем оператором Оіп(д') символ а*.
8) Смещаемся вправо на единицу (оператор Rt), попадаем па 4-ю решетку.
9) Оператор Ліу находит правый конец массива из единиц на 4-й решетке.
10) Оператор і?і осуществляет сдвиг на единицу вправо.
11) Двигаясь налево по первой решетке, находим (оператор Li) левый копец кода на 1-й решетке.
12) Оператор Ф(«*->-1+а) пристраивает к этому коду слева на 1-й решетке еще одну единицу, и, далее, возвращаемся к оператору 2).
Если р = 0, то:
13) Стираем оператором 0ш(а') символ а .
14) Смещаемся вправо (оператор R3) на две единицы — попадаем на 1-ю решетку.
15) Отыскиваем (оператор Ai) левый конец основного кода на первой решетке и останавливаемся.
Считаем, что все моделирующие операторы на 4-й решетке в пределах рабочей зоны ставят единицы.
Операторная схема для ПДЗ, 1) имеет следующий вид:
#ФУЬ)LtjIf?jgр(йs ) Q^(S)R^
Лемма доказана.
Теорема 2. Класс Рьыч замкнут относительно операции Пр.
Доказательство. Пусть функция /(агь ..
?„+,) определяется ИЗ ВЫЧИСЛИМЫХ функций ф (ач, ,. ., Хп)
158
