С.В. Яблонский - Введение в дискретную математику (1060464), страница 25
Текст из файла (страница 25)
Лемма доказана. Табмена 19 ху х> хе х, х, Оям„ 1их„ Олхг Огтхг 1йхг 1бм, Оггх, 11гме 1нхз Ойх„ 1нх, Одх, 1Ухг Лемма 10. Пг1сть оператор П,(3, 1) осуществляет перенос кода 1' (массив из единиц) с 3-й решетки на первую, располагая его через нулевой промексуток левее основного кода, при'гелг в начальный лгомент обозревается левая единица основного кода, расположенного на 1-й решетке, в конце преобразования — левая единица построенного основного кода на 1-й решетке и код 1 на 3-й решетке стирается, а жг- 3 пить основного кода на 2-й решетке не меняется. Пусть, далее, на 4-й реисетке ннстнз нз нензнз в начальный. лгозгент нахоРнс.
8 дится лгассие из единиц, который захватывает все точки этой решетки в пределах кодов первых трех решеток (см. рис. 8), и в конце преобразования имеем на 4-й решетке массив из единиц, также захватывающий все точки решетки, но в пределах построенных кодов на первых трех решетках. Тогда можно построить машину Тьюринга, реализующую оператор П,(3, 1). Доказательство. 1) Оператор Ф(а'- 1 10а) ставит на первой решетке слева от основного кода символы 10. 2) Смещаемся влево на единицу (оператор Бг), попадаем на 4-ю решетку, Гл. ь Вычисш!мыв Функции 157 3) Оператор Г~т отыскивает левый конец массива иэ единиц на 4-й решетке.
4) Смещаемся влево на единицу (оператор Б,), попадаем на 3-ю решетку. 5) Оператор Еш находит левый конец кода ~ на 3-й решетке (движение вправо). 8) Аналпзкруем начало а'а" кода на З-й решетке, вычисляя предикат (1 прн а" -1. Если р 1, то: 7) Стираем оператором Ои1(а') символ а'. 8) Смещаемся вправо на единицу (оператор В,), попадаем на 4-ю решетку. 9) Оператор Ятт находит правый конец массива из едпнвц на 4-й решетке. 10) Оператор В, осуществляет сдвиг на единицу вправо.
11) Двигаясь налево по первой решетке, находим (оператор Е,) левый конец кода,на 1-й решетке. 12) Оператор Ф (а' - 1'с) пристраивает к этому коду слева на 1-й решетке еще одну единицу, и, далее, возвраьпаемся к оператору 2). Если р=О, то: 13) Стираем оператором 0„,(а') символ а'. 14) Смещаемся вправо (оператор В,) на две единицы — попадаем на 1-ю решетку. 13) Отыскиваем (оператор Х~) левый конец основного кода на первой решетке и останавливаемся. Считаем, что все моделирующие операторы на 4-й решетке в пределах рабочей зоны ставят единицы. Операторная схема для П~(3, 1) имеет следующий вид: Лемма докааана.
Теорема 2. Класс Р,„, занкнут относительно операции Пр. 'Докааатольство. Пусть функция ~(х„..., х„, х.+,) определяется из вычислимых функций ~р(т„..., х.) 169 ч. к фтккцпонлльнык спсткмы с опквьцпямп и 19(хь ..., х„, х.+„х е,) при помощи операции Пр через схему 1(хо ..., х„, 0) = ~р(хо ..., х„), Дхь ..., х„, у+1) ф(хь ..., х„, у, ~(хь ..., х„, у)). Покажем, что ~(хь ..., х„, х„+,) ж Р,„,. Вместо даппой схемы возьмем другую схему Дхь ..., х„, 0) ~р(хь ..., х„)', ~(хь ..., х„, у+ 1) = ф'Щхь ..., х., у), х„..., х., у), где $'(х„ем хь ..., х„, т„+,) Ф(хь ..., х., х.ьь х„+,). В силу следствия 1 леммы 7 ~' ж Р, „.
1) Оператор К, преобразует код(иь ..., а., 6) в четырехкратный код с буферным словом 0 — 0001, з результате чего получаем код, который разбивается при помощи четырех решеток с шагом 4 па три экземпляра кода(а„..., а„, 6), расположенных ка первых трех решетках, и массива из единиц на 4-й решетке (см. рис. 9) в пределах кодов на первых трех решетках.
нпда,,...,а,я ~а~з~/.-.Фл Ф' лайке -., а„„й хагжУ ю лаз Рзс. 9 2) Оператор Ф заменяет ка второй решетке вод() на код 0 и па третьей решетке стирает код 6, останавливается иад левой единицей третьей решетки, после чего на второй решетке имеем код (ик ..., а„, 6') с р' 0 и па третьей — код (аь .. „а„). 3) Оператор Л, вычисляет ка третьей решетке 9(яь ° ° .1 пл) ° 4) Оператор А, отыскивает начало кода() па первой решетке.
5) Оператор р Щ, 6') (6 > 6') производит сравнение кодов чисел 6 и 6', расположенных на 1-й и 2-й решетках. В конце преобразования обозревается начало кода р. Если р) 1, то: 6) Оператор Б~ отыскивает левую единицу кода на первой решетке, гл. ". сычпслимык чгнкцпп 7) Оператор П~(3, 1) переносит код 1(ао ..., и„, р'), равный коду <р(ио ..., а„) прп 3'= О, с 3-й решетки на первую, располагая его череа нулевой зазор левее основного кода и стпрая код ( на 3-й решетке и в конце преобразования обоаревает левую единицу построенного основного кода — кода (г', я„ ..., а„, р) — на 1-й решетко. 8) Оператор Ен отыскивает левую единицу на 2-й решетке.
9) Оператор П(2, 3) переносит основной код со 2-й решотки на 3-ю (пустую) решетку, заканчивает работу в некоторой ячейке второй решетки. 10) Оператор Ьш отыскивает левую единицу кода на 3-й решетке. 11) Оператор П,(1,3) переносит код~ с 1-й решетки на З-ю, располагая его через нулевой зазор левее основного кода (вариант леммы), после чего на 3-й решетке получим код (1, а„ ..., а„, р'). В конце преобразования обозревается левая единица этого кода.
12) Оператор Ае вычисляет код $'(1, сс„ ..., а„, ()')' на 3-й решетке. Тем самым мы получаем Дае ..., а., 3'+ 1) 4~'((, ао ..., а., ()'). 13) Оператор Р (б', 1) увеличивает на единицу код р' на второй решетке и останавливается в некоторой ячейке 3-й решетки, после чего переходим к оператору 4). Если р О, то: 14» Оператор 0(1, 2, 4) производит очистку решеток 1, 2, 4, ориентируясь массивом из единиц на 4-й решетке, и останавливается над левой единицей на 3-й решетке. 15) Оператор Ка преобразует квазиосновной код, в котором все буферные слова пустые, в основной код.
Мы получаем код Дао ..., и., 3). Здесь все операторы 1) — 13) выбираются таким образом, что они не иэменяют записи на других решетках, а на 4-й решетке в пределах рабочей эоны добавляют единицы. Операторная схема имеет следующий вид: »нфт тэ,рф~цПгди~,~ать,л„платю„гд:тр, ~дга~нэе Теорема доказана. тзс ч. е Фупкцпонлльные системы с опеглцпями Замечание. В доказательстве теоремы по существу используется свойство области определения функции 1(хь ..., х.+,): если 1(ан ..., а, а.+,) не определено, то при 3 > а„+, не определено 1(аь ..., а„, 3). 'Теорема 3. Класс Р,„, замкнут относительно операции и. Доказательство.
Пусть <р(хь ..., х„„х„) — вычислимая функция. Покажем, что функция 2(хь ..., х„), где ДХО ..., Х„) Рк(1Р(ХН ..., Х „У) Х„), вычислима. Рассмотрим вспомогательную функцию ~Р'(У, Х„..., Х„,)=1Р(Хе ..., Х„„У). В силу следствия 1 леммы 7 ~р' вычислима.
1) Оператор К, преобразует код(а„ ..., а„) в трехкратный код с буферным словом У 001, в результате чего получаем код, который разбивается прн помощи трех решеток с шагом 3 па два экземпляра иода(а„ ..., а„), расположенных на первых двух решетках, и массива из единиц на З-й решетке в пределах кодов первых двух решеток. 2) Оператор Ф, „(ак — 1 ' Оа) пристраивает на первой и второй решетках к основным кодам слева код О. кркзкккс ккк Ьк решкекк 2-к ркаваа' коз 1К' Рвс. 10 3) Оператор Оп(а.) стирает на второй решетке последний массив — код а..
4) Оператор Лч вычисляет на второй решетке 1р'(О, а„..., а„,). 5) Оператор А, евыравниваетэ коды на 1-й н 2-й решетках, т. е. располагает их на решетках так, чтобы правый конец кода 1р' находился в ячейке, непосредственно следующей за ячейкой, в которой расположен правый конец основного кода 1-6 решетки (см.
рис. 10). Вь1равнивапне кодов может быть осуществлено следующим образом: двигаясь по третьей решетке, выходим на 1В1 ГЛ. Ь ВЫс)««СЛ««МЫК Фтп)«ЦИИ правый конец массива, затем отступаем вправо на 9 ячеек и, сдвигаясь влево на одну ячейку, попадаем на 2-ю решетку, в которую сдвигаем массив нз единиц (код ф') (см. пример 5) и, далее, из правого конца сдвинутого кода ф' отступаем влево на одну ячейку — мы попадаем на 1-ю решетку, в которую переносим основной код (обобщение примера 5). 6) Оператор рю(ф', ае) сравнивает код ф' и код а, расположенные на 1-й и 2-й решетках (используем программу, аналогичную программе в лемме 8).
Если р 1, т. е. ф' Вь а„, то: 7) Оператор 0(2) очищает 2-ю решетку. 8) Оператор Рв(у, 1) увеличивает код у на 1-й решетке на единицу. 9) Оператор П(1, 2) переносит код с 1-й решетки па 2-ю и возвращается к оператору 3). Если р = О, т. е. «р' = а . то: 10) Оператор 0(2, 3) очищает решетки 2 и 3. 11) Оператор О(1) стирает на 1-й решетке все, кроме первого, массивы из единиц. 12) Оператор К, преобразует квазпосновной код в основной код и останавливается.
Операторная схема имеет вид ° Ку Фут (Р-1 йр) Р~(К„) А,.А Р (РЕ) В«н)Р (У 1) Л(12)Р З(«Р)«)(1)йзо Прп реализации отдельных операторов необходимо учитывать их согласование и простановку единиц на З-й решетке в пределах рабочей зоны. Теорема доказана. Замечание. В доказательстве используется по существу тот факт, что если хоть одно из значений ф(а„... ..., а. „О), ..., ф(а„..., а. „9„-1) не определено, то )(а„ ..., ан) также не определено.
Теорема 4. Класс Р,„, замкнут относительно системз«операций т«(С, Пр, 9). Следствие. Є— Р. ' Данная теореь«а дает возможность устанавливать вычислимость функций, не прибегая к построению машин Тьюринга, путем доказательства их частичной рекурсивности. П р и м е р ы: а) На стр. 149 построен ряд примитивно-рекурсивпых функпий. В силу доказанного они являются также и вычислимыми. 6 Весенние в еискреуную мвеемеенку (ез ч. г. огнкционллькыв спствмы с опкгациями б) Пусть 1(х) х'.,Очевидно, что )жР„, так как г'(О) О, 1(х+ 1) г(х)+ 2х+ 1. Следовательно, (ж Р,„,. $7.
Формула Кляни. Частичная рекурсивность вычнслвмык функцкй. Примеры полных систем Этот параграф мы начнем с установления примитив- ной рекурсивности некоторых функций. 1. Пусть р (х) обозначает число разрядов, содержа- щихся в двоичноп ааписи числа х. Очевидно, что р(0) 1, р(х+ 1) = р(х)+Гй(2м*'-:(х+ 1))'.
Следовательно, р(х)~и Р„. 2. Пусть 6„(хо ..., х.).обозначает натуральное число, двоичная запись которого имеет вид 1 ... 1 0 1 ... 1 ... 0 1 ... 1 ~~+~ ~~+~ ~5+1 Примитивная рекурсивность доказывается индукцией по я: 6,(0) 1, б, (х, + 1) 26, (х,)+ 1, 6„(х„..., х„„О) 46„,(х„..., х„,)+ 1, 0„(хь ..., х„ь х„+ 1) - 26„(хо ..., х„„.т„) + 1. 3.
Рассмотрим функцию п(х„х,) (см. табл. 20). Эта функция называется леоновской функцией н служнт для нумерации всех пар (сг„а,) чисел из расширенного натурального ряда. Очевидно, (х +х)(х +х, +$) к(х хз)- ' ' ' ' +'- 2 -[' ''' (з3 + хг) (я1 + хз + $) 1 г г з 1+ т. е. является примитивно-рекурсивной. 4. С пеановской функцией и(х„х,) связаны Х(х) и р(х).ПустьХ(х)-к(0, х) =~, ~,т. е. функция й(х) ( '(с+И) гл. а Вычислимые Функции ю еадается первой строкой табл. 20 для н. Значит, Х(х)юР„.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
