С.В. Яблонский - Введение в дискретную математику (1060464), страница 26
Текст из файла (страница 26)
Определим функцию р(х) через табл. 2(. Из таблицы видна связь функций и, Х и рл значения функции и пробегают расширенный натуральный ряд и оип делятся Таблеца 20 Табл аца 22 г )з 4 Ь 6 7 8 9 ° ) о а(») ~ О 1 ~ ! ~ 2 2~2~2~2~ З ~... Из этих соображений имеем р(0) О, Н(х+2)-р(х)+Зй(р(х) — '(х —:7 (р(х)))) Поэтому И (х) ш Р,». 5. Пусть (а„а,) — произвольная пара. Тогда т и(ао а,) — ее номер. Обозначим через ((х) и г(х) функции, которые по номеру т пары (ио и,) дают ее диагоналями (х, + х, с) на конечные куски; если а(аы Е» )-произвольное эначение из таблицы для я, то р(а) указывает номер с диагонали, на которой находится а, а л(р(а)) — наименьшее число иа Е»», лежа7цее на этой диагонали.
!64 ч. 1, ФункцпопАльпые системы с опеРАцпяъи! компоненты зх, и аз. Таким образом, з(()= са, н г(() аа. Данные функции удовлетворяют тождествам л(а(х), г(х) ) ° х, 1(л(х„х„) ) х„г(л(х„х,) ) х,. Так как 1(х) = х †' й(п(х)), г(х) р(х) †' а(х), то ((х), г(х)зи Р,„. б.
Функдии л, 1 н г могут быть обобщены па случай многих переменных. Пеановскан функция л.(х„..., х,) определяет номер г-ки (а„..., аа,) чисел из расширенного натурального ряда, а функции Ф,(х), ..., С. (Х) указывают по номеру з-ки значенил ее компонент, т. е. числа !хо ..., а,.
Для з 3 данные функции определяаотся так: л,(х„х„хз) = л(х„л(х„х,) ), Фз(х) = Е(х), 1,(х) = ((г(х) ), Юз(х) = г(г(х) ). Очевидно, что Ла(гз(Х), га(Х), гз(Х))з~ Хэ гз(па(Хзз тз, Хз)) ~з Хзз га(ла(ха, тм ха) ) за за, аз (ла (хз, ха, ха) ) заз хз. Из определения следует, что л,(х„х„х,), гз(х), Сз(х), га(х) принадлежат Р„,. Для дальнейших рассмотрений нам понадобится один способ построения функций. Пусть х-(х„..., х.) п функции !,(х, у), ..., !,(х, у) заданы прп помощи схемы одновременной примитивной рекурсии: )з(х, О) = зр,(х), ~.(х, О) = зр,(х), ~,(х, у + 1)= зрз(х, у, (з(х, у), ..., (,(х, у)), ~,(х, у + () = зр.(х, у, ~,(х, у), ..., )„(х, у)), представляющей естественное обобщение схемы примитивной рекурски.
Эту схему используем для случая, когда ар„ ..., 1р., аРь ..., аР. примитивно-рекурсивны. Покажем, что зги функции могут быть получены из функций чзз "° ар. зрз, ..., зр., а также прнмитивко-рекурсивных Гл. 4. Вычислимые Функции функций л„Фо ..., г, при помощи суперпозиций и при- митивной рекурсии. Рассмотрим функцию 1(х, р)=л,(1,(х, р), ..., 1,(х, р)); мы имеем 1(х, О) л,(1,(х, О)',, 1,(х, О)) л,(<р,(х)', ..., <р,(х)), 1(х, у+()=л.(1,(х, у+ 1), ..., 1,(х, у+ 1)) л,(ф(х, у, 1,(х, у), ..., 1.(х, у)), ..., ф(х, д, 1,(х, р), ..., 1,(х, у))) - л.(ф (х, р, г (1(х, р)), ", г.(1(; р))), " ° ..., ф,(х, р, г,(1(х, р)), ..., г,(1(х, у))))=ф(х, у, 1(х, р)), где Ф(х, р, г) = л,(ф(х, у, С,(г)', ..., Г.
(г) )', ... 1 ° ., фв(х, р, г~(г), ..., 1а(г))) ° Значит, 1(х, р) может быть получена при помощи примитивной рекурсии из л,(~р„ ..., <р,) и ф, т. е. 1(х, р)4и <и Р, . Далее, 1,(х, р)= г,(1(х, р)), ..., 1,(х, р)= г,(1(х, у)), поэтому 1,(х, р), ..., 1,(х, у)ыР„. Докая|ем теперь теорему о представлении вычислимой функции (а значит и произвольной частично-рекурсивной функцпп) через примитивно-рекурсивные функции в специальной форме (аналог теоремы Кляни).
Т е о р е ы а 5. Для всякой вычисяигшй функции 1(х„..., х„) существуют такие яризштивяо-рекурсивные функции Р'у(х„..., х„, р) и 6((хо ..., х„, р), что 1(х„..., х ) Р,(хь ..., х., р,(6,(хо ..., х., р) О)). Доказательство. Пусть 1(хо ..., х„) — произвольная вычислимая функция, которую мы будем записывать короче как 1(х), где х (х„..., х.). Рассмотрим машину Тьюринга, вычисляющую ее правильным образом. Пусть Т вЂ” программа машины и х„..., х, — состояния машины. Введем новое состояние х, (символ х, отличен от х„..., х,) и дополним программу Т, заполнив все ее пустые клетки, а также клетки присоединенного столбца х, следующим образом: если пустая клетка принадлежит строке а, то в нее помещается команда а|х,.
Полученную программу обозначим через Т'. Если усло- 166 ч. 1. Функциональные спстеыы с опкгзцпямн виться, что машина, соответствующая Т' (которая факти- чески работает так же, как исходная), останавли- вается, попадая в состояние к„ то она будет вычислять функцию 1 так же, как исходная машина с программой Т. Для машкны Т' рассгютрпм «а ла в момент времени Г ее ленту н отметим на ней рабочую зону, т. е. совокупность всех ячериРиаии ааии ек ленты, состоящую нз ячеек, Рвс.
И в которых побывала головка машины, н ячеек, в которых записан исходный основной код для з. По отношению к ячейке, которую в момент г обозревает головка, рабо- чая эона разбивается на две части Ж и Я, — левую и правую части (см. рис. 11). Кусок х.г расположен левее ячейки, обозреваемой головкой в момент г, Я, — содержит остальные ячейки рабочей зоны. Обозначим через ),— натуральное число, запись которого в двоичном счисле- нии находится в ячейках 2'„ и через 1, — натуральное число, запись которого в двоичном счислении находится в ячейках Я„ если ее читать справа налево (инверсным образом).
Очевидно, что Ял', Г), Ь=Ял', 1), где л' — натуральное число, запись которого в двоичном счислении совпадает с записью исходного кода л, читаемого справа налево. Пусть 1а(л', г) — номер состояния в момент времени г, если в начальный момент запись на ленте характеризуется натуральным числом х'. В момент времени г 0 будет Я'г Л (пусто), Яг совпадает с множеством ячеек, занятых записью основного кода. Поэтому гг(л', 0)* х', (г(х', 0) О, г,(л', 0) 1. С другой стороны, очевидно, 1г(*', 1+1) = Р,((г(к', г), )а(к', г), 1а(*', 1) ), аа(к', 1+1) гра(гг(л', г), га(х', с), га(х', г)), ~а(х'а 1+ 1)'~ ггаа(Ую(х'а а)а Уг(л'а а) а Уа(х'а а) ).
гл. а Вычпслттмые Функции В самом деле, зная в момент времени С числа (,(х', С), 1,(х', С), ср(х', С), мы находим число, обозреваемое головкой в момент времени С, — это будет младший разряд в двоичной записи С,(х', С) и состояние машины, номер которого есть Ях', С). Эти две величины позволяют по таблице Т' налти новое значение этой ячейки, новое состояние (номер состояния) н характер двин'ения и, в конечном счете, числа С,(х', С+ 1), с,(х', С+1), С,(х', С+1). Эти преобразования и дают формулы для тр„тр, и фр.
Сейчас мы найдем их явное выражение. Для этого обозначим через Т,(го гр), Т,(г„г,) и Т,(г„г,) соответственно функции, определяемые таблицей и дающие по входному символу и номеру состояния соответственно новый символ, номер нового состояния и номер движения (2 — для движения Ь, 1 — для движения Я и Π— для движения В). Для остальных значений из расширенного натурального ряда полагаем значения этих функций равными О. Очевидно, что Т„Т„Т, ш Р„, так как они в конечном числе точек принимают ненулевые значения. Обозначим через т(г) о) младший разряд г и для сокращения записи положим С,(х', С), Ср С,(х', С), 6-Ь(х', С), 'С = Т (Х(И и, сС-Т (Х(У), Ь) Тогда при любом В=О, 1, 2 Ях', С+ 1) = Т,()С Ц,), С,), Соответствующие равенства для С, (х', С + 1) н Ях', С+ 1) составим сначала отдельно для каждого случая: а) с( 1 (движение Я) Л(х С+1) Ст ' Х(С)+С, Ст(х', С+1) (а,' р) Очевидно, что д(т) <ю Р„р.
168 ч. 1. ФункцнонАльные системы с ОпеРАцпямаа б) аа 0 (движение Н) 1,-(х'ат+ 1) = Ц ~ (х'а 1 + 1) 21а + у; в) Ы 2 (движение 1.)' ~1(х',1+1) 2(71 — 'Х(Я+ у)+ Х(Ца ~а(хз Ф+ 1)-Ц Вспоминая, что У,(х', 8+1), (а(х', 1+1) и 1,(х', 1+1)— зто значения функций ар„аЗ, и аГз, и объединяя соответствующие равенства из разных случаев, имеем ф,(1и У.,6) -У, — Х(6)+т,(У.(а,а а+ + (2~ 82 а+Х(11) Ва(( — '1)* фа Уа Уа Уз) = (211 + Та(ХУ1) Уз))'201(+ + Уа'БКЫ'БК(11 1) + [~~'ЯКИ ' 1) Фв(У1 Уа Уз)-та(Х(У1) Уз) ОтсюДа вытекает, что ааль аРз, Ч1а 'и Р.а. Дла фУнкЦий 1о 1з и 1а мы имеем схемУ оДновРеменной примитивной рекурсии. Следовательно, мы можем утверждать, что )„1а, 1а ыР„. Возьмем теперь Н,(Ях', 1)-0). Данная функция принадлежит классу Р„и определяет для каждого х' момент останова машнны.
Если зту величину подставить в Л, то получим ~,(х', ра(1з(х', 1) 0)), т. е. если машина останавливается, то получим натураль- ное число, двоичной записью которого будет код ~(х). тво гл, ь Вьгчислиыыв Функции В таком случае, если учесть, что х' б'(х„ ..., х„), где О'(хь ..., х„) б„(х„, ..., х,), то ~(х» ..., х„) - р У (О'(хи ", х.), р (Ь(О'(хи ° х.), () = О) ))+ 1 ° Если положить Р~(хм ..., ха, у) = р(/,(бт(г„..., .т„), у)) — '$, С,(х„..„х„, у) 1,(б'(хи ..., х„), у), то получим требуемое. Теорема доказана. Как следствие из теорем получается Теорема 6. Р,„„Р„. Табл зцз 22 Из последних двух теорем имеем также, что каждая частично-рекурсивная функция может быть записана через примитивно-рекурсивные функции в виде канонического уравнения, даваемого представлением Клини. Теорема 7.
Система функций (О, Я(х), 11 (х)) полна в Р, относительно набора онераций (С, Пр, р), Теорема 8. Система функций (О, Я(х)) нолна е Р, относительно набора операций (С, Пр, р), 11О ч. е ФкнкцпонАлъные системы с ОпеРАциями Д о к а з а т е л ь с т в о. Функция 1', (х) определяется через 0 и 8(х) при помощи следующей схемы: 1', (О) О, 1',(х+ 1) -В(1',(х)). У Теорема 9. В функциональной системе (Р ч, С, Пр, )з) существует аналог Яуннции Ше4бберае).
Доказательство. Возьмем функцию 1(хо хз) (см. табл.22).Очевидно,Яхо х,) В(х,) н ~(хо 8(х,)) О(х,). Затем, как в предыдущей теореме, получаем 1,'(х„х,), 1,'(Х,) 1,'(Х„Х,) И ВСЕ 1н(Х1, ..., Х»). ОтСЮда ЛЕГКО ПОстроить также класс Реме. е) Здесь через Р', обоззвчам множество Ром»1Уе е' ЧАСТЬ 11 КОМБИНАТОРНЫЙ АНАЛИЗ Комбинаторный анализ занимается изучением объектов из конечного множества Е (а„..., а„) и их свойств. Этими объектами могут быть подмножества множества Е, подмножества с повторяющимися элементами из множества Е, упорядоченные подмножества множества Е и т.
п. Комбинаторный анализ является разделом дискретной математики, истоки которого уходят в глубокую древность. В настоящее время интерес к нему значительно усилился. Благодаря этому комбинаторный анализ сегодня превратился в достаточно развитую ветвь математики, которая непрерывно разрастается. Это делает трудным четко очертить круг объектов и их свойств, которые принадлежат комбинаторике. Ввиду этого мы начинаем с описании простейших (элементарных) комбииаторных объектов.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
