Введение в дискретную математику - Яблонский С.В.
Скачать (прямая ссылка):
Ч. I. ФУНКЦИОНАЛЬНЫЕ СИСТЕМЫ С ОПЕРАЦИЯМИ
И ^(#1, • ? хп* Яп+Іі Хп+г) нри помощи операции Пр через схему
1{хи ..., хп, 0) = ф(^, ..яп)',
/(л?!,хП11/~ы) = ф(^і, ..., хп, у, /{а, *«, г/))'.
Покажем, что І(хи ..#«, хп+і)^ Рвыч. Вместо данной схемы возьмем другую схему
/(Хі Хп> 0) = ф(аг,, хп),
}(хи хп, у + 1) - ф' (}(хи ..Хп, у), хи ..хп, у),
где ф (л^п+г, Хі^ .. хп, агп+і) ” я]? р.., хп, хп+і, Хп+г)*
В силу следствия і леммы 7 ф' е Рвыч.
1) Оператор К, преобразует код{аь ..., ап, р) в четырехкратный код с буферным словом І) = 0001, в результате чего получаем код, который разбивается при помощи четырех решеток с шагом 4 на три экземпляра кода(а!, ..а„, р), расположенных на первых трех решетках, и массива из единиц на 4-й решетке (см. рис, 9) в пределах кодов на первых трех решетках.
8)
коё(а^,...>ап,А) код(а1,...,а1}}^) цпсикд1/3 еёиуау
Рис. 9
2) Оператор Ф заменяет на второй решетке код 3 на код 0 и на третьей решетке стирает код 3, останавливается над левой единицей третьей решетки, после чего на ехо-рон решетке имеем код (аь ап, (Г) с р' = 0 и на третьей — код (аг, ..ап).
3) Оператор Ач вычисляет на третьей решетке
ф(аі а„).
4) Оператор Лі отыскивает начало кода р на первой решетке.
5) Оператор р>(р, Р') (Р^Р') производит сравнение кодов чисел р с рг, расположенных на 1-й и 2-й решетках. В конце преобразования обозревается начало кода р.
Если р> = 1, то:
С) Оператор Ьг отыскивает левую единицу кода на первой решетке,
ГЛ. 4. ВЫЧИСЛИМЫЕ ФУНКЦИИ
159
7) Оператор П/(3, 1) переносит код /(аь ..а„, ?'), равный коду ф(а1} ..ап) при Р'=0, с 3-й решетки на первую, располагая его через нулевой зазор левее основного кода и стирая код / на 3-й решетке и в конце преобразования обозревает левую единицу построенного основного кода — кода {/, аи ..., сс„, р)—на 1-й решетке.
8) Оператор Ьц отыскивает левую единицу на 2-й решетке.
9) Оператор П(2, 3) переносит основной код со 2-й решетки на 3-ю (пустую) решетку, закапчивает работу в некоторой ячейке второй решетки.
10) Оператор ?ш отыскивает левую единицу кода на
3-й решетке.
11) Оператор П. (1,3) переносит код / с 1-й решетки на 3-ю, располагая его через пулевой зазор левее основного кода (вариант леммы), после чего на 3-й решетке получим код (/, сц, ..ап, ?Е). Б конце преобразования обозревается левая единица этого кода.
12) Оператор вычисляет код-ф'(/} а15 ..ап, (Г) на 3-й решетке. Тем самым мы получаем
/(сеь ..., о«, р' + 1) = \1/(/, «і Р')\
13) Оператор 1) увеличивает на единицу код
на второй решетке и останавливается в некоторой ячейке
3-й решетки, после чего переходим к оператору 4).
Если р> = 0, то:
14) Оператор 0(1, 2, 4) производит очистку решеток 1, 2, 4, ориентируясь массивом из единиц на 4-й решетке, и останавливается над левой единицей па 3-й, решетке.
15) Оператор Кг преобразует квазиосновной код, в котором все буферные слова пустые, в основной код. Мы получаем код /(«і, ап, ?>)?
Здесь все операторы 1)—13) выбираются таким образом, что они не изменяют записи на других решетках, а на 4-й решетке в пределах рабочей зоны добавляют единицы.
Операторная схема имеет следующий вид:
Теорема доказана.
uni u ишьглцішти
Замечание. Б доказательстве теоремы по существу используется свойство области определения функции f{x 1, ?n+i): если f(au ..., а„, а„+1) не определено, то при р > а„+1 не определено /{а„ ..ап, р).
Теорема 3. Класс Рвыч замкнут относительно операции р.
Доказательство. Пусть ф(гь ..хп~и хп)>—вычислимая функция. Покажем, что функция j{xj, ..хп), где
/ ? ? “» ^я) '= * * ?» <?п~i) ?)
вычислима.
Рассмотрим вспомогательную функцию
В силу следствия 1 леммы 7 ф' вычислима.
! 1) Оператор Кк преобразует код(сс!, ..., ап) в трехкратный код с буферным словом и “= 001, в результате чего получаем код, который разбивается при помощи трех решеток с шагом 3 на два экземпляра кода(о?(, ..а„), расположенных на первых двух решетках, и массива из единиц на 3-й решетке в пределах кодов первых двух решеток.
2) Оператор Фх. и (я* 11 Ос) пристраивает на первой
и второй решетках к основным кодам слева код 0.
3) Оператор Он («Л стирает на Еторой решетке последний массив — код а„.
4) Оператор вычисляет на второй решетке
ф'(0, Ох, «„-О.
5) Оператор А і «выравнивает» коды на 1-й и 2-й решетках, т. е. располагает их па решетках так, чтобы правый конец кода ф' находился в ячейке, непосредственно следующей за ячейкой, в которой расположен правый конец основного кода 1-й решетки (см. рис. 10).
Выравнивание кодов может быть осуществлено следующим образом: двигаясь по третьей решетке, выходим на
bcnsBh?? ход
1-я pemsma
ход р‘ Рпс. 10
ГЛ. 4. ВЫЧИСЛИМЫЕ ФУНКЦИИ
161
правый конец массива, затем отступаем вправо на 9 ячеек и, сдвигаясь влево на одну ячейку, попадаем на 2-ю решетку, в которую сдвигаем массив из единиц (код ф') (см. пример 5) и, далее, из правого конца сдвинутого кода <р' отступаем влево на одну ячейку — мы попадаем на 1-ю решетку, в которую переносим основной код (обобщение примера 5).
6) Оператор р+{ф', а„) сравнивает код ф' и код ап, расположенные на 1-й и 2-й решетках (используем программу, аналогичную программе в лемме 8).
