автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.16, диссертация на тему:Исследование рекурсивных схем на конечных моделях некоторых нетрадиционных арифметических теорий

НАЦИОНАЛЬНАЯ АКАДЕМИЯ НАУК РЕСПУБЛИКИ АРМЕНИЯ И ЕРЕВАНСКИЙ ГОСУДАРСТЕННЫЙ УНИВЕРСИТЕТ Институт проблем информатики и ннтоматигл.тции

од

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

^ 1^ Машурян Лшот Сергеевич

УДК 517.11

ИССЛЕДОВАНИЕ РЕКУРСИВНЫХ СХЕМ ITA КОНЕЧНЫХ МОДЕЛЯХ НЕКОТОРЫХ НЕТРАДИЦИОННЫХ Л РИФМЕТИ MEf Ж ИХ ТЕОРИЙ

Спсщтлыюсп, 05.13.1 в - Применение нмчнели гелы/пи чих пики, математического моделирования л математических молояоп

II imV'IIIhlX ИССЛГ'ДППЛГШЯХ

АВТОРЕ ФЕРА Т

диссертации на соискание ученой счепсии кандидата физнко-математических наук

Ерошш - 1005

Работа выполнена на

кафедре: высшей алгебры и геометрии

Ереванского государственного университета

Научный руководитель - к-шдндаг ф.-м. паук

старший научный сотрудник Г.Б.МАРАПДЖЯП

Офипиалып.и: оппоненты - диктор ф. м. паук

профессор И.Д.ЗАСЛАВСКИЙ кандидат ф.-м. наук доцент Д.Л.ЧУКЛРЯН

Ведущая организации - Государственный инженерный университет 1'Л

Защита состоится " " — 1995г. ц 11U,J часов на заседа-

нии специализированного совета К005.21.01 по присуждению ученой степени кандидата паук в Институте проблем информатики и автоматизации Национальной AII РА и ЕГ5' по адресу: 375044 г.Ереван, ул.И.С'епака, I.

С диссертацией можно ознакомиться а библиотеке ИПИА НАМ РА и ЕРУ. л q

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

Ученый секретарь специализированного совета L К0()Г>.21.01., к.:>.н.,('..нх. С@

Л. 10. МЕЛКОЙ Я И

ог>щля характеристика pauoti.i

Актуальность темы. Унар - достаточно гибкое, универсальное j 1 о 11 и ■ I ■ 11 и и поэтому является объекз-ом исследований специалистов разных разделом ма тематики. 13 частпости^ычислиз-ельные возможности yimpon интересовали, начинам с к Jim: nimm оспой мин'машм! Дедекинда и Гильберта, многих специалистов в области математической логики и теории алгоритмов. В предлагаемой работе шюдит-«я поня тие харак i-еристики упара, с homuiui.io которой получен ряд результатов, дополняющих, обобщающих, а иногда, и у точняющих некоторый известные результаты. Тик, И главе I обобщена теорема о гомоморфизме1 (теорема!.2.2); сущестпопание операций сложения и умножения и произвол!.пом унаре, н отличие от доказательства Кальмара2 , установлено без апеллирования к ак туально Оескопеч ному натуральному ряду.

Н глане 11 установлен бесконечный класс у нарой, и которых определена функция xv, чем уточняется соответствующий резуль гаг Гильберта. Методы, развитые и глане II, позволяют запершить решение одной проблемы Гжеторчикп чнезичцо решенной 1'ецнн гом 4.

1 Геон llelkin. On iimUieinaUcal induction. The American Mathematical Monthly, V.67, N4, April,1960 (n русском переводе Л.Генкии. О ма тема тической индукции. Гос.издание физ ма т.ли гера туры. Моек

' Da, 1062).

2 Acta .4ei.Mal.li.(.4zegod) V.O.N'l,HMO, p.227-232.

Grzegorczyk A. Some classes of recursive functions, llozprawy Maternal,icy,не, IV, VVaiH/awa, 1953. (n русском переиоде А.Гжегорчик. Некоторые классы рекурсивных функций, в сборнике Проблемы математической логики, Мир, Москва, 1970, стр.9-49.)

1 Hoddintf I). Uber ilie Kliiniiiierkek von ПеПнИionHclietnata in der Tlieirie der rectirsiven Functionen, Z.inath.Logik und Grunlag. der Math., 10, N4, 10G4, p. 315-330.

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

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

1. Изучение унаров (в связи с тем, что они являются носителями спойстпа индукции) с точки зрения возможности реализации на них рекурсивных схем.

2. Изучение у нарой, как конечных моделей некоторых формальных теорий первого порядка.

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

11 аучная новизна и теоретическая ценность. В работе:

1) введено понятие характеристики унара, которое позволяет полноценно исследовать механизм построений но индукции;

2) установлены критерйи представимости арифметических

функций на конкретном унаре и на всех уларах;

3) введен универсальный способ задания цслозначпых функций, а именно, через разложение и ряд Полин15. Понятие ряда Полна вводится нами впервые исходя из задач о целоэначных полиномах которые можно продолжить до бесконечного ряда и виде конечных линейных комбинаций биномиальных коэффициентов;

'1) установлен клпсс всех /Ш-функций, продстапимых iia всех унарах;

б) решением одной из проблем Гжегорчика продемонстрирован новый метод решения задач теории рекурсивной функции;

б) введен ряд новых формальных теорий (//-арифметики), допускающих конечные модели.

Апробация работы. Результаты диссертации докладывались в ВЦ АН Армении (1972,1004), на Всесоюзной конференции по теории графов (Одесса, 1073), на семинарах кафедры математической логики МГУ (Москва, 1978, 1981, 1985), на I и II Республиканских научных конференциях преподавателей вузоп Армении (1983, 1985), на VIH Всесоюзной конференции по математической логике (Москва,108(1), па семинара но теории нумерации ИГУ (Новосибирск, 1983), на семинаре ф-та прикладной математики ЛГУ (Ленинград, >1990) и на семинарах кафедры высшей геометрии и алгебры ЮГУ.

// у б л и к а ц и и. Основные результаты диссертации опубликованы в 13 статьях.

Структура и объем диссертации. Диссертация изложена на 78 страницах машинописного текста, состоит из введения и трех глин. Библиография содержит 37 иинмоиопниий.

СОДЕРЖАНИЕ РАБОТЫ

5 Г.Полна, Г.Сеге. Задачи и теоремы из анализа, т.1, Паука, 1978,

Москва.

Ло ааедснчи излагается нредистория попросоп, исследован-иых н диссертации, обосновьюастся актуальность темы, формулируется цель работы, научная новизна и теоретическая ценность полученных результатом. СдслЬи краткий обзор литературы, рассмотрены структура и содержание диссертации и определено понятно уппра, как алгебраическая структура (А, ас одной нульместной (ао) и одной одноместной (у?) операциями, удовлетворяющая следующему требованию, называемому аксиомой индукции: если 1) X С А; 2) п„ 6 Л'; 3) х £ Л' - ф) € Л\ то Л' = А.

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

Б первом параграфе вводится понятие орграфа унара. Доказывается классификационная теорема (теорема 1.2), дающая качественный перечень множества всех унаров. Это: 1) счетно-бесконечный унар (имеет "бесконечно длинный" хвост и не имеет кольцевой части); 2) унар с т (т > 0) элементами на хвосте и с к (к > 0) элементами на кольце и 3) унар без хвоста и с п элементами на кольце.

Далее, вводится понятно характеристики унара - носи геля основных свойств унара. Унару 1) приписывается характеристика (оо,0), унару 2) - характеристика (т, к) и унару 3) - характеристика (0,п).

Но втором параграфе исследуется вопрос о гомоморфизме унаров. Устанавливается критерий гомоморфизма между уларами, а именно:

Теорема 2.2. Для того, чтобы унар характеристики (т^гн) Пыл гомоморфен унару характеристики (*г»2, пэ), необходимо и достаточно, чтобы выполнялись требования:

1) »щ > Ш2, 2) »1 кратно иг.

Эта теорема обобщает аналогичный результат Генкина1, где рассмотрен только случай тх = оо, г»1 = 0 (случай бесконечного унара - унара Пеано).

В качество следствия устанавливается, что с точностью до изо-мо{)(]шости существует только один унар данной характеристики.

В третьем параграфе приводятся некоторые применения теоремы о гомоморфизме. ( )|1|)сд'м1я1' I си пкмм ! iii' реализуемости рекурсивной схемы в унаре и доказывается, что рекурсивная схема для сложения реализуема н любом унаре (чеорема Л. I). Лпплогичпвй факт устанавливается и для операции умножения (теорема 3.3). Далее показывается, что схема для ноказатслыю-степспной операции реализуема не н любом упиро. Далее устанавливаемся (теорема 3.5 и 3.0), что гомоморфизм между упарами является также гомоморфизмом в арифметической сигнатуре =< 0, ', +, ^ =>.

В четвертом параграфе исследуется вопрос о переносе сигнатуры произвольного унара на гомоморфный ему унар. Доказывается свойство транзитивности такого'переноса (теорема ^Л).

Теорема 4.2. (о сигнатурном переводе). Пусть уиар 3£ гомоморфен упару СТ, и Й удовлетворяет некоторой сигнатуре Тогда существует такая реализация ]Г] в Зи, что данный гомомор<]|изм 9{ на О является Iомоморфизмом между зтими упарами также в сигнатуре

Е-

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

В первом параграфе определяется понятие представимости функции в данном унаре.

Определение. Функция f(xj,..., хп) называется представимой в данном унаре если существует такая операция F{x\,..., х„), определенная и унаре ili, что при любых xi,...,xn имеет место равенство

1"Эг/(®1. • • м»п) = ^(TTKri, • • • > 7T3ii„)i

где тгвг - гомоморфизм унара ш па унар

Далее устаиаш/инаются критерии представимости.

Определение. Функция /(ж) называется

a) m-надаргументной, если при любом х > т имеет место неравенство f(x) > х;

b) падаргумеитной, если она m-надаргумептпа при любом т £

N;

c) (г, т, гг)-периодичной, если для любого к (Е N имеет место сравнимость

/(» -(- т •)- кп) ~ /(» т) {mod н)

d) (т, п)-периодичной, если она при любом г 6 Я (г, т, п)- периодична;

e) абсолютно периодичной, если она (гп, п)-периодичпа при любых т,п 6 N,n ф 0.

Теорема, (критерий локальной представимости). Для того, чтобы m-надаргументная функция была представима в унаре характеристики (гп, п) необходимо и достаточно, чтобы она была (т, п) -периодичной.

Теорема, (критерий абсолютной представимости). Для того, чтобы функция была представима в любом унаре, необходимо и достаточно, чтобы она была надаргументной и абсолютно периодичной.

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

в данной работе вопросах, между функциями одного аргумента и нескольких аргументов не имеется: многомерный случай непосредственно сводится к одномерному. Например, критерий абсолютной представимости для многомерного случая выглядит следующим образом: для того, чтобы функция /{х\, ■ ■ ■, хп) была нредставима в унаре 3?, необходимо и достаточно, чтобы она была нредставима в 3? как функция одного любого аргумента при фиксированных значениях остальных.

В третьем параграфе строится теория рекурсии данного унара Рассматриваются базисные функции 0(х), в(х), 1/™(х1,..., хп) и операторы подстановки и примитивной рекурсии на С помощью этих построений, обычным способом, определяется класс - примитивно рекурсивных функций. Устанавливается, что этот класс замкнут относительно оператора подстановки и явных преобразований, по но замкнут относительно оператора примитивной рекурсии. П качестве следствия из этих построений получается утверждение: надаргумептный многочлен с целыми коэффициентами является А11-функцией, т.е. функцией, представимой со всех унарах.

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

Пусть последовательность функций /о, Д,... задается следующими рекуррентными соотношениями:

/о(я. 2/) — У + 1,Ых,у) = х + 11,/2(х,у) = (х + 1)0/+ 1) при п > 2, /„+1(0, у) = /„(у + 1,»/+ 1), /п+1(г + 1,у) = /Рп+1(х,/п+х(х,у))

и пусть Гп - наименьший класс функций, включающий функции у), н(х) = т. -!- 1, и-1(х,у) ~ х, Щ(т,у) ■ — у и замкнутый относительно операций подстановки и ограниченной рекурсии. Требуется определить - можно ли в построении классов = 0,1,...)

использовать (при тех же базисных функциях) только операции подстановки. Д.Рсдингом4 дан положительный ответ для п > 3. Нами доказывается (теорема 4.1), что ответ на поставленный вопрос для клиссои Гц, I'i, Га отрицательный.

В §5 устанавливаются области представимости (множества уна-роп, и которых данная функция нредстаиима) некоторых функций. В частности, установлен бесконечный класс унаров, в которых представима функция х", чем опровергается утверждение1 о том, что эта ; функция представима только в унаре Нсано. А именно:

Теорема 5.1. Функция xv представима во всех упарах, характеристика (ш, п) которых, при некотором к £ ш, удовлетворяет условиям: n = 2к, т > к.

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

В §6 исследуется класс AU - функций. Вводится понятие ряда • Полна и доказывается, что любая целозпачпая функция может быть, при этом единственным образом разложена в ряд Нолиа, то есть

представлена в вида

; - . /■-£>(;)

<=0 ; 4 '

где <ц (»' = 0,1,...) - целые числа, a f = - бино-

миальные коэффициенты.

. Затем доказывается основная теорема, а именно Теорема G.3. Для тот, чтобы надаргумоитная функция принадлежала классу AU, необходимо и достаточно, чтобы се коэффициенты аь(к = 2,3,...) удовлетворяли условию: а* = 0 (mod Мь), где М* - наименьшее общее кратное совокупности чисел {2,3,..., к). Далее основная теорема обобщается на,многомерный случай: Теорема G.4. Для того, чтобы надаргументная функция f(x 1,..., хп) была AU - функцией, необходимо и достаточно, чтобы

п ос разложении и ряд Полна

.....«->=£•••£>......•■<• С-)•••(")

коэффициент n¡¡ in был кра тен наименьшему общему крапюму совокупности чисел {2,3,..., iti«x{«i ,...,;„}}.

В третьей главе вводятся и исследую ! ся некоторые новые

формальные теории первого порядка в сигнатуре =< 0, 1', +, ■,

немцовской арифметики, названные ЛЛ арифме тиками.

13 §1 определяются //-арифметики: AS (абсолютная арифметика), MAS\, МЛЯ2, АМ\, ЛМ2. Абсолютная арифметика получается из пеановской арифметики S устранением из числа собственных аксиом последней двух следующих аксиом: (14) x'¡ ф 0 и (1'2) х[ = х'2 Э = Остальные //-арифметики получаются из абсолютной арифметики добавлением одной или двух из аксиом (14), (Р2) или их отрицаний. _

Г? §2 доказывается, что псе .чти лрифмезики непротиворечивы и неполны.

В §3 исследуе тся вопрос о представлении функций в абсолю тной арифметике. Доказывается, что /t.S'-вредс занимая функция рекурсивна и абсолютно унарно прелс тавима, то ген. принадлежит классу функций ItAU.

ОСНОВНЫМ 14;!)У.II 1/ГЛТЫ РЛГ.ОТЫ

1. Классификационная теорема, позволившая провести естественную классификацию во множестве всех уваров, на основе ко торой введено понятие характеристики упара - основною носителя свойств унара.

2. Теорема о гомоморфизме, устанавливающая критерий гомо-морфп'ости унаров.

'3. 'Георома о существовании операции сложения в любом унаре.

4. Теорема о существовании операции умножения в любом уларе.

5. Теорема о сигнатурном переводе, позволяющая обогати ть язык унара с помощью языка его гомоморфного образа.

Г>. Необходимое и достаточное условие для представимости' арифметической функции в данном унаре.

7. Необходимом и достаточной условие для представимости арифметической функции во всех унарах.

8. Решение одной из ноблем Гжегорчика.

9. Теорема о разложимости произвольной целозначпой функции в рил Полип.

10. Необходимое и достаточное условие для коэффициентов Полна абсолютно унарно представимой функции.

11. Теорема, о классе функций, прсдстанимых в абсолютной арифметике.

По теме диссертации опубликованы следующие работы

1. С) рекурсивных определениях пи индукционных моделях, ДЛИ Арм.ССТ, т.IX, N4, 1974.

2. Об одном классе нримитинпо рекурсивных функций, ДЛИ Лрм.СХЛ', т./Х1, N1, 1979.

О классе прими тивно рекурсивных функций, определимых на конечных моделях, ДЛИ Лрм.С'С!', т.ХХ!, N4, 1980.

4. Арифметика на конечных фрагментах натурального ряда, Тезисы докл. I республиканской научно-методической конференции, I!Ж.Ч, Кревап.

5. Нримитинпо рекурсивные функции па унарах конечной характеристики, Межвуз.сб. "Математика", N2, 1984.

6. О некоторых применениях теоремы о гомоморфизме унаров, Тезисы докл. XVII Исссоюзпой алгебр,конференции, 1983, Минск.

7. Варианты ненеапопских арифметик, Тел и г. 1.1 докл. II республиканской ппучпо-мо чодичег.кпй конференции, ИЖ5, Кирниикин.

8. Свойство индукции и рекурсивные cxeMi.t, Межнуч.сб."Математика", N3, 1985.

9. Непротиворечивость некоторых теорий первого порядка, Можпучхб. " Ми гс.ми.гика" , N3, Н)ЯГ>.

10. О спектре; арифметических icnpufl, Течиг.ы докл. VIII Пег союзной конференции по математ ической логике, 1986, Москва.

11. Унарм и функции, нрсдставимые па унарах, 191)1 (демон.) 4Л201 в Лрм.ИИИИТИ.

12. О к л nr.ee абсолютно унарно нредг.тммимых функций, Ученые записки ЕГУ, N1, НИИ.

13. Ряды Полна и представимость функций в конечных моделях некоторых арифметических теорий. Ичвсглия ЛИ 1'Л "Мнчемати-ка", N1,1995.

U¿nu) Uiu¿ui|ijui(i

" Muipqpüpmg ufubtiujfibpf» hbimuqniniutln nPn2 uiiJujünu»liujri |)i|uj(.'ui(4iu[)|(ii(i(jti|i|i iJL|iytui(ii|i liiuüqniüujljúbpfi i|puj "

llu)hriui|iii!tiiiippiifip (íi||i|ii|mi/> t ti; i) 11 j u i u 11 (11 Ti upn? pijuipuinmpjiufiril¡p|i li ()|ku(kj i(li|i2iiii(ii{i liuiüc|mütxjl|üü|i|r iuGujpübp|i niuiuúümu|i|iiupjuiúii: Rbtmuqnini[bL bG prqnp tuGuipGüpf! i^ojuq, GpuiGg htuGpiuhui2i|ujl)uiq hiuuil|nipjruGGbp|i L ábuirjpuilpuG inbumpjmGGbpo' M-piluipuiGrupjntGGbpo: UiiiliGui|unumpjm(iiiirt qquij|i tiiliit L liniuil|ui(ji|uió pi|iupinGuil|Uifi, liiuuit|(uu|Uu l|uipq[ilipujg, uinntjpGt¿p|i luGwpübpiui) Güpujl)iiugi(ti[ni b uiju (|(iu1 üijG M pt|uipiiiriittp|nif«iul ui|\iauiluu|(iu|t¡|(u hGuipuiij<i|uupjtufitH¡|i[y. lUiit)(iui|iiniiuipiullj Ii|uIImiI|iuU uijti)jiuüi>übpü Gli tu) Hiuuujliuipqúiuú qbpiupbpjujL úiuljiuunijpB. npQ liGiupiuiJnp t qiiipófinul prnul|iuGiipGri ipiiimi(|i»pqb| niGuipribpi!, |ifi¿|i h|iiluifi i|pui ti lili|iiiiói(lii I (ii<mi|i|i liuiwil|iupjm(iíiGp|i li|ulGdi(|ui(j l(p|i¿|r iuGuip|) p(iiHpuiqp|i¿ji i|uniuii|uupp:

p) ii)ii)iuiM>iiipjiii(i i|liputpli)i)tti| iínil|uiiiiujp|), i)pm| inpi|iuii t

nibu>pbbp|i tiuiúuidb t|iGü(ni liuijuiuiü|i2o:

q) 3mpuj£UjG¿jiup luGuipnid qniiliupúiuG qnpónqnipjujG qnjmpjujG (|Upni[!Gpjuj| riuit|iuunijpn:

q) ¿Jiupun>iuli¿jmp «iGuipiuú puiqiliuu)uiuitji5uiG qnpánqiupjuiG qnjnipjuuü ilbpiupbpjmi i5u)l|tuunijpp: " .

li) 'l|()IIIUll||l pi(ip(|lllll(llllpjlll(l l|lipUI|llip)llll llHll|llllllllJp|l, ll|l(l

liUuipuiiliipnipjiitú t quipáGiuú npbt niúuipji (bqil|i huipumiugniiíp GpuiG huidmáb ntGaipfi |bq4h újigngnq:

q) Spi|iuó ni&uipmú ptluipuiGuil|uin tunnijp|t Gfopl)iujuigQbt|i j|iGb[iu uiGh|iuj()b2ui b pun{iupiup u|uijúuiG[):

. t) Piipip ninuipGtipniiS pijui|miruiil(iufi ■ lunmjpfi Gbpl)Uijmgrib||i ||iliG|ni iii(ili|iui(ili/((i li piiti(ui|iii<|i u|uijtliu(i[i

O) <WGqnp¿|ilih pbp|i [nióiluió ú|i (uüqpti i[bpgGiut)UjG inióniúi): p) UúpnqgaipdbpuiGli uinnijp|i' ^niJiuijli ¿^Pí?!1 tlbpiniób|[i ||iGbini i|lt|iiiipGpjiii| i)iiil|uiiinijpi!

d) PmguipóuiljnpbG Gbpt|injujgGbiti iunnijp(i Tlnifiujj|i qtipótt)l||i<jGbp|i ijlipmpbpjuq uifilijinKJli^in'U puii[iupuip U|iujúuiGi}.

|i) Puigutp¿uil| pilmpiuGnipjniGniú Qtspt|UijuigQbi|i iunnijpGbp|i quiuji i[li|im|.'Gpjmi úiitl|imjiujpu: