Проблема полноты для функциональных систем полинолов Дарсалия, Валерий Шотаевич

Введение к работе

Актуальность темы. Функциональная система представляет собой множество функций с некоторым набором операций, применяемых к этим функциям и приводящих к получению других функций из этого же множества.

Функциональные системы являются одним из основных объектов математической кибернетики и дискретной математики и отражают следующие главные особенности реальных и абстрактных управляющих систем: функционирование (в функциональных системах - это функции), правила построения более сложных управляющих систем из заданных и описание функционирования сложных систем по функционированию их компонент (последние два момента отражены в операциях функциональных систем).

Функциональные системы обладают определенной спецификой, состоящей в рассмотрении задач и подходов, возникающих при их исследовании с позиции математической кибернетики, математической логики и алгебры. Так, с позиции математической кибернетики функциональные системы рассматриваются как модели, описывающие функционирование сложных кибернетических систем; с позиции математической логики - как модели логик, т.е. как системы предложений с логическими операциями над ними; с позиции алгебры - как универсальные алгебры.

В качестве обобщений реальных функциональных систем могут в принципе рассматриваться и универсальные алгебры, однако, в этом случае теряются основные достоинства реальных функциональных систем и, прежде всего, такие, как конструктивность множеств и операций.

Содержательная связь функциональных систем с реальными кибернетическими моделями управляющих систем, с одной стороны, определяет серию существенных требований, которые накладываются на функциональные системы, а с другой стороны, порождает класс важных задач, имеющих как теоретическое, так и прикладное значение.

Проблематика функциональных систем обширна. К числу основных задач хтя функциональных систем относятся задачи о полноте и выразимости, о синтезе и анализе, о тождественных преобразованиях и другие.

Изучение проблемы полноты осуществлялось путем исследования конкретных модельных функциональных систем, среди которых одной из первых была изучена двузначная логика. Здесь основополагающие результаты были получены Е. Постом' в 1921 году. Им была полностью описана струк-

Post Е. Two-valued iterativeni systems of mathematical logik - Prinston. 1941.

тура замкнутых классов двузначной логики. Это описание по существу эквивалентно решенто задачи о полноте. Им же были сделаны шаги по изучению к-значных логик (к>2). В 1954 году СВ. Яблонским² была решена задача о пол-ноте в 3-значной логике. Решение было сведено к описанию всех предполны> классов в ней. Сами предлолные классы были описаны явно. Из этого описа ній вытекал алгоритм распознавания полноты для конечных систем функций Метод решения проблемы полноты в терминах предполных классов стал после этого одним из основных для функциональных систем. Особые усилия различ пых авторов были сосредоточены на решении проблемы полноты для ключе вой функциональной системы, которой является ^-значная логика. На этол пути окончательный результат был получен И. Розенбергом³ в 1970 году.

Интенсивно начали изучаться алгебры автоматов и, прежде всего, функ циональная система ограниченно-детерминированных (автоматных) функций Здесь важные результаты о полноте были получены В.Б. Кудрявцевым⁴.

Большой интерес представляет функциональная система вычислимы; функций, о чем свидетельствуют многочисленные работы таких математиков < мировым именем, как Д. Гильберт⁵, К. Гедель⁶ , К. Клини , А. Марков⁸ , А Тьюринг⁹ и т.д.

Наряду с этими функциональными системами начали интенсивно изучаться и другие важные функциональные системы и, прежде всего, функциональны!

системы недетерминированных функций, неоднородных функций и т.д.

" Яблонский СВ. О функциональной полноте в трехзначном исчислении!

ДАН СССР. - 1954. - Т.95, N 6. - С. 1153-1156.

³ Rosenberg J. Uber die functionate Vollstandigkeit in der mehnvertigei

logiken Rozpra\y CSAV, Rada mat. print., - 1970. - V.80, N 4.

^A Кудрявцев В.Б., Алешин СВ., Подколзин А.С. Введение в теории

автоматов. -М.: "Наука", 1986.

⁵ Hilbert D., Bernays P. Grundlagen der Mathematik. - Springer-Verlag
OHG. Berlin, 1939.

⁶ Go del K. Uber formal unentscheidbare SStze der Principia Mathematica un
Venvandier Systeme'-' Monatsh. Math, und Phys., -1931.- V.38 - P.173-198.

' Клини С К. Введение в метаматематику. - М.: "ИЛ", 1957.

⁸ Марков А.А. Теория алгоритмов. - В сб.: Труды математического инстг
тута АН СССР, - 1954. -Т.42.

⁹ Turing A. On computable numbers, with an application to the Entscheidungi
problem- Proc. London Math. Soc, ser. - 1936. - V.42, -P.230-265.

В настоящем работе рассматриваются следующие функциональные системы:

/*n - функциональная система полиномов с натуральными коэффициентами:

Fz - функциональная система полиномов с целыми коэффициентами;

Fq - функционаїьпая система полиномов с рациональными коэффициентами. где в качестве операций над полиномиальными функциями выступают операции суперпозиции. Для этих функциональных систем исследуется проблема полноты, а также порожденные ее решением задачи "функционального" характера, а именно, іпучение замкнутых и предполных классов, исследование базисов и т.д.

Для решения поставленных задач необходимо формализовать понятие суперпозиции функций. Существует несколько таких формализации, например, операции в итеративных алгебрах Поста, предложенные А.И.Мальцевым'⁰ , и операции в алгебрах Менгера" . Мы выбираем первый путь и с этой целью строим новые объекты: F_N, F_z. F_Q - итеративные алгебры полиномиальных функций, соответственно, с натлральными, целыми и рациональными коэффициентами.

Цель работы. Целью настоящей работы является исследование проблемы полноты для функциональных систем полиномов с натуральными, целыми и рациональными коэффициентами; более подробно, решение следующего крута вопросов:

1. Алгебраический вариант проблемы полноты для ф.с. F_x \

является ли множество всех предполных классов критериальной системой? найти мощность множества предполных классов.

1. Алгоритмический вариант проблемы полноты для ф.с. F_x; алгоритмически разрешима или нет проблема полноты ?

2. Задача о базисах яія ф.с. F_K;

имеет ли базис каждая полная система ?

существует ли алгоритм, выделяющий из произвольной конечной полной

¹⁰ Мальцев А. И. Итеративные алгебры и многообразия Постав Алгебра и логика. - 1%6. - Т.5. N 2. - С.5-24.

Whitlock H.J. A composition algebra for multiplace function ' Math. Ann., -1964.-V. 157. N 2.-P.167-178.

системы базис ?

4. Задача об универсальных функциях для ф.с. F_x : существует ли универсальная функция ? найти число универсальных функций.

5. Задача об относительной полноте для ф.с. F\:

найти условия полноты систем, содержащих все одночлены; существует ли алгоритм, распознающий образует ли произвольная конечная система функций вместе с множеством всех одночленов полную систему ? найти условия полноты систем, содержащих все функции одной переменной;

существует ли алгоритм, распознающий образует ли произвольная конечная система функций вместе с множеством всех функций одной переменной полную систему ?

6. О связи ф.с. F_N> F_z и F_Q;

найти глубину класса Рц в классе Рг- класса Р_г в классе Pq и класса Р^ в

классе P_Q;

задача об относительной полноте множеств в P_v относительно P_v для пар

(t/,Owwa(ZJV),(&Z)H (Q,N). (здесьXe{N,Z,Q}, а Рц, Рг и Pq - множества всех полиномиальных функций соответственно с натуральными, целыми и рациональными коэффициентами).

Замечание. Задачи об алгоритмической разрешимости проблемы полноты, о существовании алгоритма, выделяющего из произвольной конечной системы базис и о существовании универсальных функций ставится только для конечно-порожденных функциональных систем, т.е. для ф.с. F_N и F_z.

Методы исследования. В работе используются методы теории функциональных систем, теории алгоритмов. Также используются результаты алгебры и теории чисел.

Научная новизна. Результаты диссертации являются новыми и состоят в следующем:

В функциональной системе полиномов с натуральными коэффициентами:

1. Множество всех предполных классов является (приведенной) критери-

альной системой [следствие 1 теоремы 2.3.1];

2. Мощность множества всех предполных классов равна 4 [следствие 2

теоремы 2.3.1];

3. Проблема полноты алгоритмически разрешима [теорема 2.3.2];

4. Каждая полная система имеет баше, состоящий либо из трех, либо

и j четырех функций [теорема 2.4.11:

5. Существует алгоритм, который и з любой конечной полной системы

выделит ваше [теорема 2.4.2]; (у. Проблема выразимости алгоритмически разрешима |теорема 5.3.11.

В функциональной системе полиномов с целыми коэффициентами:

1. Множество всех предполиых классов является (приведенной) крите-

риальной системой [теорема 3.3.11:

2. Мощность множества всех предполиых кчассов равна с [теорема

3.3.2|:

3. Проблема полноты алгоритмически неразрешима |теорсма 3.3.3):

4. Каждая полная система имеет базис; более того, для любого поло-

жительного целого чисча п существует базис мощности п [теорема 3.4.1|:

5. Не существует алгоритм, который из любой конечной полной систе-

мы выделит базис [теорема 3.4.2]:

6. Существует счетное число универсальных функций [теорема 3.5.2]:

7. Проблема выразимости алгоритмически неразрешима |теорема 5.3.2]:

В функциональной системе полиномов с рациональными коэффициентами:

1. Множество всех предполиых классов является (приведенной) крите-

риальной системой [теорема 4.3.1];

2. Мощность множества всех предполиых классов равна с [теорема 4.3.2]:

3. Существует полная система, не имеющая базиса [теорема 4.4.1]:

4. Проблема выразимости алгоритмически неразрешима [теорема 5.3.3].

Теоретическая и практическая ценность.

Рассмотренные функциональные системы полиномов F_u, F₇ и F_Q играют ключевую роль в теории чисел, теории алгоритмов и теории функций. К изучению их свойств сводятся многие проблемы указанных разделов математи-

ки, такие как представление натуральных чисел в виде специальных полиномов (проблема Варинга) в теории чисел, описание рекурсивных множеств натуральных чисел, как областей значений полиномов в теории алгоритмов, как полиномиальные апроксимации гладких функций с помощью действительных полиномов (проблема Чебышсва) в теории функций и т.п. Большую роль свойства полиномов стали играть в вычислительной математике и технике, а также в теории нейронных сетей. Тем самым знания о природе выразимости одних полиномов через другие, а также предельно широкой выразимости, т.е. полноты полиномов могут пролить свет сразу на целую группу ключевых вопросов математики. В этом состоит теоретическое значение работы, находящейся на стыке разных направлений математики.

В узком смысле теоретическая значимость работы состоит в развитии теории функциональных систем как в плане охвата новых модельных объектов типа полиномов, так и в вычленении позитивных результатов типа алгоритмической разрешимости, а также в отсечении негативных ситуаций, когда указанных разрешимостей нет.

Практическая направленность работы обусловлена возможными приложениями в синтезе нейронных сетей и вычислительных чипов.

Полученные результаты могут быть использованы как в научной работе, так и в разработке учебных курсов.

Апробация. Результаты диссертации докладывались и обсуждались на семинарах по теории автоматов механико-математического факультета Московского государственного университета им. М.В. Ломоносова (руководитель семинара академик В.Б. Кудрявцев).

Публикации. Основные результаты диссертации опубликованы в работах автора, список которых приведен в конце автореферата.

Структура и объем диссертации. Диссертация состоит из предисловия, 5 глав и списка литературы. Текст диссертации изложен на 116 страницах. Список литературы содержит 32 наименование.