Решение проблемы отделимости алгоритмически разрешимых случаев А-полноты для базисов поста дефинитных автоматов

Жук, Дмитрий Николаевич

Решение проблемы отделимости алгоритмически разрешимых случаев А-полноты для базисов поста дефинитных автоматов тема автореферата и диссертации по математике, 01.01.09 ВАК РФ

Жук, Дмитрий Николаевич АВТОР

кандидата физико-математических наук УЧЕНАЯ СТЕПЕНЬ

Москва МЕСТО ЗАЩИТЫ

2009 ГОД ЗАЩИТЫ

01.01.09 КОД ВАК РФ

Диссертация по математике на тему «Решение проблемы отделимости алгоритмически разрешимых случаев А-полноты для базисов поста дефинитных автоматов»

Автореферат диссертации на тему "Решение проблемы отделимости алгоритмически разрешимых случаев А-полноты для базисов поста дефинитных автоматов"

004603168

МОСКОВСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ ИМЕНИ М.В. ЛОМОНОСОВА

МЕХАНИКО-МАТЕМАТИЧЕСКИЙ ФАКУЛЬТЕТ

На правах рукописи УДК 519.71

Жук Дмитрий Николаевич РЕШЕНИЕ ПРОБЛЕМЫ ОТДЕЛИМОСТИ АЛГОРИТМИЧЕСКИ РАЗРЕШИМЫХ СЛУЧАЕВ Л-ПОЛНОТЫ ДЛЯ БАЗИСОВ ПОСТА ДЕФИНИТНЫХ АВТОМАТОВ

01.01.09 — дискретная математика и математическая кибернетика

АВТОРЕФЕРАТ диссертации на соискание учёной степени кандидата физико-математических наук

С/

- 3 ИЮН 2010

МОСКВА - 2010

004603168

Работа выполнена на кафедре Математической теории интеллектуальных систем Механико-математического факультета Московского государственного университета имени М.В. Ломоносова.

Научный руководитель — доктор физико-математических наук, профессор

Кудрявцев Валерий Борисович

Официальные оппоненты:

доктор физико-математических наук, профессор Гашков Сергей Борисович

кандидат физико-математических наук, доцент Карташов Сергей Иванович

Ведущая организация — Учреждение Российской Академии Наук

Вычислительный центр им. A.A. Дородницына

Защита диссертации состоится 4 июня 2010 г. в 16 ч. 45 м. на заседании диссертационного совета Д.501.001.84 при Московском государственном университете им. М.В.Ломоносова по адресу: Российская Федерация, 119991, Москва, ГСП-1, Ленинские горы, д.1, Московский государственный университет имени М.В. Ломоносова, Механико-математический факультет, аудитория 14-08.

С диссертацией можно ознакомиться в библиотеке Механико-математического факультета МГУ имени М.В. Ломоносова (Главное здание, 14 этаж).

Автореферат разослан 4 мая 2010 г.

Ученый секретарь диссертационного совета Д.501.001.84 при МГУ доктор физико-математических наук, профессор

А.О.Иванов

Общая характеристика работы Актуальность темы

Понятие автомата относится к числу важнейших в математике. Оно возникло на стыке разных её разделов, а также в технике, биологии и других областях. Содержательно автомат представляет собой устройство с входными и выходными каналами. На его входы последовательно поступает информация, которая перерабатывается им с учётом строения этой последовательности и выдается через выходные каналы. Эти устройства могут допускать соединение их каналов между собой. Отображение входных последовательностей в выходные называют автоматной функцией, а возможность получения новых таких отображений за счёт соединения автоматов приводит к алгебре автоматных функций.

Первый толчок к возникновению теории автоматов дала работа Э. Поста 1921 года1. В ней были получены фундаментальные результаты о строении решетки замкнутых классов булевых функций. В дальнейшем эти результаты были переработаны и упрощены в книге?. Сами автоматы и их алгебры начали исследоваться в тридцатые годы двадцатого века, но особенно активно в период с 50-х годов.

Основополагающую роль здесь сыграли работы Тьюринга, Мура, Кли-ни, а также многочисленные статьи, опубликованные в знаменитом сборнике «Автоматы» 3 под редакцией Шеннона и Маккарти. В одной из работ данного сборника впервые встречается понятие дефинитного события и дефинитного автомата4. Дефинитные автоматы — это все автоматные функции, которые можно получить из задержек и булевых функций с помощью операции суперпозиции. Впервые дефинитные автоматы были систематически исследованы в работе5.

Последующие работы по изучению алгебр автоматных функций велись под большим влиянием известных статей А.В.Кузнецова6,7 и

'Е. Post. Two-Valued Iterative Systems of Mathematical Logic. Princeton Univ. Press, Princeton, 1941.

'Яблонский C.B., Гаврилов Г.П.,Кудрявцев В.Б. Функции, алгебры логики и классы Поста. Наука, Москва, 1966.

3 Automata Studies, ed. by C.E. Shannon and J. Mc Carthy. Princeton, Î956 (русский перевод: Сборник статей под редакцией Шеннона и Маккарти. ИЛ, Москва, 1956.)

4Kleene S. С. Representation of events in nerve nets and finite automata. Automata Studies, ed. by C.E. Shannon and J. Mc Carthy. Princeton, 1956, 3-41.

5M. Perles, M.O. Rabin, E. Shamir. Theory of definite automata. IEEE Trans, on Electronic Computers, EC-IS (196S), 233-243.

'Кузнецов А. В. О проблемах тождества u функциональной полноты для алгебраических систем. Труды третьего всесоюзного математического съезда. Т. 2. Москва. Изд. АН СССР, 1956, с.145-146.

'Кузнецов А. В. Структуры с замыканием ti критерии функциональной полноты. Успехи матема-

С. В. Яблонского8 по теории функций /с-значной логики. Возникшие для таких функций постановки задач о выразимости, полноте, базисах, решётке замкнутых классов, а также развитый аппарат сохранения предикатов оказались весьма действенными и для алгебр автоматных функций. При этом под выразимостью понимается возможность получения функций одного множества через функции другого с помощью заданных операций, а под полнотой — выразимость всех функций через заданные.

Основу результатов для функций fc-значной логики составляет подход А.В.Кузнецова, опирающийся на понятие предполного класса. Для конечно-порождённых систем таких функций семейство предполных классов образует критериальную систему: произвольное множество является полным тогда и только тогда, когда оно не является подмножеством ни одного предполного класса. Множество предполных классов оказалось конечным и из их характеризации вытекает алгоритмическая разрешимость задачи о полноте. На этом пути С. В. Яблонским путем явного описания всех предполных классов была решена задача о полноте для функций трехзначной логики, а вместе с А. В. Кузнецовым найдены отдельные семейства предполных классов для логики произвольной конечной значности. Затем усилиями многих исследователей?'10,11'12 последовательно были открыты другие семейства предполных классов. Заключительные построения провел Розенберг в 1970 году13. При этом все предполные классы были описаны как классы сохранения отношений или предикатов.

Одновременно с изучением функций fc-значной логики были сделаны попытки применения аппарата предполных классов в задаче о полноте для автоматов. Сначала В. Б. Кудрявцев14 эффективно решил задачу о полноте и её модификациях для функций с задержками. После этого им был получен фундаментальный результат негативного характера: континуаль-

тических наук. Т. 16, №2, 1961, с.201-202.

8 Яблонский С. В. Функциональные построения в k-значной логике. Труды математического института им. В.А. Стеклова. АН СССР, 1958, T. 51.С.5-142.

®Ло Чжу-Кай, Лю Сюй Хуа. Предполные классы, определяемые бинарными отношениями в многозначной логике. Acta Sex. Natur. Univ. Jilinensis, 1963, Ж.

'"Захарова Е.Ю. Критерий полноты для системы функций из Ръ. Проблемы кибернетики. 1967, №18, с.5-10.

1]Маргьшкж В. В. Исследование некоторых классов функций в многозначных логиках. Проблемы кибернетики. 1960, №3, с.49-60.

12Пан Юн-Цзе. Один разрешающий метод для отыскания всех предполных классов в многозначной логике. Acta Sei. Natur. Univ. Jilinensis, 1963, №3.

"Rosenberg J. La structure des fonctions de plusiers variables sur un ensemble fini. Comptes Rendus Acad. Sei. Paris, 1965 №260, c.3817-3819.

"Кудрявцев В. Б. Теорема полноты для одного класс автоматов без обратных связей. Проблемы кибернетики. 1962, №8, с. 91-115. // ДАН СССР. 1963. Т. 151. № 3. С. 493-496.

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

Ситуация не улучшается, если вместо автоматных функций рассматривать дефинитные автоматы. Автору удалось показать, что в классе дефинитных автоматов континуум предполных классов[4]. В. А. Буевич показал, что в классе дефинитных автоматов задача о полноте относительно операции суперпозиции алгоритмически неразрешима17.

В силу своего определения автоматные функции и дефинитные автоматы являются бесконечнозначными и даже континуумзначными функциями. Тем самым полагается, что вычисляющие эти функции автоматы «работают» бесконечно долго. Однако совершенно ясно, что каждое реальное кибернетическое устройство по истечении некоторого конечного промежутка времени прекращает свою «работу» , то есть либо становится ненужным, либо переходит в начальное состояние. В связи с этим возникает проблема r-полноты. Множество M называется r-полным, если для любого дефинитного автомата / с помощью операций суперпозиции из множества M можно получить дефинитный автомат /', совпадающий с / на всех наборах, составленных из слов длины т.

В работах18'19 показано, что для решения проблемы т-полноты операция обратной связи является несущественной, так как в данном случае эта операция выразима через операцию суперпозиции. Отсюда следует, что проблема r-полноты для г = 1 по сути является проблемой полноты в ко-нечнозначных логиках. Вместе с тем при т > 2 существует принципиальное отличие между этими задачами. Множество всех детерминированных отображений на словах длины т порождает специальное замкнутое подмножество в конечнозначной логике, существенно зависящее от параметра г. Используя естественную аналогию между проблемой т-полноты и полноты в конечнопорождённых замкнутых классах конечнозначных логик, можно ввести понятие т-предполного класса. Так как для проблемы т-полноты

15Кудрявцев В. Б. О мощностях множеств предполных классов некоторых функциональных систем, связанных с автоматами // ДАН СССР. 1963. Т. 151. № 3. С. 493-496.

16Кратко М. И. Алгоритмическая неразрешимость проблемы распознавания полноты для конечных автоматов. Москва, ДАН СССР, 1964, т. 155.

17Буевич В. А., Клиндухова Т. Э. Об алгоритмической неразрешимости задач об А-полноте и полноте для дефинитных ограниченно-детерминированных функций. Москва, Математические вопросы кибернетики. Вып. 10. 2001.

"Кудрявцев В.В., Алешин C.B., Подколзин A.C. Введение в теорию автоматов. Наука, Москва, 1985.

18Буевич В. А. Условия А-полноты для конечных автоматов, ч.1, ч.2 Издательство МГУ, 1986,1987

г.г.

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

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

С проблемой т-полноты тесно связана проблема А-полноты. Множество М называется А-полным, если оно является т-полным для любого т. Из определения понятия А-полноты следует, что произвольный дефинитный автомат / можно «аппроксимировать» дефинитными автоматами, принадлежащими замыканию А-полного множества М. То есть можно выбрать последовательность дефинитных автоматов

/ъ /¡2) • ■ • j /г> • • •

такую, что для любого т > 1 дефинитный автомат fT совпадает с / на всех наборах, составленных из слов длины т.

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

Проблема A-полноты подробно исследовалась в работах В. А. Буевича. Оказалось, что эта проблема алгоритмически неразрешима, как для автоматных функций21, так и для дефинитных автоматов22. Тем не менее, критерий полноты может быть сформулирован в терминах А-предполных классов; число А-предполных классов счётно, множество А-предполных

20Буевич В. А. Условия А-полноты для конечных автоматов, ч. 1, ч.2 Издательство МГУ, 1986,1987.

21Буевич В. А. Об алгоритмической неразрешимости распознавания А-полноты для о.д.-функций // Математический заметки. Т. 12, №6. 1972. С. 687-697.

22Буевич В. А., Клиндухова Т. Э. Об алгоритмической неразрешимости задач об А-полноте и полноте для дефинитных ограниченно-детерминированных функций. Москва, Математические вопросы кибернетики. Вып. 10. 2001.

классов рекурсивно перечислимо и каждый предполный класс может быть описан эффективно23. Более того, каждый т-предполный класс является Л-предполным и наоборот: для любого Л-предполного класса существует г > 1, такое что этот Л-предполный класс является в тоже время т-предполным.

Алгоритмически разрешимые случаи возникают при ограничении класса проверяемых систем. Так, А. А. Часовских24 описал в классе линейных автоматов все предполные классы, число которых оказалось счётным, и нашел, тем не менее, алгоритм распознавания полноты конечных систем. Для каждой конечной системы М автоматов он заключается в проверке непринадлежности М конечному числу предполных классов. То есть для произвольной конечной системы удаётся выделить конечную критериальную систему предполных классов. Тальхальм25 установил свойства решетки замкнутых классов одноместных стабильных автоматов. К. В. Коляда?6 в 1984 году рассматривал классы функций, определённых на регулярных множествах (функции, сопряженные к автоматным) и обнаружил для одних классов алгоритмическую неразрешимость, а для других алгоритмическую разрешимость проблемы полноты.

Ещё в 1961 г. А. А. Летичевским27 был получен алгоритм решения задачи о полноте для конечных систем автоматов, выдающих номер своего состояния (автоматов Медведева) при наличии всех булевых функций. В 1986 году В. А. Буевич28 показал алгоритмическую разрешимость проблемы Л-полноты для систем автоматов, содержащих все булевы функции. В 1992 году Д. Н. Бабин29 доказал, что существует алгоритм распознавания полноты системы автоматных функций при наличии в рассматриваемой системе всех булевых функций. Автору удалось получить аналогичные результаты для дефинитных автоматов, а именно: показать, что для систем дефинитных автоматов вида и и существует алгоритм проверки на полноту и Л-полноту таких систем дефинитных автоматов[1]. Для каждого конечного V он заключается в проверке непринадлежности V конечному чис-

23Буевич В. А. Условия А-полноты для конечных автоматов, \.1, ч.2 Издательство МГУ, 1986,1987.

24Часовских А. А. О полноте в классе линейных автоматов. Математические вопросы кибернетики. Вып. 3. 1995, с. 140-166.

25Тальхайм Б. О. О решетке замкнутых классов стабильных автоматов. Методы и системы диагностики. Вып. 1, Саратов, 1979.

26Коляда К. В. О полноте регулярных отображений. Проблемы кибернетики. Вып. 41. М. Наука, 1980., с.41-49.

27Летичевский А. А. Условия полноты для конечных автоматов. Вычислительная математика и математическая физика, №4, 1961, с.702-710.

28Вуевич В. А. Условия А-полноты для автоматов. М.: Изд-во МГУ, 1986. // Математический заметки. Т. 12, №6. 1972. С. 687-697.

29Бабин Д, Н. Разрешимый случай задачи о полноте автоматных функций. Москва, Дискретная математика, 1992. Т. 4, вып. 4. С. 41-56.

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

Учитывая эти результаты, естественно исследовать на А-полноту и полноту системы вида Р и I/, где Р — некоторый замкнутый класс булевых функций или класс Поста, а V — конечная система дефинитных автома-тов(автоматных функций). Такие системы мы будем называть автоматными базисами Поста — также, как это делал Д. Н. Бабин в своих работах. Возникает разделение классов Поста на сильные и слабые по их способности гарантировать разрешимость проблемы А-полноты и полноты. Для автоматных функций данную задачу решил Д. Н. Бабин. Ему удалось расслоить классы Поста на те, для которых проблемы полноты и А-полноты для систем автоматных функций вида Ри V разрешимы, и те, для которых эти проблемы неразрешимы. Оказалось, что проблемы полноты и А-полноты для систем вида Рим разрешимы точно тогда, когда Р содержит либо функцию х + у + г, либо функцию ху V у г V хг30.

Автор исследовал на А-полноту и полноту системы вида Р и и, где Р — некоторый класс Поста, а V — конечная система дефинитных автоматов.

Цель работы

В работе исследуются на А-полноту системы вида Р и и, где Р — некоторый класс Поста, а и — конечная система дефинитных автоматов. Целью работы является расслоение всех классов Поста на те, для которых проблема А-полноты для таких систем автоматов алгоритмически разрешима, и те, для которых указанная проблема алгоритмически неразрешима.

Структура и объем диссертации

Диссертационная работа изложена на 91 странице и состоит из «введения», «основных понятий и результатов» и трех глав. Библиография включает 45 наименований.

30Бабин Д. Н. О классификации автоматных базисов Поста по разрешимости свойств полноты и А-полноты // Доклады Академии наук. №4. Т. 367. 1999. С. 439-441

Научная новизна

1. Решена проблема отделимости алгоритмически разрешимых случаев А-полноты для базисов Поста дефинитных автоматов. А именно, исследовались на Л-иолноту системы вида F и и, где Р — некоторый класс Поста, а и — конечная система дефинитных автоматов. Удалось расслоить классы Поста на те, для которых проблема Л-полноты для таких систем автоматов алгоритмически разрешима, и те, для которых указанная проблема алгоритмически неразрешима (см. рис.). Было доказано, что проблема А-полноты для систем дефинитных автоматов вида Р и и разрешима точно тогда, когда Р содержит одну из следующих функций: х\ + Х2 + Хз,

Х!Х2 V Х2Х3 V Х1Х3,

Х1Х2Х3 V Х1Х2Х4 V Х1Х3Х4 V Х2Х3Х4, Х1Х2 V Х1Х3 V Х1Х4 V Х2Х3 V Х2Х4 V Х3Ж4.

2. Для решения данной проблемы была разработана специальная предикатная техника. Она позволила для конкретных классов Поста выделять узкие множества А-предполных классов, необходимых для проверки на А-полноту.

Основные методы исследования

В диссертации использованы методы структурной теории автоматов, алгебры и теории алгоритмов.

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

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

Апробация работы

Результаты диссертации неоднократно докладывались на семинарах механико-математического факультета МГУ им. М.В. Ломоносова «Теория автоматов» (2005-2010 гг.) и «Кибернетика и информатика» (2005-2010 гг.) под руководством академика В. Б. Кудрявцева.

Также результаты докладывались на следующих конференциях:

• международные научные конференции студентов, аспирантов и молодых ученых «Ломоносов» (Москва, МГУ им.М.В.Ломоносова, 2007, 2008, 2009 и 2010 гг.);

• IX международный семинар «Дискретная математика и её приложения», посвященный 75-летию со дня рождения академика О. Б. Лупанова;

• научные конференции «Ломоносовские чтения» (Москва, МГУ им. М.В. Ломоносова, 2007, 2008 и 2009 гг.);

• международная конференция «Интеллектуальные системы и компьютерные науки» (Москва, МГУ им. М.В. Ломоносова, 2006г.);

• третья научная конференция студентов и аспирантов кафедры МаТИС механико-математического факультета МГУ (Москва, МГУ им. М.В. Ломоносова, 2007г.).

Публикации по теме диссертации

Основные результаты работы опубликованы в статьях [1]-[5].

Краткое содержание работы

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

Автор исследовал на полноту и А-полноту системы дефинитных автоматов вида Е и V, где ^ — некоторый класс Поста, а и — конечная система дефинитных автоматов. Для проблемы А-полноты удалось отделить разрешимые случаи от неразрешимых. Оказалось, что проблема А-полноты для систем дефинитных автоматов вида FU^, разрешима точно тогда, когда Р1 содержит либо функцию х + у + г, либо функцию хуУугУ хг, либо функцию

Х1Х2Х3 V Х1Х2Х4 V Х1Х3Х4 V 3:22:3X4,

либо функцию

Х\Х2 V Х\Х$ V £1X4 V х2Хз V Ж2Х4 V Х3Х4.

В результате на диаграмме Поста (см. рис.) появилась явная граница, отделяющая разрешимые случаи от неразрешимых.

проблемы А-полноты оказывается несущественной, результаты, полученные для дефинитных автоматов, отличаются от результатов, полученных для автоматных функций Д. Н. Бабиным. Так, для классов Ff, где i = 1,2,..., 8, проблема А-полноты для систем автоматных функций алгоритмически неразрешима, а проблема А-полноты для систем дефинитных автоматов алгоритмически разрешима. В то же время, можно показать, что если для класса Поста F проблема А-полноты для систем автоматных функций вида F U v разрешима, то она разрешима и для аналогичных систем дефинитных автоматов.

Метод доказательства алгоритмической разрешимости принципиально отличается от метода доказательства неразрешимости. В разрешимом случае для каждой конечной системы дефинитных автоматов строится конечная критериальная система, состоящая из предполных классов. Все пред-полные классы описываются как классы сохранения отношений, поэтому принадлежность этим предполным классам легко проверяется. Для слабых классов Поста из счетного множества А-предполных классов не удается выделить конечное подмножество классов, являющееся критериальной системой. Более того, удается свести проблему А-полноты к известной алгоритмически неразрешимой проблеме — проблеме конечности последовательности продукций Поста.

Воспользуемся обозначениями Эмиля Поста31. Для ц>2

/1+1

hn(xi, ®2, • • •, ¡Vu) = V XlX2 • • • ^«-i^i+i • • • хр+ъ ¿=1

/г* — функция, двойственная к h^. В частности

h2{xi,X2, Хз) = XiX2 V Х2Х3 V Х1Х3.

= Ш], Fi = [{Лз}], D2 = [{h2}}, U = [{x + y + z}], Ft = [{xVy}], Fi° = [{хЩ}, Se = {{x Vy,0,l}], P6 = [{xky, 0,1}], 09 = [{z,0}], FÏ = [{a; V y, Л4}], F84 = [{x&y, ft.4}].

Как было сказано выше, автор доказал, что проблема А-полноты для систем вида F U v алгоритмически разрешима тогда и только тогда, когда Jh Я F, Li С F, F$ ç F, либо F63 ç F.

Легко убедиться, что если F' Ç F и проблема А-полноты алгоритмически неразрешима для систем вида F U и, то она алгоритмически неразрешима и для систем вида F' U v. Аналогично, если F Ç F' и проблема А-полноты алгоритмически разрешима для систем видами!/, то она алгоритмически разрешима и для систем вида F' U v. Также, если F* — класс,

31Е. Post. Two-Valued Iterative Systems of Mathematical Logic. Princeton Univ. Press, Princeton, 1941.

двойственный к Р относительно замены 0 на 1, то проблема А-полноты для систем вида Р и и, алгоритмически разрешима тогда и только тогда, когда алгоритмически разрешима проблема А-полноты для систем вида Р* и и. А значит, для доказательства указанной классификации достаточно рассмотреть только граничные случаи и только левую половину диаграммы Поста. То есть, достаточно доказать неразрешимость для классов^4, Р§ и Од, и разрешимость для классов £>2, £4, р2-

В основных понятиях и результатах строго определяются необходимые понятия и формулируются основные результаты. Пусть Р — замкнутый класс булевых функций. Определим проблему А-ПОЛНОТА(^): дана конечная система V дефинитных автоматов; требуется установить, А-полна ли система Р1 и V.

В трех главах работы доказываются следующие три теоремы.

Теорема 1. ¡3] Проблема А-ПОЛНОТА(Р) алгоритмически разрешима для каждого Р е р£, £>2, £4}.

Теорема 2. [2] Проблема А-ПОЛНОТА(Р) алгоритмически неразрешима для каждого Р € {5б, Р&, Од}.

Теорема 3. [5] Проблема А-ПОЛНОТА(Р) алгоритмически неразрешима для каждого Р € {Р$,

Эти три теоремы позволяют все классы Поста разделить на сильные и слабые по их способности гарантировать разрешимость проблемы А-полноты для дефинитных автоматов. Таким образом, может быть сформулирована

Теорема 4. Проблема А-ПОЛНОТА(Р) алгоритмически разрешима тогда и только тогда, когда для какой-то / € {/12, х + у + г, /13, /13} выполняется f £ Р.

Первая глава посвящена разрешимым случаям проблемы А-полноты, в ней доказывается теорема 1, сформулированная выше. Как уже указывалось, достаточно рассмотреть только граничные случаи, а именно:

¿4, Ре - Для каждого из них строится несколько счётных семейств А-предполных классов, которые образуют критериальную систему. Затем для каждой конечной системы дефинитных автоматов из каждого семейства выделяется конечное множество А-предполных классов. Каждый А-предполный класс описывается как класс сохранения отношения. Так как мы рассматриваем только системы, содержащие £>2, ¿4, Р^ шш то нас

интересуют не все Л-предполные классы32, а только те, которые содержат все функции из £>2, ¿4, ¿2, или ^д. В работе встречаются унарные, бинарные отношения, а также отношения арности 4. Любопытно, что самая большая сложность возникает с унарными отношениями. Более того, именно унарные отношения строятся для доказательства неразрешимости во второй и третьей главе.

Ранее упоминалось, что разрешимость проблемы Л-полноты для систем Дгии и 1/4иг/ можно вывести как следствие из результатов Д. Н. Бабина33, полученных для автоматных функций. Но автор приводит своё доказательство этих фактов в работе, так как в процессе доказательства демонстрируется общий подход к решению такого рода задач, а именно, показывается, как наличие соответствующих функций без памяти ограничивает множество унарных отношений, которые необходимо рассматривать. Такое ограничение позволяет для каждой конечной системы дефинитных автоматов из счётного множества Л-предполных классов выделять конечное множество. Именно такой подход позволяет решать задачу об Л-полноте для классов , где г = 1,2,..., 8, хотя для автоматных функций данная задача алгоритмически неразрешима. К тому же, по мнению автора, описание Л-предполных классов и их ограничений, необходимых для решения задачи об Л-полноте при наличии классов Д; или ¿4, имеет самостоятельную ценность.

Во второй главе рассматриваются простейшие неразрешимые случаи, а именно: 5е, -Ре и Од, и доказывается теорема 2. Как было сказано выше, неразрешимость сводится к проблеме конечности последовательности продукций Поста. Тройка в = (£),р,ш), где Б = {<¿1,^2,• ••> И* — множество слов в алфавите £>, р : О -> £>*, р(с^) = Я,-, ш — натуральное число, называется системой однородных продукций Поста. Если / > ш, то скажем, что в применима к слову £ = <1^(1^... <1ц и слово в(£) = ... с^Я^ назовём результатом применения в к слову По-

следовательность £ь£2.£з!••• > такую что £1 = а £¿+1 = назовём

последовательностью продукций Поста слова Последовательность продукций конечна, если последнее слово имеет длину меныдуюш. Известно34, что существует система однородных продукций Поста, для которой не существует алгоритма, по слову £ решающего вопрос о конечности последовательности продукций слова Эта система продукций Поста (В, р, и)) фик-

32Бусвич В. А. Условия А-полноты для конечных автоматов, ч.1, ч.2. Издательство МГУ, 1986, 1987 г.г.

33Бабин Д. Н. О классификации автоматных базисов Поста по разрешимости свойств полноты и А-полноты // Доклады Академии наук. №4. Т. 367. 1999. С. 439-441

34Мальцев А. И. Алгоритмы и рекурсивные функции. Наука, Москва, 1986.

сируется. После этого продукции Поста специальным образом кодируются словами в алфавите {0,1}. Для каждого слова £ строятся параметрические системы дефинитных автоматов:

Ех = {х V у, О,1, \¥0, Со, ТиТ2,..., Тк, Т(}

Е2 = {х, О, Со, ТиТ2,..., Тк, Т6}.

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

Следует заметить, что доказательство существенно отличается от доказательства аналогичных утверждений для автоматных функций. В отличие от автоматных функций не существует дефинитных автоматов, не зависящих от входа, которые бы выдавали периодическую последовательность на выходе. А значит мы не можем в каждый момент времени находить начала частей, которые получились при кодировании продукций. Для корректного «чтения» и «преобразования» продукций метод кодирования продукций существенно усложняется. Есть ещё одно существенное отличие доказательств для автоматных функций и дефинитных автоматов. При некорректном использовании автоматной функции, она запоминает «ошибку» и во все последующие моменты уже не работает корректно. Дефинитный автомат забывает любую информацию через определённое число шагов. А значит даже после некорректного использования дефинитный автомат начнёт работать как и раньше. Это тоже значительно усложняет конструкцию, так как приходится следить, чтобы «ошибка», возникшая в какой-то момент времени, не могла исчезнуть.

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

В третьей главе рассматривается самый сложный неразрешимый случай, а именно рассматриваются классы и и доказывается теорема 3. Техника доказательства неразрешимости сильно отличается от техники доказательства во второй главе. И хотя задача опять решается сведением к проблеме конечности последовательности продукций Поста, отличие настолько существенно, что доказательство выделено в отдельную главу. В

отличие от доказательства во второй главе, где используются специальные дефинитные автоматы, с помощью которых можно из одного элемента последовательности продукций построить следующий элемент последовательности, в данном случае вся последовательность продукций сначала кодируется специальным образом с помощью нулей и единиц, а потом только проверяется, что последовательность записана корректно. Ещё больше усложняется конструкция, позволяющая выделять части, которые получились при кодировании продукций. Суть этой конструкции заложена в определении унарного отношения, которое сохраняется в случае, если последовательность продукций конечна. Одно из принципиальных отличий доказательства в этой главе от доказательства во второй главе заключается в следующем. Во второй главе автоматы строились таким образом, что «ошибка», возникшая в какой-то момент времени, не могла исчезнуть, а оставалась записанной в сверхслове. Наличие же функций кц для ц > 4 делает это невозможным. Специальным образом подобрав слова, всегда можно избавиться от «ошибки», записанной на сверхслове. Для этого достаточно проследить, чтобы «ошибки» в разных сверхсловах были в далёкие друг от друга моменты времени. Для решения данной проблемы был придуман новый подход, в котором такого понятия, как «ошибка» уже нет. В процессе доказательства мы сразу строим автоматы так, чтобы они сохраняли сложное унарное отношение.

Благодарности

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

Работы по теме диссертации

[1] Жук Д. Н., Присмотров Ю. Н. О проблеме полноты в классе автоматов без обратной связи. Москва, Интеллектуальные системы, т. 11, 2007, с. 439472. (Жуку Д. Н. принадлежит описание семейств 05, 2), и <£ пред полных классов, доказательство пунктов 2, 4, 5, 6 теоремы 1, а также доказательство теоремы 2).

[2] Жук Д. Н. О неразрешимости проблемы полноты для дефинитных автоматов. Москва, Интеллектуальные системы, т. 12, 2008, с. 211-228.

[3] Жук Д. Н. Разрешимые случаи задачи об А-полноте для дефинитных автоматов. Москва, Интеллектуальные системы, т. 13, 2009, с. 273-312.

[4] Жук Д. Н. Континуальность множества предполных классов в классе дефинитных автоматов. Москва, Интеллектуальные системы, т. 13, 2009, с. 41-48.

[5] Жук Д. Н. О классификации автоматных базисов Поста по разрешимости свойств А-полноты для дефинитных автоматов. Москва, Дискретная математика, 2010. Вып. 2. с. 41-56.

Подписано в печать 29. ОЦ. 2010 Формат 60x90 1/16. Усл. печ. л. 4,25 Тираж {ОО экз. Заказ 26

Отпечатано с оригинал-макета на типографском оборудовании механико-математического факультета МГУ имени М. В. Ломоносова

Содержание диссертации автор исследовательской работы: кандидата физико-математических наук, Жук, Дмитрий Николаевич

Введение

Основные понятия и результаты

1 Разрешимые случаи проблемы Л-полноты

1.1 Основные утверждения.

1.2 Доказательство утверждений.

2 Неразрешимость проблемы Л-полноты для классов 5б, Ре, Од

2.1 Основные утверждения.

2.2 Доказательство утверждений . ;.

3 Неразрешимость проблемы Л-полноты для классов ^, ^

3.1 Основные утверждения.

3.2 Доказательство утверждений.

Введение диссертация по математике, на тему "Решение проблемы отделимости алгоритмически разрешимых случаев А-полноты для базисов поста дефинитных автоматов"

Первый толчок к возникновению теории автоматов дала работа Э. Поста 1921 года [1]. В ней были получены фундаментальные результаты о строении решетки замкнутых классов булевых функций. В дальнейшем эти результаты были переработаны и упрощены в [8]. Сами автоматы и их алгебры начали исследоваться в тридцатые годы двадцатого века, но особенно активно в период с 50-х годов.

Основополагающую роль здесь сыграли работы Тьюринга, Мура, Кли-ни, а также многочисленные статьи, опубликованные в знаменитом сборнике «Автоматы» [2] под редакцией Шеннона и Маккарти. В одной из работ данного сборника впервые встречается понятие дефинитного события и дефинитного автомата [3]. Дефинитные автоматы — это все автоматные функции, которые можно получить из задержек и булевых функций с помощью операции суперпозиции. Впервые дефинитные автоматы были систематически исследованы в [4]. Некоторые свойства дефинитных автоматов изучались в [5, 6, 7].

Последующие работы по изучению алгебр автоматов велись под большим влиянием известных статей А. В. Кузнецова [9, 10] и С. В. Яблонского [11] по теории функций &-значной логики. Возникшие для таких функций постановки задач о выразимости, полноте, базисах, решётке замкнутых классов, а также развитый аппарат сохранения предикатов оказались весьма действенными и для алгебр автоматных функций. При этом под выразимостью понимается возможность получения функций одного множества через функции другого с помощью заданных операций, а под полнотой — выразимость всех функций через заданные.

Основу результатов для функций /с-значной логики составляет подход A.B. Кузнецова, опирающийся на понятие предполного класса. Для конечно-порождённых систем таких функций семейство предполных классов образует критериальную систему: произвольное множество является полным тогда и только тогда, когда оно не является подмножеством ни одного предполного класса. Множество этих предполных классов оказалось конечным и из их характеризации вытекает алгоритмическая разрешимость задачи о полноте. На этом пути C.B. Яблонским путем явного описания всех предполных классов была решена задача о полноте для функций трехзначной логики, а вместе с А. В. Кузнецовым найдены отдельные семейства предполных классов для логики произвольной конечной значно-сти. Затем усилиями многих исследователей [13]-[16] последовательно были открыты другие семейства предполных классов. Заключительные построения провел И. Розенберг в 1970 году [17]. При этом все предполные классы были описаны как классы сохранения отношений или предикатов.

Одновременно с изучением функций Ахзначной логики были сделаны попытки применения аппарата предполных классов в задаче о полноте для автоматов. Сначала В. Б. Кудрявцев [18] эффективно решил задачу о полноте и её модификациях для функций с задержками. После этого им был получен фундаментальный результат негативного характера: континуальность множества предполных классов автоматных функций [19]. В дальнейшем, М. И. Кратко [20] установил алгоритмическую неразрешимость задачи о полноте относительно операций суперпозиции и обратной связи для конечных систем автоматов.

Ситуация не улучшается, если вместо автоматных функций рассматривать дефинитные автоматы. Автору удалось показать, что в классе дефинитных автоматов континуум предполных классов [44]. В.А.Буевич показал, что в классе дефинитных автоматов задача о полноте относительно операции суперпозиции алгоритмически неразрешима [28].

В силу своего определения [12, 33] автоматные функции и дефинитные автоматы являются бесконечпозначными и даже континуумзпачными функциями. Тем самым полагается, что вычисляющие эти функции автоматы «работают» бесконечно долго. Однако совершенно ясно, что каждое реальное кибернетическое устройство по истечении некоторого конечного промежутка времени прекращает свою «работу», то есть либо становится ненужным, либо переходит в начальное состояние. В связи с этим возникает проблема т-полноты. Множество М дефинитных автоматов называется т-полным, если для любого дефинитного автомата / с помощью операций суперпозиции из функций множествам можно получить функцию /', совпадающую с / на всех наборах, составленных из слов длины т.

В работах [33, 24] показано, что для решения проблемы т-полиоты операция обратной связи является несущественной, так как в данном случае эта операция выразима через операцию суперпозиции. Отсюда следует, что проблема т-полноты для т = 1 по сути является проблемой полноты в ко-нечиозначных логиках. Вместе с тем при т > 2 существует принципиальное отличие между этими задачами. Множество всех детерминированных отображений на словах длины т порождает специальное замкнутое подмножество в конечнозначной логике, существенно зависящее от параметра т. Используя естественную аналогию между проблемой т-полноты и полноты в конечнопорождённых замкнутых классах конечнозначных логик, можно ввести понятие т-предполного класса. Так как для проблемы т-полноты операция обратной связи несущественна, то каждый т-предполный класс в классе автоматных функций порождает т-предполный класс в классе дефинитных автоматов. Для этого достаточно рассмотреть множество всех дефинитных автоматов, принадлежащих заданному г-предполному классу в классе автоматных функций. Других т-предполных классов в классе дефинитных автоматов нет.

Можно показать, что всякое множество дефинитных автоматов (автоматных функций) является т-полным тогда и только тогда, когда целиком не содержится ни в одном из т-предполных классов; совокупность т-предполных классов конечна, может быть описана эффективно и образует минимальную т-критериальную систему [24], при этом множество 1-предполных классов изоморфно множеству предполных классов в конеч-нозначных логиках. Таким образом, для любого т > 1 существуют алгоритмы распознавания т полноты как для конечных множеств автоматных функций, так и для конечных множеств дефинитных автоматов.

С проблемой т-полноты тесно связана проблема А-полпоты. Множество М называется А-полным, если оно является т-полным для любого т. Из определения понятия А-полноты следует, что произвольный дефинитный автомат / можно «аппроксимировать» дефинитными автоматами, принадлежащими замыканию А-полного множества М. То есть можно выбрать последовательность дефинитных автоматов ъ /2, • • •, /г, • • • такую, что для любого т > 1 дефинитный автомат /г совпадает с / на всех наборах, составленных из слов длины т.

Проблема Аполноты исследовалась в работах В. А. Буевича [21]-[28]. Оказалось, что эта проблема алгоритмически неразрешима, как для автоматных функций [21], так и для дефинитных автоматов [28]. Тем не менее критерий полноты может быть сформулирован в терминах Апредполных классов; число Апредполных классов счётно, множество Апредполных классов рекурсивно перечислимо и каждый предполный класс может быть описан эффективно [24]. Более того, каждый т-предполный класс является А-предполным и наоборот: для любого А-предполного класса существует т > 1, такое что этот А-предполный класс является в тоже время т-предгюлным.

Алгоритмически разрешимые случаи возникают при ограничении класса проверяемых систем. Так А. А. Часовских [29] описал в классе линейных автоматов все предполные классы, число которых оказалось счётным, и нашел, тем не менее, алгоритм распознавания полноты конечных систем. Для каждой конечной системы М автоматов он заключается в проверке непринадлежности М конечному числу предполных классов. То есть для произвольной конечной системы удаётся выделить конечную критериальную систему предполных классов. Тальхальм [30] установил свойства решетки замкнутых классов одноместных стабильных автоматов. К.В.Коляда в 1984 году [31] рассматривал классы функций, определённых на регулярных множествах (функции, сопряженные к автоматным) и обнаружил для одних классов алгоритмическую неразрешимость, а для других алгоритмическую разрешимость проблемы полноты.

Ещё в 1961 г. А. А. Летичевским [32] был получен алгоритм решения задачи о полноте для конечных систем автоматов, выдающих номер своего состояния (автоматов Медведева) при наличии всех булевых функций. В 1986 году В. А. Буевич [23] показал алгоритмическую разрешимость проблемы Аполноты для систем автоматов, содержащих все булевы функции. В 1992 году Д. Н. Бабин [35] доказал, что существует алгоритм распознавания полноты системы автоматных функций при наличии в рассматриваемой системе всех булевых функций. Автору удалось получить аналогичные результаты для дефинитных автоматов, а именно показать, что для систем дефинитных автоматов вида Р2 и ь> существует алгоритм проверки на полноту и А-полноту таких систем дефинитных автоматов [41]. Для каждого конечного V он заключается в проверке непринадлежности и конечному числу предполных классов. Значит, для распознавания полноты и А-полноты существенна роль функций без памяти, присутствующих в базисе. Если присутствуют все функции без памяти, то проблемы Аполноты и полноты алгоритмически разрешимы как для автоматов [23, 35], так и для дефинитных автоматов [41]. Если присутствует, фактически, лишь тождественная функция х, то не существует алгоритма распознавания Аполноты и полноты ни для автоматных функций [20, 21], ни для дефинитных автоматов [21, 28].

Учитывая эти результаты, естественно исследовать на Аполноту и полноту системы вида Р и и, где Р — некоторый класс Поста, а и — конечная система дефинитных автоматов (автоматных функций). Такие системы мы будем называть автоматными базисами Поста — также, как это делал Д. Н. Бабин в своих работах [36]-[40]. Возникает разделение классов Поста на сильные и слабые по их способности гарантировать разрешимость проблемы Аполноты и полноты. Для автоматных функций данную задачу исследовал Д. Н. Бабин. Ему удалось расслоить классы Поста на те, для которых проблемы полноты и Аполноты для систем автоматных функций вида разрешимы, и те, для которых эти проблемы неразрешимы. Оказалось, что проблемы полноты и Аполноты для систем вида Р и V разрешимы точно тогда, когда Р содержит либо функцию х + у + либо функцию хуМугУ хх [36]-[40].

Воспользуемся обозначениями из [1]. Для [л>2 ц+1

1, Ж2, • • ■ , Хц+1) = \/ Х1Х2 • • • • • • г=1 г,* — функция, двойственная к Нц. В частности к2{хъ х2, жз) = Х1Х2 V х2хг V Х1Х3. Определим все классы Поста. Классы типа С :

Сг = [{х\/у}],С2 = [{хУу,х + у + 1}],

С3 = [{ху, х + у}], С4 = [{х V у, х{х + у + 1)}]. Классы типа М :

А = [{ху, х V у, 0,1}], А2 = [{ху, XV у, 1}],

0. ч д а

Ц ь / ж

У í'5)

О,

А3 = [{ал/, ж V у, 0}], А4 = [{ху, х V у}}.

Классы типа Ь : [{х + у, 1}], Ь2 = [{х + у + 1}], Ь3 = [{х + у}], ЬА = [{х + у + х}],Ьъ = [{х + у + г + 1}].

Классы типа И :

Бг = [{ху У хг У у г}], £>2 = [{ху У уг У хг}], £)3 = [{ху У хг У гу}]. Классы типа [{ж V У*-* хуУ хгУ у г}], Р22 = [{ж V у г, хуУхгУ у г}],

Р32 = [{1 ,хуУхгУуг}],Г% = [{ж V у, ху У хг У у г}], ръ = [{х{уУг),хуУхгУуг}],Г% = [{х(у У г), ху У хг У у г}}, Р2 = [{0, хуУхгУ у г}}, Р2 = [{ху, хуУхгУ у г}]. Классы типа ^ при ¡л > 2 : = [{х У уг, КЦхъ хд+1)}], ^ = Щ(хъ ., К1' К^ • • •' ^+1)}]» = [{* V У> К^ • • ■' ^+1)}]. рь = [ЫуУг),^^х,. ,^+1)}],^ = . ,хИ+1)}},

К = [{О, К{хх,., ж^+О}], ¿^ = [{ху, И^хг,., 2^+1)}]. Классы типа .Р00 : [{х У = [{я V у*}], = [{1, я V уг}}, = [{х У у}], [{х(у У *)}], = [{*(г/ V *)}], = [{о, х(у У г)}], ВТ = [{ху}}. Классы типа 5 : й = [{х У у}], = [{а: V у, 1}], ^ = [{х У У, 0}], 56 = [{х У у, 0,1}]. Классы типа Р :

Р\ = [{®2/}],Рз = [{^,0}],Р5 = [{*г/, 1}],Рв = [{^г/,0,1}].

Классы типа О :

0\ = [{я}], 02 = [{1}], 03 = [{0}], 04 = [{а?}], 05 = [{х, 1}],

06 = [{х, 0}], О7 = [{0,1}], 08 = [{х, 0,1}], Оэ = [{х,х, 0,1}].

Автор исследовал на А-полноту и полноту системы вида Е и г/, где ^ — некоторый класс Поста, а ь> — конечная система дефинитных автоматов. Для проблемы А-полноты удалось отделить разрешимые случаи от неразрешимых. Оказалось, что проблема А-полноты для систем вида ^Ри^ разрешима точно тогда, когда Г содержит либо функцию х + у 4- г, либо функцию хуУугУ хх, либо функцию

Х1Х2Х3 V Х1Х2Х4 V Х1Х3Х4 V Х2Х3Х4, либо функцию

12:2 V V Х1Х4 V Ж2Ж3 V Х2Х4 V Ж3Ж4.

Следует отметить, что хотя операция обратной связи для решения проблемы А-полноты оказывается несущественной, результаты, полученные для дефинитных автоматов отличаются от результатов, полученных для автоматных функций Д. Н. Бабиным. Так, для классов^3, где г = 1, 2,., 8, проблема А-полноты для систем автоматных функций алгоритмически неразрешима, а проблема А-полноты для систем дефинитных автоматов алгоритмически разрешима. В то же время, можно показать, что если для класса Поста Р проблема А-полноты для систем автоматных функций вида Р и у разрешима, то она разрешима и для аналогичных систем дефинитных автоматов.

Как было сказано выше, автор доказал, что проблема А-полноты для систем вида Р и V алгоритмически разрешима тогда и только тогда, когда £>2 С Р, ЬА С Р, Р23 С Р, либо Р63 С Р.

Легко убедиться, что если Р' С Р и проблема А-полноты алгоритмически неразрешима для систем вида Р и и, то она алгоритмически неразрешима и для систем вида Р' и V. Аналогично, если Р С Р' и проблема А-полноты алгоритмически разрешима для систем видаРи^, то она алгоритмически разрешима и для систем вида Р' и V. Также, если Р* — класс, двойственный к Р относительно замены 0 на 1, то проблема А-полноты для систем вида Р и г/, алгоритмически разрешима тогда и только тогда, когда алгоритмически разрешима проблема А-полноты для систем вида Р* и V. А значит, для доказательства указанной классификации достаточно рассмотреть только граничные случаи и только левую половину диаграммы Поста. То есть, достаточно доказать неразрешимость для классов^1, Ре и Од, и разрешимость на классах £?25 -^4,

Данная работа состоит из «Введения», «Основных понятий и результатов», а также трёх глав. В отличие от «Введения» в «Основных понятиях и результатах» все определения и утверждения даются формально и строго.

Первая глава посвящена разрешимым случаям проблемы А-полноты. Как было указано выше, достаточно рассмотреть только граничные случаи, а именно Дз, Ь4, , • Для каждого из них строится несколько счётных семейств А-предполных классов, которые образуют критериальную систему. Затем для каждой конечной системы дефинитных автоматов из каждого семейства выделяется конечное множество А-предполных классов. Каждый А-предполный класс описывается как класс сохранения отношения. Так как мы рассматриваем только системы, содержащие!^, ¿4, или ^, то нас интересуют не все А-предполные классы [24], а только те, которые содержат все функции из £>2, или В работе встречаются унарные, бинарные отношения, а также отношения арности 4. Приведём некоторые примеры классов сохранения этих отношений. Для каждого р > 2 определяется множество автоматов, у которых выход в момент времени р не зависит от входа в момент времени р — 1. Для каждого р > 1 определяется множество всех автоматов, у которых выход в момент времени р самодвойственно зависит от входа в момент времени р\ множество всех автоматов, у которых выход в момент временир линейно зависит от входа в момент времени р\ множество всех автоматов, у которых выход в момент времени р монотонно зависит от входа в момент времени р. Любопытно, что самая большая сложность возникает с унарными отношениями. Более того, именно унарные отношения строятся для доказательства неразрешимости во второй и третьей главе.

Ранее упоминалось, что разрешимость проблемы А-полноты для систем £>2 и ъ> и ¿4 и р можно вывести как следствие из результатов Д. Н. Бабина [40], полученных для автоматных функций. Но автор приводит своё доказательство этих фактов в работе, так как в процессе доказательства демонстрируется общий подход к решению такого рода задач. А именно, показывается, как наличие соответствующих функций без памяти ограничивает множество унарных отношений, которые необходимо рассматривать. Такое ограничение позволяет для каждой конечной системы дефинитных автоматов из счётного множества А-предполных классов выделять конечное множество. Именно такой подход позволяет решать задачу об А-полноте для классов где г = 1, 2,., 8, хотя для автоматных функций данная задача алгоритмически неразрешима. Более того, по мнению автора описание А-предполных классов и их ограничений, необходимых для решения задачи об А-полноте при наличии классов или Ь4, имеет самостоятельную ценность.

Во второй главе рассматриваются простейшие неразрешимые случаи, а именно б'о, Рв и О9. Как было сказано выше неразрешимость сводится к проблеме конечности последовательности продукций Поста. Тройка в = (И, /9, и), где П = {¿1, (¿2} ■ ■ • 5 с^}, -О* — множество слов в алфавите .О, р \ И —ь £)*, уо(^) = ^5 ^ — натуральное число, называется системой однородных продукций Поста. Если I > си, то скажем, что 0 применима к слову £ = с?ггб?г2. и слово = . назовём результатом применения в к слову Последовательность £2, £з> • • •, такую что а г-+х = назовём последовательностью продукций Поста слова Последовательность продукций конечна, если последнее слово имеет длину меньшую ш. Известно [34], что существует система однородных продукций Поста, для которой не существует алгоритма, по слову £ решающего вопрос о конечности последовательности продукций слова Зафиксируем эту систему продукций Поста После этого продукции Поста специальным образом кодируются словами в алфавите {0,1}. Для каждого слова £ строятся параметрические системы дефинитных автоматов:

Ех = {ж V р, О,1, ИЪ, С0, Ть Т2,., П, ТУ

Е2 = {ж, О, Со, Т1; Т2,., Тк,

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

Следует заметить, что доказательство существенно отличается от доказательства аналогичных утверждений для конечных автоматов [36, 39, 40]. В отличие от конечных автоматов не существует дефинитных автоматов, не зависящих от входа, которые бы выдавали периодическую последовательность на выходе. А значит мы пе можем в каждый момент времени находить начала частей, которые получились при кодировании продукций. Для корректного «чтения» и «преобразования» продукций метод кодирования продукций существенно усложняется. Есть ещё одно существенное отличие доказательств для конечных автоматов и дефинитных автоматов. При некорректном использовании конечного автомата, он запоминает «ошибку» и во все последующие моменты уже не работает корректно. Дефинитный автомат забывает любую информацию через определённое число шагов. А значит даже после некорректного использования дефинитный автомат начнёт работать как и раньше. Это тоже значительно усложняет конструкцию, так как приходится следить, чтобы «ошибка», возникшая в какой-то момент времени, не могла исчезнуть.

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

В третьей главе рассматривается самый сложный неразрешимый случай, а именно рассматриваются классы и ^. Техника доказательства неразрешимости сильно отличается от техники доказательства во второй главе. И хотя задача опять решается сведением к проблеме конечности последовательности продукций Поста, отличие настолько существенно, что доказательство выделено в отдельную главу. В отличие от доказательства во второй главе, где используются специальные дефинитные автоматы, с помощью которых можно из одного элемента последовательности продукций построить следующий элемент последовательности, в данном случае вся последовательность продукций сначала кодируется специальным образом с помощью нулей и единиц, а потом только проверяется, что последовательность записана корректно. Ещё больше усложняется конструкция, позволяющая выделять части, которые получились при кодировании продукций. Суть этой конструкции заложена в определении унарного отношения, которое сохраняется в случае, если последовательность продукций конечна. Одно из принципиальных отличий доказательства в этой главе от доказательства во второй главе заключается в следующем. Во второй главе автоматы строились таким образом, что «ошибка», возникшая в какой-то момент времени, не могла исчезнуть, а оставалась записанной в сверхслове. Наличие же функций Нц для ¡л > 4 делает это невозможным. Специальным образом подобрав слова, всегда можно избавиться от «ошибки», записанной на сверхслове. Для этого достаточно проследить, чтобы «ошибки» в разных сверхсловах были в далёкие друг от друга моменты времени. Для решения данной проблемы был придуман новый подход, в котором такого понятия, как «ошибка» уже нет. В процессе доказательства мы сразу строим автоматы так, чтобы они сохраняли сложное унарное отношение.

Основные результаты работы опубликованы в статьях [42] — [45].

Помимо этого результаты диссертации неоднократно докладывались на семинарах механико-математического факультета МГУ им. М.В. Ломоносова «Теория автоматов» (2005-2010 гг.) и «Кибернетика и информатика» (2005-2010 гг.) под руководством академика В. Б. Кудрявцева.

Также результаты докладывались на следующих конференциях:

• международные научные конференции студентов, аспирантов и молодых ученых «Ломоносов» (Москва, МГУ им. М.В. Ломоносова, 2007, 2008, 2009 и 2010 гг.);

• научные конференции «Ломоносовские чтения» (Москва, МГУ им. М.В.Ломоносова, 2007, 2008 и 2009 гг.);

Основные понятия и результаты

Пусть N = {1,2,3,.} — множество всех натуральных чисел, N0 = 1^и{0}, Е2 — {0,1}, Е2 — множество всех слов длины I в алфавите Е — множество всех бесконечных последовательностей нулей и единиц. Далее такие последовательности называем сверхсловами. МножествоЕп состоит из всех наборов (о,!, а^, • • •, <хп), где а^ £ Е. Если а,Ь е Е2, то а — отрицание а, а V Ь — дизъюнкция а и 6, а&& — конъюнкция а и 6, а + Ь — сложение по модулю 2. Множество всех булевых функций будем обозначать Р2.

Пусть а — слово или сверхслово. Для п е N через а(п) обозначим тьый элемент а. Обозначим через |си| длину слова а; для сверхслова а будем полагать, что \а\ — со. Для слова а, такого что |а| > к, определим го; = а(|о:| — к + 1). а(|а| — 1)а;(|а|).

Для слова или сверхслова а, такого что \а\ > к > I положим ка = а(1)а(2). а(к), [¡]ка = а(к - I + 1 )а(к -1 + 2). а{к).

Для произвольного слова а определим слово о^ = (у.а „. а, и сверхслово ск°° = ааа.

Пусть п, к € N. Функция Т : Еп —> Е называется дефинитным автоматом с п входами высоты /г, если существуют функции : (Е23)П Е2 {у = 1, 2,3,. ., /г), такие что для любых х\, Х2,., хп £ Е выполняется: т(хг,х2: . . • = Л(]1Ж1,]1Ж2, • • • ,Ь хп)

Т(х 1,Ж2, • • • ,хп)(2) = /2(] 2^1,] 2^2, • ■ • ,]2Хп)

Т(х1,х2, Хп){К) = ЛО/гГЕь ]/1Х21 ]}гХп) Т(х 1, Ж2, . • • , + 1) = Ь([н\к+1Х1, Ы/г+1^2, - - • , Ы/г+1^г)

Т(хъх2, ■ ■ ., хп)(Н + г) = Д([л]л+»Ж1, [л]л+»Ж2,., [л]л+гЖ„)

Таким образом, согласно нашему определению автомат высоты Н является также автоматом высоты /г +1. Элемент Т(жх, х2,., хп)(у) будем называть элементом на выходе автомата Т в момент времени а £¿0) — элементом, подаваемым на ¿-ый вход в момент времени ]. Для ^ — 1,., /г — 1 функция определяет элемент на выходе автомата Т в момент времени , а функция Д определяет элемент на выходе автомата, начиная с момента времени /г.

Пусть Т — автомат высоты ¡г. Для р Е N определим функцию Тр : (Е2Р)п —Е2. Если р < /г, то положим

Тр(аи а2,., ап) = /р(аь а2,., ап).

Для р > Н положим

Тр(аь а2,. , ап) = Д([лаь [догг, • • ■, [н^п)

Таким образом, для любого р функция Тр определяет элемент на выходе автомата Т в момент времени р. Функции где р = 1,. будем называть порождающими. Нетрудно убедиться, что для задания дефинитного автомата необходимо задать высоту автомата и порождающие функции. Доопределим естественным образом каждый автомат на словах длины р. Будем полагать, что для любых с*1; а2,., ап € Е2Р выполняется Т{аъ а2, ■ ■., ап) = р, где ¡3 е Е2Р и /?($) = Т5(]Ааь ]3а2,]ва„) для любого 5 < р.

Множество всех дефинитных автоматов обозначим Va• Для Т £ Va через h(T) обозначим наименьшую высоту автомата Т. Ясно, что каждой булевой функции из Р2 соответствует дефинитный автомат высоты 1. Будем использовать стандартные обозначения для автоматов высоты 1, а именно: х, xSzy — ху, х V у, х + у — дефинитные автоматы 7\, Т2, Т3 и Т4 высоты ' 1, такие что выполняется Tl(a) = a, T2(a,fi) = aSz/3, Т^(а,/3) = а V /3,

ТЦа,/3) = с* + /3.

Пусть 5С — автомат высоты 2 с одним входом, для которого S](а) = с, = а(1), Автомат 5С будем называть задержкой с начальным состоянием с.

Пусть М С Va. Фиксируем некоторое счётное множество

U = {^1,^2,^3, • • •}, элементы которого будем называть переменными. Индуктивно определим понятие терма над множеством М :

1) Если и £ U, то и — терм над М.

2) Если F — автомат с п £ N входами, F £ М, т\, т2,., тп — термы над М, то выражение F(ri, т2, ., тп) — терм над М.

Термы, отличные от переменных, назовём собственными. Пусть т — произвольный терм, (xi,x2,. ,xm) — набор попарно различных переменных, содержащий все переменные, использованные при построении терма т. Тогда через т(хi,x2,. ,xm) обозначим функцию г : Еш —> Е, определяемую индуктивно:

1) Если т — хс — переменная, 7 = (71, j2,., 7m) £ Em, то определим т(хъх 2,. .,xm)(j) = 7е.

2) Если г = F(r1, г2,. ., т„), 7 = (71,72,., jm) £ Em, то определим г(ж1,ж2,. • • ,Жт)(7) = F(ti(xi,x2, . ,жто)(7),., Tn(r27i, а;2, • • • ,жш)(7))

О функции Т, такой что Т = т(х 1, Ж2, •., хт) для некоторого собственного терма т над множеством М, будем говорить, что она получена термальными операциями из дефинитных автоматов множества М. Нетрудно проверить, что функция Т также будет дефинитным автоматом, поэтому мы можем ввести на множестве Та оператор замыкания [ ] относительно термальных операций — такое отображение, которое каждому множеству М С Та сопоставляет множество [М] всех автоматов, которые можно получить термальными операциями из автоматов множествам. Определённый выше оператор замыкания также известен как оператор замыкания относительно операции суперпозиции [33].

Множество М называется замкнутым, если [М] = М; множество М называется полным, если [М] = Та- Пусть т 6 М, скажем, что автоматы Т\ и Т2 с п входами т-равны, если для любого г < г выполняется Т[ = XОбозначим через [М)т множество всех дефинитных автоматов, т-равных получающимся из М с помощью термальных операций. Множество М называоо ется А-полным, если [М]т = Та для любого т. Определим [М]д = р| [М]т.

Т—1

Проблема А-полноты для Та состоит в описании всех А-полных множеств М. Множество М называется А-замкнутым, если [МЦ = М; М называется А-предполным, если [М]а ^ Та и для любой / е Та \ М выполняется [М и {/}]Л = Та.

Нетрудно заметить, что дефинитные автоматы — это все автоматы, которые можно получить с помощью термальных операций из автоматов из Р2 и задержки. Другими словами [Р2 и {<5с}] = Та, где 8С — задержка с начальным состоянием с. Отсюда, в частности, следует, что [{х\/у, «Б'с}] = Та

Постом полностью описаны все замкнутые относительно операции суперпозиции "классы булевых функций [1, 8]. Все они конечнопорожденные и образуют счётную решетку по включению.

Пусть Р — замкнутый класс булевых функций. Определим проблему А-ПОЛНОТА(-Р): дана конечная система V дефинитных автоматов, заданных своими порождающими функциями; требуется установить, А-полна ли система Р и V.

Нетрудно убедиться, что если ^ С и проблема А-ПОЛНОТА(^) алгоритмически разрешима, то А-ПОЛНОТА(-Р') также алгоритмически разрешима. Аналогично, если С .Р и проблема А-ПОЛНОТА(Т) алгоритмически неразрешима, то А-ПОЛНОТА^') также алгоритмически неразрешима. Также, если Р* — класс, двойственный к Р относительно замены 0 на 1, то проблема А-ПОЛНОТА(Р*) алгоритмически разрешима точно тогда, когда алгоритмически разрешима проблема А-ПОЛНОТА(Р). Воспользуемся обозначениями из [1]. Для ¡1 > 2

М+1 х2, . ■ . , хц+г) = \/ хгх2 . хг^х{+1 . . . х/1+1, г=1 г* — функция, двойственная к К^. В частности

12(^1, х2, хз) = х±х2 V х2х3 V х1х3. [№}], р| = кад], ^ = над, ь4 = = [{жуй],

Р8°° = [{ж&У}], = [{ж V 2/, 0,1}], Р0 = [{ж&7/,0,1}], Од = [{г,0}], =

Были доказаны следующие три теоремы.

Теорема 1. [43] Проблема А-ПОЛНОТА(Р ) алгоритмически разрешима для каэюдого Р Е {Р|? > -^2? £4}

Теорема 2. Проблема А-ПОЛНОТА(Е) алгоритмически неразрешима для каждого Р € {¿>6; Од}.

Теорема 3. [45] Проблема А-ПОЛНОТА(Е) алгоритмически неразрешима для каэ!сдого Р € {Р4, Р^ }•

Теорема 4. Проблема А-ПОЛНОТА(Р) алгоритмически разрешима тогда и только тогда, когда для какой-то f е {/¿2,^ + у + ^3} выполняется /б

Список источников диссертации и автореферата по математике, кандидата физико-математических наук, Жук, Дмитрий Николаевич, Москва

1. Post Е. Two-Valued 1.erative Systems of Mathematical Logic. Princeton Univ. Press, Princeton, 1941.

2. Automata Studies, ed. by C.E. Shannon and J. Mc Carthy. Princeton, 1956 (русский перевод: Сборник статей под редакцией Маккарти и Шеннона. ИЛ, Москва, 1956.)

3. Kleene S. С. Representation of events in nerve nets and finite automata. Automata Studies, ed. by C.E.Shannon and J. Mc Carthy, Princeton, 1956, 3-41.

4. M. Perles, M.O. Rabin, E.Shamir. Theory of definite automata. IEEE Trans, on Electronic Computers, EC-12 (1963), 233-243.

5. G. Ginzburg. About some properties of definite, reverse definite and related automata. IEEE Trans, on Electronic Computers, EC-15 (1966), 809-810.

6. B. Imreh. On finite definite automata. Acta Cybernetica, 7 (1984), 61-65.

7. M. Steinby. On definite automata and related systems. Ann. Acad. Sci. Fenn., Ser. A 1,444 (1969).

8. Яблонский С. В., Гаврилов Г. П.,Кудрявцев В. Б. Функции алгебры логики и классы Поста. Наука, Москва, 1966.

9. Кузнецов А. В. О проблемах тождества и функциональной полноты для алгебраических систем. Труды третьего всесоюзного математического съезда. Т. 2. Москва. Изд. АН СССР, 1956, с.145-146.

10. Кузнецов А. В. Структуры с замыканием и критерии функциональной полноты. Успехи математических наук. Т. 16, №2, 1961, с.201-202.

11. Яблонский С. В. Функциональные построения в fc-значной логике. Труды математического института им. В.А.Стеклова. АН СССР, 1958, Т. 51, с.5-142.

12. Яблонский С. В. Введение в дискретную математику. Наука, Москва, 1986. с.5-142.

13. Ло Чжу-Кай, Лю Сюй Хуа. Предполные классы, определяемые бинарными отношениями в многозначной логике. Acta Sei. Natur. Univ. Jilinensis, 1963, №4.

14. Захарова Б. Ю. Критерий полноты для системы функций из Проблемы кибернетики. 1967, №18, с.5-10.

15. Мартынюк В. В. Исследование некоторых классов функций в многозначных логиках. Проблемы кибернетики. 1960, №3, с.49-60.

16. Паи Юн-Цзе. Один разрешающий метод для отыскания всех предпол-иых классов в многозначной логике. Acta Sei. Natur. Univ. Jilinensis, 1963, №3.

17. Rosenberg J. La structure des fonctions de plusiers variables sur un ensemble fini. Comptes Rendus Acad. Sei. Paris, 1965 №260, c.3817-3819.

18. Кудрявцев B.B. Теорема полноты для одного класс автоматов без обратных связей. Проблемы кибернетики. 1962, №8, с. 91-115. // ДАН СССР. 1963. Т. 151. m 3. С. 493-496.

19. Кудрявцев В. Б. О мощностях множеств предполных классов некоторых функциональных систем, связанных с автоматами // ДАН СССР. 1963. Т. 151. № 3. С. 493-496.

20. Кратко М.И. Алгоритмическая неразрешимость проблемы распознавания полноты для конечных автоматов. Москва, ДАН СССР, 1964, т. 155.

21. Буевич В. А. Об алгоритмической неразрешимости распознавания А-полноты для о.д.-функций // Математический заметки. Т. 12, №6. 1972. С. 687-697.

22. Буевич В. А. О т-полноте в классе автоматных отображений. Москва, ДАН СССР, т. 252. №5. 1980.

23. Буевич В. А. Условия А -полноты для автоматов. М.: Изд-во МГУ, 1986. // Математический заметки. Т. 12, №6. 1972. С. 687-697.

24. Буевич В. А. Условия А-полноты для конечных автоматов, 4.1, ч.2. Издательство МГУ, 1986, 1987 г.г.

25. Буевич В. А. О т-полноте в классе детерминированных функций. Доклады РАН, т. 326. №3. 1992.

26. Буевич В. А. О т-полноте систем, содержащих все одноместные ограниченно-детерминированные функции. Математические вопросы кибернетики. Вып. 8. 1999.

27. Буевич В. А. О существовании алгоритма для распознавания А-полноты систем, содержащих все одноместные ограниченно-детерминированные функции. Математические вопросы кибернетики. Вып. 8. 1999.

28. Буевич В. А., Клиндухова Т. Э. Об алгоритмической неразрешимости задач об А-полноте и полноте для дефинитных ограниченно-детерминированных функций. Москва, Математические вопросы кибернетики. Вып. 10. 2001.

29. Часовских А. А. О полноте в классе линейных автоматов. Математические вопросы кибернетики. Вып. 3. 1995, с. 140-166.

30. Тальхайм Б. О. О решетке замкнутых классов стабильных автоматов. Методы и системы диагностики. Вып. 1, Саратов, 1979.

31. Коляда К. В. О полноте регулярных отображений. Проблемы кибернетики. Вып. 41. М. Наука, 1980., с.41-49.

32. Летичевский A.A. Условия полноты для конечных автоматов. Вычислительная математика и математическая физика, №4, 1961, с.702-710.

33. Кудрявцев В. Б., Алешин C.B., Подколзин A.C. Введение в теорию автоматов. Наука, Москва, 1985.

34. Мальцев А. И. Алгоритмы и рекурсивные функции. Наука, Москва, 1986.

35. Бабин Д. Н. Разрешимый случай задачи о полноте автоматных функций. Москва, Дискретная математика, 1992. Т. 4, вып. 4. с. 41-56.

36. Бабин Д. Н. Неразрешимость проблемы полноты и А-полноты некоторых систем автоматных функций. Москва, Дискретная математика, 1995. Т. 7, вып. 2. с. 52-65.

37. Бабин Д. Н. О разрешимости проблемы полноты для специальных систем автоматных функций. Москва, Дискретная математика, 1996. Т. 8, вып. 4. с. 79-91.

38. Бабин Д. Н. Алгоритмическая разрешимость свойств полноты и А-полноты конечных систем автоматных функций с линейной истинностной частью. Москва, Интеллектуальные системы, т. 3, 1998, с. 51-69.

39. Бабин Д. Н. Конечность множества автоматных базисов Поста с разрешимой проблемой полноты. Москва, Дискретная математика, 1998. Т. 10, вып. 3. с. 57-64.

40. Бабин Д. Н. О классификации автоматных базисов Поста по разрешимости свойств полноты и А-полноты // Доклады Академии наук. №4. Т. 367. 1999. С. 439-441

41. Жук Д. Н., Присмотров Ю. Н. О проблеме полноты в классе автоматов без обратной.связи. Москва, Интеллектуальные системы, т. 11, 2007, с. 439-472.

42. Жук Д. Н. О неразрешимости проблемы полноты для дефинитных автоматов. Москва, Интеллектуальные системы, т. 12, 2008, с. 211-228.

43. Жук Д. Н. Разрешимые случаи задачи об А-полноте для дефинитных автоматов. Москва, Интеллектуальные системы, т. 13, 2009, с. 273-312.

44. Жук Д. Н. Континуальность множества предполных классов в классе дефинитных автоматов. Москва, Интеллектуальные системы, т. 13, 2009, с. 41-48.

45. Жук Д. Н. О классификации автоматных базисов Поста по разрешимости свойств А-полноты для дефинитных автоматов. Москва, Дискретная математика, 2010. Вып. 2. с. 41-56.