Введение в дискретную математику - Яблонский С.В.
Скачать (прямая ссылка):
мы будем называть несущественной (в узком смысле), если: 1) Е] цилиндрично по х2) / для наборов из Е{ не зависит от х{.
Операция удаления несущественной переменной (см. с. 12) уточняется следующим образом. Пусть для простоты /(ач, хп) имеет несущественную переменную хп. По определению Е} цилиндрично по хп и / для наборов из Ef не зависит от хп. Рассмотрим функцию ё(хи ... *.%п-0 с областью определения Ей такую, что:
1) —проекция ЕI на подпространство (а^,
последнее в силу цилиндричности Е1 по хп эквивалентно условию (аь ..ап-\)^Е& тогда и только тогда, когда для любого ап^ Е К (сц, ..., ап-и
152 Ч. I. ФУНКЦИОНАЛЬНЫЕ СИСТЕМЫ С ОПЕРАЦИЯМИ
2) для любого («!, Ип-!) из Е,
В(аи ..., «„-!) = /(«!, ап-и 0).
Операция введения несущественной переменной ВЫГЛЯДИТ так. Пусть /{#1, ..хп)—вычислимая функция с областью определения ?/. Рассмотрим функцию к{хи ... ..хп, ^п+() с областью определения Ен такую, что:
1) Ен — цилиндр по хп+1 ? основанием Е/, т. е. (а,, ... ..а„, сСп+0 е Ен тогда и только тогда, когда (а!, ... * ? о&п) ^ Е}\
2) для любого (аь ..ав, осл+1)^7?л
А(аь ..., а,„ ап+1) = /(а1.............а„)'.
Лемма 6. Из вычислимой функции при добавлении и изъятии несущественных переменных получается вычислимая функция.
Доказательство. Справедливость леммы докажем для частных случаев.
а) Пусть ?{я!, ..., Жп-О' получена из Цхи ..., х„-и хп) путем изъятия несущественной переменной Рассмотрим преобразование
код {аи ..., СЕя-О код (а!, ..., ал-!, 0) -*?
-? код/(ах, ..., а„_1( 0)'.
Соответствующая машина Тьюринга, очевидно, вычисляет функцию §(хи ..., дг«-,}.
б) Пусть Н(хи ..., хп, Яп-н) получена из 1(хи ..., хп) путем добавления несущественной переменной хп+1. Рассмотрим преобразование
код(а1( ..., а», а„+1)-> код(а1( ..«„)'-? код/(с^,..., а„).
Соответствующая машина Тьюринга вычисляет функцию Ь{хи ..., хя, аг»+1).
Общий случай сводится к доказанным с использованием следствия приводимой ниже леммы.
Лемма 7*). Если
/(?^11 • ? *Глг) 9 /1 (*^1) • * З'п)', • • >, . . ., 2ц)
*) Б доказательстве леммы существенно, что вычислимая функция может быть реализована машиной, вычисляющей ее правильным образом.
ГЛ. 4, ВЫЧИСЛИМЫЕ ФУНКЦИИ
153
вычислимы, то функция
также вычислима.
Доказательство. Рассмотрим преобразование
* Л, Л 2КгЛ 3Л 4 о.
Кл — преобразование кода (а,, ..ал) в (ш+1)-кратный код с буферным словом и = 0 — 01. Очевидно, что
мы получаем на первых т решетках с итагом т +1 коды, совпадающие с кодом (а,, ..а„ ), а па т + 1-й решетке — сплошной массив из единиц.
А1 преобразует код(а,, ..ос„)
и па т + 1-й решетке всюду, где побывает головка, ставится 1. Это преобразование выполняется путем использования т раз машин, моделирующих вычисление функций /Дя,, жп) 0 = 1, т) (см. следствие 4 к лемме 1) .
Аг осуществляет «выравнивание» кодов /Да,, ..., а„)’ на решетках 1(1 = 1, иг). Для этого на т + 1-й решетке находят левую единицу и сдвигаются влево от нее на Зт. + 2 ячеек*). Мы попадаем на первую решетку и осуществляем сдвиг кода /Да,, ал) к этой ячейке (моделирование машины, осуществляющей сдвиг влево). Затем из ячейки, в которой находится левая единица на
1-й решетке, смещаемся вправо на одну ячейку — мы попадаем на вторую решетку. Аналогичным образом производим сдвиг кода ..., а„) к этой ячейке и т. д.
После сдвига кода Д.(а*, а„) на т-й решетке головка
обозревает левую единицу на т-й решетке, и мы очищаем отрезок ш + 1-й решетки левее этой ячейки, а затем воз-
на 1-й решетке в код
/Да,, а„),
/Да,, а„),
на 2-й
на т-п
»
/?п (а,, ..., ап)
*) Левая единица на т + 1-й решетке может быть правее левой единицы на 1-й решетке на т ячеек.
154
Ч. I. ФУНКЦИОНАЛЬНЫЕ СИСТЕМЫ С ОПЕРАЦИЯМИ
вращаемся к левой еднпице на 1-й решетке. Мы получили решетчатый код с параметром а = т + 1.
К2 осуществляет преобразование решетчатого кода в основной.
Л3 в основном коде стирает последний т + 1-й массив и возвращает головку к левой единице кода. Мы имеем на ленте код(/|(а!, ..., а„), ..а*)).
Ак преобразует этот код в код У{/1 («1, .. а*)',
• . /го (ОС 1, . . ОС)г) ) .
Очевидпо, что данное преобразование выполнимо тогда и только тогда, когда значение /(Д, ../т) определено. Здесь, по существу, используется вычислимость функций /, Д, ../го машинами правильным образом.
Таким образом, машина, осуществляющая это преобразование, и будет искомой машиной. Лемма доказана.
(1 2 ... гп \
Следствие 1. Пустъ\г^^ произвольная под-
становка. Тогда
• • •, Ят), С™ (а?1, ..., хт), .. ., ..., *т))=-
~ / (^*1! • • Ч ^,п)-
Это означает, что функция, получаемая из вычислимой функции путем перестановки переменных, вычислима.
Следствие 2. Лемма 7 легко обобщается на случай, когда функции Д, ../т зависят не от всех переменных хи ..., хп.
Последнее достигается путем добавления всех недостающих несущественных переменных (лемма 6.) из функций Д, . . ., /го и применения леммы 7.
Теорема 1. Класс Ръыч замкнут относительно операции суперпозиции.
Доказательство основано на использовании леммы 7 и того, что тождественная функция (а^) принадлежит классу Ръыч (см. замечание 3 на стр. 18).
