Введение к работе
Актуальность теш. Одной из ваташх проблем, рассматриваемых в математической кибернетике, является проблема полноты для функциональных систем. Функциональная система /ф.с/ представляет собой множество функций и множество операций над отими функциям. Проблема полноты для: ф.с. состоит б описании всех таких подмножеств функций, используя которые с помощью операций ф.с. можно выразить все принадлежащие ф.с. функции.
С точки зрения алгебры ф.с. могут рассматриваться как вариант универсальных алгебр. Существенной особенность*) ф.с, выделяющих их из общего ісласса универсальных алгебр, является содержательная связь ф.с. с реальными кибернетическими моделями управляющих систем и отображение важнейших характеристик таких моделей: функционирования, правил построения более сложных систем из заданных, описания функционирования сложных систем по функционированию их компонент.
Центральное ыесго среди ф.с. принадлежит итеративным ф.с, представляющим собой множество дискретных функций с операциями итерации - суперпозиции, обратной связи, а также их модификациями /1,7/. В свою очередь итеративные ф.с. могут быть разделены на два типа: истиностнне ф.с. и последовательные ф.с В первом случае функции, принадлежащие ф.с, вычисляются бея использования, а во втором - с использованием "памяти".
Важнейшими примерами истиностных и послодователыгсетннх ф.с. являются К-значнне логики, с одной стороны, и ф.с автоматных функций, с другой. Отличительной чертой этих ф.с якляется возш;люсть с их помощью аппроксимировать произвольные итеративные ф.с: К-значнне логики за счет увеличения числа К аиирок-
- 4 -симируют логики любой значности, а ф.с. автоматних функций с ко нечнои памятью и ограниченным временем вычислений могут аппрокс мировать все последовательностные ф.с. Кроме того ашіроксимацио ньііі подход к изучению итеративных ф.с. обладает еще одной важнс особенностью. Он позволяет аппроксимировать операции итерации /обратной связи/ через операции суперпозиции. Таким образом, с ашрокеимационной точки зрения изучение итеративных ф.с. сводит сн к изучению двух центральних моделей - К-значных логик с or рациями суперпозиции и ф.с. автоматних функций с конечной памят ограниченным временем вичислений и также с операциями суперпозі ции. Тем самым эти две модели являются ключевыми в теории итерг тивных ф.с.
Для К-значных логик - ф.с. r^-, основная проблема в теорі итеративных ф.с. - проблема полноты, была решена. Усилиями многих авторов /Е.Пост, С.В.Яблонский, А.В.Кузнецов, А.И.Мальцев, Ло чжу-кай, Н.Розенберг и др./ были последовательно в явном ви,і построены все преддолные классы в &. , образующие минимальную критериальную систему для распознавания полноты систем функций К-значних логик. Важно отметить, что для явного задания множеі ва предполных классов в г^ был использован аппарат сохранения функциями /("-значных логик отношений /предикатов/. Именно на этом пути было проведено завершающее построение множества всех предполных классов в /С-значных логиках /4,6/.
Проблема полноты для ф.с. автоматных функций с конечной п мятью и ограниченным временем вычислений долгое время оставала открытой. В диссертации приводится полное решение этой проблем В качестве исходной модели рассматривается ф.с. /з.-д. , элемент ми которой являются конечно-автоматные или ограшченно-детерми рованные функции /о.-д. функции/, а операциями - операции супе
позиции и обратной связи.
В СИЛу СВОеГО Определения /1,2/ О.-Д. ФУНКЦИИ ЯВЛЯЮТСЯ бОСг-
конечнозначными и далее континуумзначннш функциями. Тем самим предполагается, что вычисляющие о.-д. функций автоматы "работают" бесконечно долго. Однако совершенно ясно, что каждое реальное кибернетическое устройство /в том числе, автомат/ по истечении некоторого конечного промежутка времени прекращает свою "работу", т.е. либо становится ненужным, либо переводится в начальное состояние. В связи с этим возникает
Проблема Т-яолноты. Пусть АС >-2 Пусть >о.-д. ~ последо-вательностная ф.е., элементами которой язляются о.-д. Функции, а операциями - операций суперпозиции и обратной связи; при этом предполагается, что переменные о.-д. функций, принадлежащих / -принимают значение из Сц; - множества всех бескопечшк последовательностей, составленных из элементов В^~ {.0Д,..., К- 4 / . Пусть fC - фиксированное натуральное число, большее или равное единице. Множество 7К~ <о,~я.< называется 'с.-полным, если для любой о.-д. функции J-G f~o.-g. из «-Д« функций множества ]ТС с помощью операций суперпозиции и обратной связи можно получить о.-д. функцию .^- , совпадающую с j- на всех наборах, составленных из слов длины f . Проблема ^-полноты состоит в описании t-полных подмножеств множества Р0-д.
Выше было отмечено, что каждую функцию, ІПМНаДЛЄЗкащую исти-ностным ф.с, мокно аппроксимировать функциями К-значннх логик. Вместе с тем, всякую функцию, вычислимую с использованием "памяти", т.е. функцию, принадлежащую лоследовательностным ф.с., можно аппроксимировать о.-д. функциями, причем это достигается путем увеличения не только числа К , как в истшюстаых ф.с, но и числа tl - времени вичислений. Таким образом, исходя из произвольного
t-полного множества о.-д. функций, любую функцию с "памятью" некоторой степенью точности можно реализовать в виде схемы, построенной из элементов этого множества.
В /2, 29/ показано, что для решения проблемы' t-полноты операция "обратная связь" оказывается несущественной, т.е. в данном случае эта операция выразима через операции суперпозициі Отсюда следует, что проблема полноты в К-значных логиках является частным случаем проблемы ^-полноты при t:= d. . Вместе с тем, при X-^Q. существует принципиальное различие между ф.с, элементами которой являются функции К-значных логик, с одной стороны, и.отображения, осуществляемые о.-д. функциями на слов; длины *с , с другой. Множество всех детерминированных отобрэжеш рассматриваемых на словах длины t: , порождает специальное зами тое подмножество в К-значной логике, существенно зависящее от двух параметров - параметра К и параметра t: . Используя есте< венную аналогию между проблемой ^-полноты и проблемой полноті в конечноиорождеиных замкнутых классах К -значной логики, моэ но ввести понятие 'С-предполного класса и показать, что всякое множество о.-д. функций является t-полным тогда и только Torj когда оно целиком не содержится ни в одном из t-предполных классов: совокупность 'с-предполных классов конечна, может бы описана эффективно и образует минимальную ^-критериальную систему; при этом множество d.-предполных классов изоморфно множеству предполных классов в К-значных логиках. Таким образом для любого t Ьd. существуют алгоритми для распознавания 'С-по. ноты конечных множеств о.-д. функций. Также, как и в К-значны: логиках, кавдый из этих алгоритмов может быть задан с использованием эффективно описываемых ^-критериальных систем, а наилу шиї из них получается на пути явного списания множества всех 1
- 7 -предиолннх классов.
Развитие теории итеративных ф.с. шло но пути изучения конкретных моделей ф.с, Е 1921г. Е.Постом была полностью описана структура замкнутых классов а двузначной логике. Это описание, изложенное в виде монографии в 1941 году, по-существу эквивалентно решению проблемы полноты для произвольных двузначных логик, в которых в качестве операций выступают операции суперпозиции /5/. Интерес к изучению итеративных ф.с. особенно возрос в начале 50-х годов в связи с появлением ЭВМ и необходимостью синтеза сложных кибернетических устройств. В Т9Б4 году П._ВЛ!бчснскмм /'.'/ била решена проблема полноты в трехзначной логике. Поело появления работы /3/ усилия многих авторов были сосредоточены на решении проб-лет полноты в произвольных Х-значных логиках /см. I и цитированную там литературу/. Начиная с 60-х годов наряду с К-зпачпыш логиками стачи интенсивно изучаться итеративные ф.с-, элементами которых являются автоматные отображения /I, 9,10,11/, функции счетнозначных логик /12,13/. Позже появились работы, связанные с изучением итеративных ф.с, содержащих в качестве элементов вычислимые функции /7.14,15/, программы и схемы программ /16,17/.
Накопление информации о свойствах конкретных моделей итеративных ф.с. поставило вопрос о выработке общего понятия ф.с, что было сделано в /I/. Суть подхода, изложенного в /I/, состоит в упомянутом выше разбиении множества всех итеративных ф.с. на lie-тиностные и последователъностные ф.с, а также в описании всех тех операций, которые индуцируют в итеративных Ф.с. операторы замыкания в точности совпадающие с множеством алгебраических операторов замыкания.
В наиболее обшей постновкв проблема полноты для о.-д, функций изучалась в работах 13 Л і. Кудрявцева /I/ и М. И. Кратко /11/.
В этих работах исследовался вопрос о существовании эффективного
Критерия ПОЛНОТЫ В Ро.-о- Следует ОТМеТИТЬ, ЧТО ф.С. fQ-q. являє
ся конечнопоровденной /1,2/ и, также как в К-значных логиках, множество всех предполных в Г5-», классов образует минимальную критериальную систему. Отсюда следует, что в принципе критерий полноты в *о-а, может быть сформулирован в терминах предполных классов. Однако, как показано В.Б.Кудрявцевым, мощность множест ва предполных в fg|_g# классов равна континууму и, таким образом, эффективного критерия полноты для о.-д. функций не существует. О этим согласуется результат М.И.Кратко, установившего отсутстн алгоритма распознавания полноты конечных систем о.-д.функций.
Негативные с точки зрения эффективности результаты по проб леме полноты для о.-д. функций в общем случае привели к тому, что различные авторы рассматривали некоторые модификации этой проблемы. Одни из них возникают на пути сужения класса систем, исследуемых на полноту, другие - на пути моделирования отдельны свойств о.-д. функций /2,10,18/.
В 1964 году Б.Б.Кудрявцев в качестве одной из наиболее важ ных и естественных модификаций проблемы полноты в /о.-ч. предлог рассматривать проблему чГ-полноты. Эта проблема, как отмечено выше, допускает эффективное решение, для всякого чг^.4. сущест вует алгоритм распознавания t-полноты конечных систем о.-д. фу цим, и каждую функцию, принадлежащую любой последовательностно ф.с, можно аппроксимировать отображениями, осуществляемыми о.-функциями на словах длины 'С .
Изложение части результатов по проблеме ^--полноты, связан ных с исследованием базисных чг-полных систем о.-д. функций, со держится в /2/. Проблема t-полноты для некоторых специальных систем о.-д. функций со специальным набором операций рассматрив
- 9 -лась в работах Ф.Гечвга, Б.Талъхайма, М.Пеака, 3.Ёжика, Г.Хорвата, Р.Дёмёши, Б.Имреха, И.Вираха и других авторов /19,20,21,22,' 23,24,25,26/.
С проблемой t-полнотн тесно связана
Проблема А-полноты /аппроксимационнок полноты/. Множество dfC~ Ri а называется А-полным, если для любого *С>-d. это мно-жество является tl-полннм. Проблема А-полноты состоит в описании А-полных подмножеств множества ч>.-г.
Проблема А-полкоты исследовалась в работах /27,29,30.31/. Оказалось, что эта проблема алгоритмически неразрешима. Тем не менее критерий А-полноты может быть сформулирован в терминах А-предполных классов, число А-предполных классов счётпо, множество А-предполных классов рекурсивно перечислимо, и каждый А-нредпол-ный класс может быть описан эффективно. Белес того, камші t-предполный класс является А-предполным классом к наоборот: для любого А-предпрлного класса существует чГ^гІ такое, что этот А-предаолный класс в то же время и t-предполоп. Отсюда следует, что проблема эффективного описания А-предполных классов сводатся к проблеме эффективного описания t-предполных классов для всех ^С^. Это позволяет вести поиск и находить примеры содержательных подклассов множества конечных систем о.-д. функций, для которых существует алгоритм для распознавания А-полноты /ЗІ/. В /30, ЗІ/ дано явное описание множества всех А-предполных /и, следовательно, f-предполннх/ классов в двузначном случае и установлена асимптотика их числа при Т-> оо . Там же на примере решения проблемы f-полноты дли мнояеотв, содержащих все одноместные о.-Д. функции, проиллюстрировано существенное различие между проблемой полноты в конечнозначннх логиках и проблемой tr-полно-ты для о.-д. функций.
Цель работ». Для любых К^ 1 ,^^ Дать явное в терминах сохранения отношений описание множества всех 'С-предполных классов и тем самым решить проблему ^-полноты для автоматов.
Научная новизна. В диссертации впервые для автоматов с прои вольным конечним алфавитом, отображающих слова заданной длины t рассматривается проблема полноты - проблема fc-полноты. Проблема t-нолнотн полностью решена: для любых /<^ 2 , *С-4 дано явное описание множества всех ^С-предполных классов. Это описание поз воляот указать, наилучший из возмолсных алгоритм для распознавания ^-полноты конечних систем автоматов и, таким образом, решать вопрос о возможности аппроксимации произвольных функций в итеративных функциональных системах.
Методы исследования. Для решения проблемы ^полноты для ав томатов использован аппарат сохранения функциями отношений /предикатов/. Аналогичный подход оказался весьма эффективным при опи оэшш множества преднолных классов в К-значных"логиках. Однако значительно более сложная структура автоматных отображений по сравнению с функциями К-значных логик во многом усложняет задачу и приводит к необходимости разработки новых методов для её решения. Каждое отношение, класс сохранения которого является t предполным, при ^^2. уде не просто совокупность наборов элементов множества Н«» а совокупность наборов слов, составленных из элементов 1Е"к, причем длины этих слов, вообще говоря, произвольны, но не превосходят t .
Аппробаиия диссертации. Результаты диссертации неоднокрап: докладывались на научно-исследовательских семинарах в МГУ, на Всесоюзных конференциях по математической кибернетике и матоматг ческой логике,на 3-ьем Всесоюзном семинаре по дискретной математике и ее приложениям, на Ломоносовских чтениях в МГУ, в Матема-
- II -
тическом центре им. С.Банаха в Варшаве, на международных конференциях в Германии, Словении, а такте на Кубе.
Структура и объем работы. Диссертация состоит из введения, одиннадцати параграфов и списіса .татературы. Библиография включает 84 наименования, в том числе 14 работ автора по теме диссертации. Полный объем диссертации - 329 страниц машинописного текста.