Введение к работе
Актуальность темы
В последние десятилетия значительно возрос интерес исследователей к решению различных типов рекурсивных уравнений при ряде ограничений на эти уравнения. Это, в частности, вызвано возрастающим интересом к поиску методов автоматизированного синтеза программ для современных ЭВМ, а также к разработке методов преобразования программ и других динамических дискретных систем для повышения эффективности работы этих систем или других задач. Интересное приложение методов решения рекурсивных уравнений (функциональных уравнений) и так называемых Е—теорем [6] в теории доказательств для поиска и анализа программ для ЭВМ было предложено Г. Крайзелем [6].
Однако с необходимостью решать рекурсивные уревнения мы сталкиваемся далеко не только в области теоретического программирования. Математическая логика также изобилует подобными примерами. Мы сталкиваемся с проблемой построения функционала, удовлетворяющего определенным условиям, например в знаменитом доказательстве Геделя [1], непротиворечивости интуиционистской арифметики. Мы также имеем дело с аналогичной проблемой в связи с так называемой интерпретацией опровержением контрпримера Крайзеля [5].
Характерной особенностью указанных выше случаев является то обстоятельство, что на функционалы(условия) фигурирующие в
уравнениях и на решение уравнений ставятся специфические ограничения, обусловленные природой и условиями данной задачи.
Это обстоятельство с одной стороны значительно сужает класс рассматриваемых задач, а с другой в некоторых случаях делает невозможным (в зависимости от природы задачи) применение таких мощных средств как первая теорема Клини [2][3] о неподвижной точке. Последнее, в свою очередь, представляет собой не что иное, как утверждение о существовании решений в классе частично рекурсивных функций для уравнений вида:
где F - рекурсивный функционал.
В работе Маранджяна [7] был рассмотрен более общий случай, когда мы имеем систему рекурсивных уравнений вида:
*.{/;.../.}(*) =
^.{/.,-./.К?) =
где Fi>~'Fm'G»—'Gm. рекурсивные термы (термы обозначающие рекурсивные функционалы от функций fi'-'f- и переменных х). Такие уравнения, следуя [7], мы называем рекурсивными уревнениями общего вида Р.У.О.В..
В [7] Маранджяном было сформулировано необходимое и достаточное условие существования решений для этих уравнений.
В современной теории рекурсивных функций так называемой общей теории рекурсии известны многие обобщения понятия рекурсивной функции и эффективной вычислимости для различных предметных областей. Эта работа как раз посвящяется анализу результатов [7] для упомянутых обобщений, а именно для функционалов, вычислимых по Клини [3,4,5].
Цель работы
Целью данной работы является поиск условий существования решений для рекурсивных уравнений общего вида над функционалами высших конечных типов [3][9], аналогичных условию полученной Маранджяном [7] для Р.У.О.В. на натуральных числах. Исследуются также свойства совокупностей функций и функционалов, являющихся решениями Р.У.О.В., в частности уточняются классы теоретико-числовых функций (характеристических функций предикатов), являющихся единственными решениями систем Р.У.О.В., т.е. однозначно представляемых посредством системы Р.У.О.В.
Научная новизна и теоретическая ценность работы
В диссертации получено необходимое и достаточное условие существования решений для рекурсивных уравнений над функционалами высших конечных типов.
Впервые уточнены классы теоретико-числовых предикатов и функций, характеризуемых как единственные решения систем рекурсивных уравнений общего вида.
Впервые приведены примеры рекурсивных уравнений, илюстрирующих различные свойства и отношения функционалов, являющихся решениями этих уравнений.
Эти и некоторые другие результаты, доказываемые в работе, являются новыми.
Вопросы, рассматриваемые в диссертации, актуальны и важны как для развития самой теории рекурсивных функций, так и для ее применений в различных областях, как теория доказательств и теоретическое программирование. Они могут дать толчок для дальнейших исследований в данном направлении.
Все результаты полученные в диссертационной работе являются новыми. Методы исследований.
В диссертации используются методы классической теории рекурсивных функций и математической логики. Апробация работы.
Основные результаты диссертации докладывались на международной конференции по вычислительным наукам и информационным технологиям CSIT-97, на конференции Армянского Математического Общества, на общем собрании ученого совета ИПИА НАН РА, на семинаре по теоретическому программированию в HPL Armenia. Публикации.
По теме диссертации опубликованы 4 работы. Список опубликованых работ приведен в конце автореферата. Структура и объем диссертации.
Диссертационная работа состоит из введения, трех глав и списка цитируемой литературы.