С.В. Яблонский - Введение в дискретную математику (1060464), страница 24
Текст из файла (страница 24)
Например, Дхо .. а х„), равная нулю за исключением конечного числа точек, в которых ее значения принадлежат Ь з,,-примитивно-рекурсивна. В самом деле, пусть ~(х1...,,х„) р' при (х„..., х„) = (и'„..., и'„) (1 = 1, ..., г) а 1 0 в остальных точках и ~1ен ек,(1 =1, ..., 3). Рассмотрим функции 1 (х), где ($ при х =1, 1'() ~0 при *;~. 1-0 1 Очевидно, ),(х) = Яд(х —.' (1 — 1)) Бц(х — ' 1) при 1Ф 0 и Д(х) Зе(х).
Положим ~( ПРИ (Х,, ..., Ха) (1„..., 1„), ~11"" 1а " ' ' (О в остальных случаях. Мы имеем )1и...ла(х1~ ° ° ° з ха) 111(х1) .. в!1а (ха)з 1 (х х ) = Х Р11 «(х1 ", х.) ае..а„ гл. 4, зы'и!слпмыи Функции Последнее является аналогом разложения в дизъюнктнвную нормальную форму. В ааключение заметим, что операции С и Пр, примененные к всюду определенным функциям, дают всюду определенные функции. Отсюда вытекает, что класс Р, замкнут относительно операций С и Пр. Далее мы займемся изучением связи классов Р,„„и Р„. Основная цель состоит в установлении тождественности этих классов.
$6. Вычислимые функции и операции С, Пр, )з Теперь мы займемся изучением особенностей опера. ций С, Пр и р над вычислимыми функциями. Как и в случае предыдущих функциональных систем, мы будем рассматривать функции ~(л„..., л„) с точностью до добавлений и изъятий несущественных переменных и, более точно, несущественных переменных определенного вида. Это связано с тем, что вычислимая функция !(ло ..., л ) определена на некотором множестве К,, которое не обязательно совпадает с множеством всех наборов (ио ..., а„) чисел из расширенного натурального ряда. В этом случае, если рассматривать несущественную переменную по аналогии с функциями нз Р, как переменную, от которой для наборов из Е, функция не зависит, то возникают некоторые трудности. Например, процесс изъятия несущественных переменных может быть неоднозначным.
(См. соответству!ощее рассуждение для не всюду определенных функций из Р„в гл. 3.) Ввиду этого переменную л< функции 1(х„..., л ) из Р„„, мы будем называть несущественной (в узком смысле), если: $) Е! цилиндрично по лб 2) ~ для наборов из Е! не зависит от хо Операция удаления несущественной переменной (см. с. 12) уточняется следующим образом. Пусть для простоты ~(х„..., х„) имеет несущественную переменную л..
По определению Е! цилиндрично по л„и ! для наборов из Е! не зависит от л„. Рассмотрим функцию л(ло ... , л„!) с областью определения К, такую, что: т) К, — проекция Е, на подпространство (хо ..., х„,); последнее в силу цилиндричности Е, по з„ эквивалентно условию (а„..., !х.,) ~ Е, тогда и только тогда, когда для любого !з„ен Е„(аь ..., и.
о с!„)ж Е;, $52 ч. 1. Фупкцпоплльпыв спсткмы с опвглппями 2) длл любого (а„..., и.,) из Е, у(а„..., а„,) = ~(иь .. ь и„„О). Операция введения несущественной переменной выглядит так. Пусть ((хь .. ч х„) — вычислимая функция с областью определения Еь Рассмотрим функцию Ь(х„... ..., х„, х +,) с областью определения Е» такую, что: 1) Е,— цилиндр по х.+, с основанием Ен т.
е. (а„... ..., а„, а„+,)ыЕ» тогда и только тогда, когда (а„... ..., а„)»иЕ», 2) для любого (а„..., и„, а...)ш Е» Ь(иь ..., а„, а.»,)=Дан ..., а.). Лемма 6. Из вычислимой функции при добавлении и изъятии несущественных переменных получается вычислимля функция. Дока аательство.
Справедливость леммы докажем для частных случаев. а) Пусть у(х„..., х,) получена из Дхь ..., х„ь х.) путем изъятия несущественной переменкой х„. Рассмотрим преобразование код (а„ ..., а ,) - код(а„ ..., а„ „ О)- — код~(аь ..., а. „О). Соответствующая машина Тьюринга, очевидно, вычисляет функцию у(х„..., х„,). б) Пусть Ь(х„..., х., х„+,) получена кв ((х„..., х„) путем добавления несущественной переменной х.+,.
Рассмотрим преобразовакие код(а„..., а„, а»ы)- код(и„..., а„)' - код1(аь...,а.). Соответствующая машина Тьюринга вычисляет функцию Ь(х„..., х., х +,). Общий случай сводится к доказанным с использованием следствия приводимой ниже леммы. Лемма 7*). Если 1(хь ..., х»), (1(хо ", х.),, ~т(хь ..., х») ») В доказательстве леммы существенно, что вычнслнмая функция может быть реализована машиной, вычисляющей ее правильным образом, 153 гл. а вычпслпмык отпкцни вь>числилсы, го у>ункдия Д(,(хп ..., х„), ..., ( (х„..., х„)) гакхсе вычислила. Д о к а з а т е л ь с т в о.
Рассмотрии преобразование «К,А,А >К>А,А,о>. К, — преобразование кода (а„, ..., а„) в (т+1)-кратиый код с буферным словом У = О... 01 Очевидно, что > -» мы получаем на первых т решетках с шагом т+1 коды, совпадающие с кодом (ип ..., и„), а па и>+1-й решетке — сплошной массив из единиц. А, преобразует код(а„..., а„) иа 1-й решетке в код ка 2-й на и>-й » 1 (и„..., а„) и па и+1-й решетке всюду, где побывает головка, ставится 1.
Это преобразование выполняется путем использования га раз машин, моделпру>ощих вычисление функций »(х>, ..., х.) (1=1, ..., и) (см. следствие 4 к лемме 1). А, осуществляет «выравнивание» кодов Д>(ап ..., и„) ка решетках >(1=1, ..., и>). Для этого на т+1-й решетке находят леву>о единицу и сдвигаются влево от кее иа Зт+2 ячеекв). Мы попадаем на первую решетку и осуществляем сдвиг кода (>(а„..., сс„) к этой ячейке (моделирование машины, осуществляющей сдвиг влево).
Затем из ячейки, в которой находится левая единица на 1-й решетке, смещаемся вправо ка одну ячейку в мы попадаем иа втору>о решетку. Аналогичным образом производим сдвиг кода Яап ..., >х ) к этой ячейке и т. д. После сдвига кода г (а„..., а.) ка пь-й решетке головка обозревает левую единицу ка пь-й решетке, и мы очищаем отрезок и+1-й решетки левее этой ячейки, а затем воз- с) Левая едпнппа но т+ 1-й рсшсткс копыт быть правее леной сдпнпцы па 1-й решетке на >н нчсск. 154 ч. ь Фупкцпопллъпые системы с опеэлппямп вращаемся к левой единице ка 1-й решетке. Мы получилп решетчатый код с параметром з = лг+ 1.
К, осуществляет преобразование решетчатого кода в основной, А, в основном коде стирает последний лг+ 1-й массив и возвращает головку к левой единице кода. Мы имеем ка ленте код(~,(иь ..., а„), ..., 1,. (аь ..., а.)). А, преобразует этот код в код Я,(аь ..., и ), ... ..., 1 (аь ..., а )). Очевидно, что данное преобразование выполнимо тогда и только тогда, когда значение Яь ..., 1 ) определено. Здесь, по существу, используется вычпслимость функций ~, А, ..., 1 машинами правильным образом.
Таким образом, машина, осуществляющая это преобразоваиие, и будет искомой машиной. Лемма доказана. Пи ...м Следствие 1. Пусть(г ~ г — произвольная под~гг" т/ становка. Тогда 1(У~",(хм ...,хт), г;г (хи ...,х ), ..., 1, (х„ ..., х )) 1(хцю ° 1 х$щ) Это означает, что функции, получаемая из вычислимой функции путем перестановки переменных, вычислима. Следствие 2.
Лемма 7 легко обобщается на случай, когда функции ~ь ..., ~ зависят не от всех переменных хь ..., х . Последнее достигается путем добавления всех недостающих несущественных переменных (лемма 6) из функций ~ь ..., 1 и применения леммы 7. Теорема 1. Класс Р,„, замкнут относительно операции суперпозиции. Доказательство основано ка использовакии лем- 1 мы 7 и того, что тождественная функция 1,(хг) принадлежит классу Р,„, (см. замечание 3 иа стр. 18). При рассмотрении операций Пр и д мы будем иметь дело с анализом и преобразованиями кодов, расположениых иа решетках с некоторым шагом 1. В связи с этим рассмотрим три оператора, которые содержательно можко охарактеризовать так: оператор р (р, р') производит сравнение двух чисел (1 и р' (р > (1'), расположенных ка двух решетках: !55 Гл. 4.
Вы~!Пслпз!ык Функции оператор П(!', у) осуществляет перенос (без стирания) основного кода с г-й решетки па впусту!о» решетку с номером у'; оператор П,(у, у) переносит (со стиранием) заданный код числа у с 1-й решетки на решетку у, располагая его через нулевой промежуток левее основного кода, который находится на у-й решетке. В дальнейшем будут рассматриваться решетки с шагом 3 и 4. Ниже доказываются леммы для случая, когда берутся решетки с шагом 4 и специальных значений параметров ! и у'. Соответствующие утверждения для других случаев доказыва»отса аналогично.
Лемма 8. Пусть оператор р (р, р') сравнивает числа р и () (р ~ ))'), расположенные соответственно на 1-й и 2-й решетках, причел! начало кода р' находится в ячейке, лежащей непосредственно справа от ячейки, в которой начинпется код р. Пусть, далее, в начальный момент головка обозревает начпло кода р, а в заключительный— ту же салгую ячейку. Наконец, пусть преобразование не меняет всей записи на ленте и завершается в состоянии х', если р 1, и в х", если р =О.
Тогда существует машина Тьюринга, реализгу!огцпя оператор р.(~, 1'). Тябляпя !8 Доказательство. Расс»!отри»! табл. 18. Очевидно, что эта машина останавливается при р > р' в состоянии х, и при () р' в состоянии х,. Для того чтобы построить искомую машину, необходимо вернуть головку данной машины в исходное положение. Лемма доказана.
Лемма 9. Пусть П(2,3) осуществляет перенос (без стирания) основного кода со 2-й решетки на «пустую» решетку с номером 3, причем в начальный момент обозревается левая единица основного кода на 2-й решетке, в конце преобразования — некоторая ячейка 2-й решетка, и запись на остальных решетках не меняется. Тогда мож- 156 ч г Фугпгчпонлльпые системы с Опвгапняъп1 но построить машину Тьюринга, реализугощуго оператор П(2, 3). Д о к а з а т е л ь с т в о. Рассмотрим табл. 19. Она, очевидно, определяет машину, реалнзующуго П(2, 3). После переноса машина останавливается на 2-й решетке правее основного кода в состоянии х,.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
