О рекурсивных уравнениях тема автореферата и диссертации по математике, 01.01.09 ВАК РФ

РГЗ ОД

ЧиЬш 4 ъ бпьэ-зп ьч/ььрг* иаадзкь иш^ъитчшь

Ь"ЬЛ>ПР1Ш8№113Ь ЬЧ иЧЗПииШЗЦЦЪ ^РПР1_ЫГЪЬРЬ

ьъизмш^

11иушй Црш

. иъч-ршшгэ <и4иииРПМГьЬРГ> игшьъ

Шшбиц^ишц^тЛ Ц.01.09 ЦшрЬйштЭДшЦшО ЩарЬпйЬифЦш и ^шрЬйшиф^шЦшО тршгёшрш Стр]П1 С

Йфс^ш-гёшрЬгёштЭДш^шО о}ипп1р,]П1СШЬр11 рЫ^ш&пф с^тш^шО шиш11бшй]1 ЬицдйииО штЪИифлпитрзшй

иьаитьр

ЬркиО-1997

ИНСТИТУТ ПРОБЛЕМ ИНФОРМАТИКИ И АВТОМАТИЗАЦИИ НАЦИОНАЛЬНОЙ АКАДЕМИИ НАУК РЕСПУБЛИКИ АРМЕНИЯ

На правах рукописи

Аслян Ара Рудольфович

О РЕКУРСИВНЫХ УРАВНЕНИЯХ

Специальность Ц.01.09 Математическая кибернетика и математическая логика

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

Ереван-1997.

Работа выполнена в Институте проблем информатики и автоматизации HAH РА

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

с. н. е., Маранджян Г. Б.

Официальные оппоненты: доктор физико-математических наук,

профессор, Заславский И. Д.

Ведущая организация: Лаборатория эвристической физики Армении

Защита состоится 28 ноября 1997 г. в 11:00 часов на заседании специализированного совета 037 " Математическая кибернетика и математическая логика" в институте проблем информатики и автоматизации HAH РА по адресу: 375044, г. Ереван, ул. П.СевакаД.

С диссертацией можно ознакомиться в научной библиотеке

кандидат физико-математических наук доцент, Топчян Р. В.

ИПИАНАНРА.

Автореферат разослан

Ученый секретарь специализированного совета к.э.н., с.н.с.

ОБЩАЯ ХАРАКТЕРИСТИКА ДИССЕРТАЦИИ

Актуальность темы

В последние десятилетия значительно возрос интерес исследователей к решению различных типов рекурсивных уравнений при ряде ограничений на эти уравнения. Это, в частности, вызвано возрастающим интересом к поиску методов автоматизированного синтеза программ для современных ЭВМ, а также к разработке методов преобразования программ и других динамических дискретных систем для повышения эффективности работы этих систем или других задач. Интересное приложение методов решения рекурсивных уравнений (функциональных уравнений) и так называемых Е—теорем [6] в теории доказательств для поиска и анализа программ для ЭВМ было предложено Г. Крайзелем [6].

Однако с необходимостью решать рекурсивные уревнения мы сталкиваемся далеко не только в области теоретического программирования. Математическая логика также изобилует подобными примерами. Мы сталкиваемся с проблемой построения функционала, удовлетворяющего определенным условиям, например в знаменитом доказательстве Геделя [1], непротиворечивости интуиционистской арифметики. Мы также имеем дело с аналогичной проблемой в связи с так называемой интерпретацией опровержением контрпримера Крайзеля [5].

Характерной особенностью указанных выше случаев является то обстоятельство, что на функционалы(условия) фигурирующие в

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

Это обстоятельство с одной стороны значительно сужает класс рассматриваемых задач, а с другой в некоторых случаях делает невозможным (в зависимости от природы задачи) применение таких мощных средств как первая теорема Клини [2][3] о неподвижной точке. Последнее, в свою очередь, представляет собой не что иное, как утверждение о существовании решений в классе частично рекурсивных функций для уравнений вида:

где Р - рекурсивный функционал. В работе Маранджяна [7] был рассмотрен более общий случай, когда

мы имеем систему рекурсивных уравнений вида:

= <?.{/"....../.}(*)

^{/.,-./„К?) = <и/..-./.к*),

где 'Ст. рекурсивные термы (термы обозначающие

рекурсивные функционалы от функций

и переменных *). Такие уравнения, следуя [7], мы называем рекурсивными уревнениями общего вида Р.У.О.В.. '

В [7] Маранджяном было сформулировано необходимое и достаточное условие существования решений для этих уравнений.

В современной теории рекурсивных функций так называемой общей теории рекурсии известны многие обобщения понятия рекурсивной функции и эффективной вычислимости для различных предметных областей. Эта работа как раз посвящяется анализу результатов [7] дня упомянутых обобщений, а именно для функционалов, вычислимых по Клини [3,4,5].

Цель работы

Целыо данной работы является поиск условий существования решений для рекурсивных уравнений общего вида над функционалами высших конечных типов [3][9], аналогичных условию полученной Маранджяном [7] для Р.У.О.В. на натуральных числах. Исследуются также свойства совокупностей функций и функционалов, являющихся решениями Р.У.О.В., в частности уточняются классы теоретико-числовых функций (характеристических функций предикатов), являющихся единственными решениями систем Р.У.О.В., т.е. однозначно представляемых посредством системы Р.У.О.В.

Научная новизна и теоретическая ценность работы

В диссертации получено необходимое и достаточное условие существования решений для рекурсивных уравнений над функционалами высших конечных типов.

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

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

Эти и некоторые другие результаты, доказываемые в работе, являются новыми.

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

Все результаты полученные в диссертационной работе являются новыми.

Методы исследований.

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

Основные результаты диссертации докладывались на международной конференции по вычислительным наукам и информационным технологиям CSIT-97, на конференции Армянского Математического Общества, на общем собрании ученого совета ИПИА HAH РА, на семинаре по теоретическому программированию в HPL Armenia. Публикации.

По теме диссертации опубликованы 4 работы. Список опубликованых работ приведен в конце автореферата. Структура и объем диссертации.

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

СОДЕРЖАНИЕ ДИССЕРТАЦИИ

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

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

Вводится понятие рекурсивных уравнений общего вида как уравнений типа:

{/,-■>/. К2) = с»{/1.-./.}(2) (1),

где . рекурсивные термы, обозначающие рекурсивные

функционалы. Термы -.С»,содержат вхождения свободных

переменных 2 для функционалов высших конечных типов и функциональные символы /и—>/»дпя искомых решений.

Рекурсивные уравнения (1) впервые были рассмотрены Маранджяном [7], для случая когда2 пробегают множество натуральных чисел. Было найдено необходимое и достаточное условие существования решений, показано, что проблема существования

у О

решений для этих уравнений является ^ полной проблемой.

Необходимое и достаточное условие существования решений, которое мы доказываем для уравнений (1) является аналогом результата полученного Маранджяном [7].

В формулировке условия фигурирует понятие ' -фрагмента, определяемое следующим образом:

Пусть дано конечное множество термов и функциональных

символов -А>•••>/», тогда

1 .Произвольный терм б,[/1.—./,]. / фрагмент

2.Произвольный терм, полученный из »'-фрагмента заменой

фиксированного вхождения функционального символа ^ на

фрагмент \ ' ' является < -фрагментом Тогда имеет место следающая

Теорема 1.1 система рекурсивных уравнений имеет решение тогда и только тогда, когда существует система термов и соответствующая

замена функциональных символов /»>•■•>/» на < -фрагменты \ ' в (1) такая, что мы получаем систему тождеств

- о,{/,...,/„}(5)

В случае когда в (1) имеем переменные « только для теоретико-числовых функций вводится понятие квази-решения для систем рекурсивных уравнений.

Пусть 3 класс теоретико-числовых функций. Систему функций

/ >•■•>/„ назовем 5-квази-решением системы рекурсивных уравнений (1), если для произвольных й !13 3 и 0 < / < т имеет место тождество

- с, {/*>••-/,'}(г) (2)

В диссертации доказана следующая

Теорема 1.3 Для производного класса теоретико-числовых

ГТ1

функцийкоторый имеет 1 определение, существует Р.У.О.В.

0{/}[а„а2}(х) = 0

которое не имеет решений, но имеет всюду определенное рекурсивное 3-квази-решение.

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

тождества (2) дтя произвольных 2 из , мы уже можем утверждать что А .••■>/„ есть решение системы рекурсивных уравнений (1).

Теорема 1.4 Система рекурсивных функций ^ >■•••-/» будет решением системы Р.У.О.В. (1) в том и только в том случае если она является квази-решением для системы уравнений(1).

В диссертации также доказано, что проблема существования решений для Р.У.О.В. со свободными переменными а только для теоретико-

числовых функций является п>-- полной проблемой (Теорема 1.5).

Во второй главе диссертации уточняется класс теоретико-числовых предикатов представимых посредством Р.У.О.В. Мы определеняем это понятие следующим образом.

Быдем говорить, что решение /I .•■•>/„ системы Р.У.О.В. (1) относительно функционального символа представляет теоретико-числовой предикат если система (1) имеет единственное решение и функция ^> из списка ^ '"'' является характеристической функцией предиката т

В случае, когда в (1) переменные <* пробегают натуральные числа, показано, что для произвольного гиперарифмегического предиката существует система рекурсивных уравнений, которая представляет данный предикат (Теорема 2.6).

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

В третей главе приводятся примеры двух уравнений илюстрируюших следующие возможности для рекурсивных уравнений. Доказывается, что первое из уравнений имеет всюду определенное непрерывное решение которое не вычислимо по Клини (см.[4],[5],[9]). Однако существует вычислимый по Клини функционал, для которого

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

Во втором примере построено уравнение, единственным решением которого является функционал, который не вычислим по Клини, но рекурсивен (для сравнительного анализа этих понятий см [9]).

Цитированная литература

1. К. Гедель Об одном еще не использованном расширении финитной точки зрения. - В книге Математическая теория логического вывода. М.Наука, 1967, с. 499—510

2. S. С. Kleene. Introduction to Metamathematics.

D. Van Nostrand Co., Inc. New York, Toronto, 1952.

3. S. C. Kleene. Recursive Functionals and Quantifiers of Finite TypesI,Trans. Amer. Math. Soc. V 142, (1959),1-52 p; and II (1963),106-142.

4. S. C. Kleene. Countable Functionals. In A. Heyting editor, Constructivity in Mathematics, Studies in Logic, pages 81-100. North-Holland Publ. Co., Amsterdam, 1959.

5. G. Kreisel. Interpretation of Analysis by Means of Constructive Functionals of Finite Types. In A. Heyting. editor, Constructivity

in Mathematics, Studies in Logic, pages 101—128. North-Holland Publ. Co., Amsterdam, 1959.

6. G. Kreisel. Some uses of proof theory for finding computer programs, Colloque International de Logique, Clermont—Ferrand, 18—25 , juillet 1975, Centre National de la Recherche Scientifique, Paris, 1977, p. 123—134

7. H. B. Marandjian. General Form Recursive Equations. Computer Science Logic, in Lecture Notes in Computer Science, vol. 933, Springer, Berlin Heidelberg, 1995, pages 501-511.

8. J. Myhill. Finitely Representable Functions. In A.

Heyting. editor, Constructivity in Mathematics, Studies in Logic, pages 195-207. North-Holland Publ. Co., Amsterdam, 1959.

9. D. Normann. Recursion on the Countable Functionals. Lecture Notes in Mathematics, vol. 811, Springer-Verlag, Berlin Heidelberg New York, 1980.

Основные результаты диссертации опубликованы в следующих работах:

1. A. Aslyan . On a Class of Number-Theoretic Predicates

Represented by Means of General Form Recursive Equations.

Математические вопросы кибернетики и вычислительной техники XVII,

Ереван 1997, р. 30—34

2. A. Aslyan. On a Representation of Hyperarithmetical Predicates Математические вопросы кибернетики и вычислительной техники XVIII, Ереван 1997, р. 1—13

3. A. Aslyan . On Higher Level Recursive Equations , (1997),p. Proceedings of the Conference on Computer Science and Information Technologies. Yerevan 1997 p.3-5

4. A. Aslyan. On Number-Theoretic Predicates Represented by Means of General Form Recursive Equations, -Dep. In ArmNIINTI. Yerevan 1997-14p.A205-AR97

Ili5i}ini}iiuqjip

llpuj ftniiyi^ti UuuuiG "UQripuirjoipd hm^uiuuiprmJQhpJi liiuutiG" Ara Rudolf Aslyan "On Recursive Equations"

UinbGiufununipjniOi} Gi^ipijiud t puipdp ljiupq[i gGqhuiGnip uihupji uiGiipuiqiupd huii(uiuuipnuiGkp[i iniimuiGhpti qnjmpjuuG ui0hpiudh2ui L puiiluipuip vqiuji5uxGGhp}i hhuiuiqninnipjuiGii : T5;>qpini[rui5 bG Guib inhuui-piluipuiGiulpufl uiphqjiliuimGbpfi li .^niGligluuGhpli rpuubpp, npnGp Ipupnq bG huiGiiliuuiGiu^uiju hunJuiuuipnuSGbpli iljnulj pn&nu$p ' Ijuipnrj bG i5[uupc)kpnphQ Gljuipiuqpv|bL hun[uiuuipi\5Gbp]i tfjigngnii : T-liinuipliilnid t Guili iIuiuGuil|}i IpupqpGpuig .1)niGl|g{inGui[flhp[i ipuuniii pndniiSGbpfi qnjnipjuiG uipnpjhiIJi uiLqnpfipiIfili puipijnipjuiQ huipg[i: Uuiuigilui& t puipdp Ipupqji pGijhuiGnip rnhupfi luGrpiuirpjipd hmxJmuuipnuSGbpJi ]_ni&i5uiG qnjnipjuiG uiGhpuidb^in b puiijuipuip upujiiuiG, npp hiuGrifiuuiGniil t ^.P.UumuiGgjuiGli [7] huiiiuiGiIuiG upujiiuiGJi luGuiinqp puipdp Ipupqji hmi[uiuiupnu5Ghpfi hunJuip: U.iquignigilui& t, np puipdp liuipqji pGrjliuiGnip inbupji uiGijpuirpupd huiiiuiuuipnuSQbpli hunluip pi5i5uiG qnjnipjuiG [uGqJipp (iIJiuijQ uibuui-pi|uipuiGuiliuiG 5>niGligliuiGbpli huiiluip uiquiui iJiniJintuuiliuiGGbpnil)

huiGqliuuiGnui t n'lpM tqpnppbti:

Srnjg t uipi]ui&,np IjuiiitujuiliuiG hfiujbppijujpuiGuiliuiG ujphqlilpuui}i Ijuitf ^niGljgJiuijli huitfuip qnjnipjniG niGJi pGqhuiGnip inbupji uiGr}puiipupd huii|uiuuipnii5Qhpli hunluilpupq, np{i (5[iiul( piicJnuIuiG IpnSupiGbGinGbpIig ribliQ huiGqfiuuiGnuS t uipi|iu6 uiphrifiljiuuipti pGniptuqpJi^ ^niGljgfiuiG Ipini inpi(mcf ^niGbahuiG: