С.В. Яблонский - Введение в дискретную математику, страница 18

Тогда в силу упомянутого выше изоморфизма 1(хо х„х„х,) 1 (х„х,), Данная функцпя, порождая все хз„позволяет построить функции 1з, 1о . °, 1з з и 1заз з(х). Рассмотрим суперпозицию 6+о-з(1(1з 1ез1о ха)) 11+о-з[1г~(1з 1о 1е ха)) Ф з 1го+е-з(1з 1ез 1о ха) 1го(з,о.о,з )+з-з(ха) 1за(ха) ха Таким образом, из (1) при помощи суперпозиций мы получили 1е(х„хз) и х, что по теореме 11 дает полноту системы (1). Теорема доказана.

Мы видим, что для системы (Р„,, „С, О) сохраняются некоторые свойства, которые справедливы для (Р„С). Прогноз других свойств системы (Р„м С, 0) затруднителен, так как, с одной стороны, функциональный объект Рзз з значительно сложнее, чем Р„и, с другой стороны, добавилась операция О. Первое имеет тенденцию разрушать положительные свойства, второе, наоборот — их усиливать. Заранее сказать трудно, какая тенденция окажется доминирующей. На самом деле в случае проблемы полноты оказалось, что сложность функционального объекта все же влияет сильнее, чем дополнительная операция.

Для пояснения приведем без доказательства два результата. Формулировка первого из них может быть понята скорее содержательно, так как в ней используется понятие алгоритма. 110 ч 1 ФункциОнАльные системы с опеуАциями Теорема 14 (М. И. Кратко (9, 10)). Не существует алгоритма, который бы для любой конечной системы о.-д. Яункций выяснял, является она полной или нет. Теорем а 15 (В. Б. Кудрявцев [12)). Мощность мнохгества предполных в (Р„м С, О) классов равна континууму. Таким образом, проблема полноты для (Рвам С, О) содержит эначптельные трудности. $8. О соотношении операций С и О Функциональная система (Р„м С, О)' обладает многими специфическими свойствами. Однако их формулировка и изложение требуют аначительно больше места, чем, например, для (Р„С). Поэтому едесь мы коснемся только одного вопроса, свяеанного с тем, что в отличие от рассмотренных, система (Р„м С, О) содержит две операции С в О.

Речь пойдет о том, в какой мерв обе эти операции существенны. Более точно: можно ли выразить результат одной операции через другую и, в частности, отличаются ли друг от друга операции замыкания в системах (Р„,ь, С), (Р„,, О) и (Рек „С, О) Г Сначала. докажем некоторые вспомогательные утверждения. Теорема 18. Пусть Х (х„..., х„), а ДХ) — о.-д.

Функция веса г; пусть а — периодическая последовательность с периодом р. Тогда существует г, (г,Кг) такое, что последовательность т (т' 1(а)) периодическая с периодом р„где р, г,р. Доказательство. В силу периодичности носледовательности и, существует таков гн что при с> г,> 1 а(1+ р) *= а(г). Функцию ДХ) можно эадать диаграммой Мура, содержащей г вершин. Возьмем числовую ось $ н в точке $в (гв 1, 2, ...) поставим две пометки; числа сг(гв) н х(1в-1)-номер вершины, в которую мы попадаем, исходя иэ начальной вершины и следуя по пути (сс(1), ..., сг(св — 1)) (см.

рис. 18). Рассмотрим далев решетку с начальной точкой г. и с периодом р (см. рис. 19). Так как диаграмма Мура содержит г вершин, то в по следовательпости х(г,— 1), х(~, + р — 1), ..., х(г„+ гр — 1) гл. 3, О..д. Функции с опкРАццями ««! по крайней мере два числа совпада!от. Пусть ! и ) таковы, что х (г, + !р — 1) х (1, + )р — 1) () > ! > О) .

Положим г, ) — !. Ясно, что г,в г. Рассмотрим надрешетку данной решетки с периодом р, г,р и начальной ай а«2) а1Г)''' ««ггя. ««д) ««д Рве. !$ точкой г,+!р (см. рпс. 20). Очевидно, вершнны 1,+!р и г,+«р+р, характеризуются тем, что в нпх обе пометки ее и х совпадают. Это означает, что в зти моменты времени мы находимся в одной и той же вершине диаграммы ««Ев) а «гв+») и !!в+ 2р) ««те-И «1'Р» ) ««в Ри!ь !9 и перемещаемся затем по одному и тому же ребру. Тогда к следующему моменту мы попадем в одну и ту же вер- шину, т. е. пометки х(2!+!Р), х($.+)р)', также совпадают. Кроме того, в силу периодичности а сь(1,+ !р+1)= и(г,+)р+1) и т.

д. Отсюда вытекает, что и выходные последователь- ности «Т(!.+!Р) Т(!.+!р+1)," ), «Т(!в+)Р)> Т(го+)Р+1)з ° ° ) совпадают, т. е. при г~ г, +!р Т (1+ Р!). Т (!). Этим теорема доказана. Теорема 17. Пусть )(Х)= 1,(),(Х)', ..., ) (Х)),где )„)„..., )„— о;д. функции с весами г„г„..., г, не превосходяи)ими В, и а — периодическая посяедоватерь- 112 ч. 1, ФункцпонАльиые системы с опеРАциямп ность, период которой содержит только простые множители, каждый из которых нс превосходит В. Тогда ( 1(гг) — периодическая последовательность с периодом, содержащим только простыв множители, каждый из которых нв превосходит В. 6з+(г'$ Рвс. 20 Докааательство.

Пусть а — периодическая последовательность, период которой р содержит только простые множители, ке превосходящие В. Рассмотрим последовательности т -Л(и), ". (--У (и)' По предыдущей теореме они являются также периодическими с периодами Ф Ф / Ф г Т1р рн Тир 1 Г1 Т » (В) Очевидно, они содержат также только простые множители, не превосходящие В. Рассмотрим, далее, вектор ("~~~ " > 7~)ю он будет периодическим и его период р, — общее наименьшее кратное периодов р„..., р; значит, все его простые множители не будут превосходить В. Наконец, последовательность "(-1.(1 ., Т ) по предыдущей теореме будет периодической с периодом р'1 р торг (тг ~ <В). Таким образом, период р' также будет содержать только простыв множители, не превосходящие В.

Теорема доказана. На основе этих утверждений мы докажем следующий факт. Теорема 18. Система (Р„,, С) нв имеет конечного базиса. гл. а Вычислимые Функции Д о к а з а т е л ь с т в о. Пусть имеет место противпое, т. е. система (Р„„С) обладает базисом )ь ..., ),. Обозиачим через г„..., г, веса о,-д, функций Пусть, далее, г шах(г„..., г,) и р — простое число такое, что р ~г. Рассмотрим о.-д. функцию ~,(Х), которая принимает значение, тождествепио равное (, где ( — периодическая последовательность с периодом р, имеющая вид Т-0... 010...

01 а Р Функцию г;(Х) нельзя выразить при помощи суперпозиции через функции )о ..., ~,. В самом деле, если 1(Х)— произвольная суперпозиция фувкций )„ ..., 1„ то оиа будет преобразовывать последовательность О =(О, О, ...) (ее период равен 1) в последовательпость периодическую с периодом, не содержащим простые мпожители, большие чем г. В то же время ),(0)=т — периодическая последовательность с периодом р) г.

Мы пришли к противоречию. Теорема доказана. Так как система (Р,„„С, 0) имеет конечный базис, а (Р„„С) конечного базиса ие имеет, то операция О является существенной. В то же время система (Р,„„О) по очевидным соображениям ие имеет конечного базиса, поэтому операция С является также существенной. Глава 4 ВЫЧИСЛИМЫЕ ФУНКЦИИ 5 1. Машины Тьюриига Иэ предыдущего следует, что о.-д. функцию ~(х„ ..., к.) можно задать при помощи канонических уравнений г(г) - Р(Х(1), д(1 — 1) ), р(г) = а(х(1>, д(1 — 1)), Е(о)-о.

Эти уравнения позволяют строить по входной последовательности эиачевпи переменных ко ..., к выходную последовательность, Более того, зпачения выходной после- 1!4 ч 1 Функцпопзльные с11стемы с опеглцпяып довательности находятся постепенно по мере поступления входных значений. Это позволяет трактовать выписанные выше уравнения как описание работы некоторого дискретного преобразователя или автомата (рис. 1), который обладает г состояниями (г — вес о.-д. функцив) и работает дискретно во времеви, формируя состояние памяти и выходное значенпе в момепт времени ! по состоянию памяти в момент времени !†1 и входным значениям в момент времени 8 в соответРис. ! стени с каноническими уравнениями. Данное устройство, в отличие от реальных автоматов (автоматпческих устройств), никогда не заканчивает работы.

Можно ввести другую функциональную характеристику, эквивалентную исходной, но пмеющую финитный характер. Из детерминированности функции ~ вытекает, что отображение ! порождает отображение конечных последовательностей вида (сс(1), ..., а(!)) в конечные последовательности (((1), ..., ((1)) (3=1, 2, ...). Это отображение обозначим через !р(х). Функцию 1р можно задать прн помощи тех же канонических уравнений, что и ~. Очевидно, что по функции 1р(х) полностью восстанавливается функция 1(х) (в этом смысле выше говорилось об эквивалентности !р и 1). Класс функций !Р(х) обозначим через Р,„„.

Функцию !Р(х) можно интерпретировать как описание работы автомата в следующем смысле: в моменты времени 1, 2, ..., 1 на вход поступают символы а(1), а(2), ..., а(!), а на выходе получают символы ((1), ((2), ..., ((1); в последующие моменты времени па вход ничего не поступает и автомат прекращает работу. В этом случае отсутствие информации на входе равносильно тому, что входной последовательности (а(1), ... „ ., сс(!)) соответствует бесконечная последовательность (а(1), ..., а(!)', Л, ), где Л вЂ” дополнительный символ входного алфавита, означающий отсутствие информации. Появление на входе символа Л является условием останова устройства, т. е. появления на выходе последовательности (((1), ..., ((1), Л, ..).