Введение к работе
Актуальность темп. Алгоритмов „.sue проблемы в алгебро (проблема равенства, сопряженности, изоморфизма и т.д.) возникли еще до появления точного понятия алгоритма. В начале 30-х годов нашего столетия это понятие било уточнено и получены парвыо результати по твори' алгоритмов. На основе этих результатов ^ыли решены ряд важных, алгоритмических проблем, которы не поддавались решению долгое время. Например, П.С.Новиковым [2Ї] била доказана,фундаментальная теорема о неразрешимости проблема равенства слов в творич групп.
С целью привлечения развитой теории алгоритмов для более широкого исследования алгоритмических проблем алгебры в 60-годах было введено лоня.пэ конструкт-эной алгебраической системы. В работах А.Мостовского [34),J35J , «.В.Кузнецова JI2J, [із], А.ірелиха и Д.Шефердсона {ІЗО] впервые, появились коне '-руктявныэ системы. В этих работах в качестве основных множеств таких систем рассматривались либо множества натуральных чисе*, либо множества слов в произвольном конечном .--тфаните.
С другой стороны в теории алгоритмов и ее приложенщ : бчла известна плодотворность введения годелевских нумераций изучаемых объектов. А.Н.Колмогоров вперши отметил важность изучения всех вычислимых нумераций чао.ично рекурсизных функций. Эта программа осуществлялась в работах В.А.Успенского [26j,[27] , X.Раиса [Зб] и Х.Родж.рса [38] .
А.И.Мальцев в своей основополагающей работе [Ї7] объединил эти два подхода и ввел, понятие. конструктивной алгебры. Пояснил -чго на .-тайме, в крупен. Нумерацией группы S) называется отображение і) ; L& -ъ* Q- іїложества всех натураль них чисел ОҐ на G* Пара (G*^^) называется kohcvb-тивной группе.:, если существует алгоритм, ко/ojчи по шэнм
двум натуральним числам XYl и Yl определяет, равны или нот елементи S>YYl к- S* Vb » а такт.о находит такое число S , чтс равенство S^ftt-^Kl = ^ S справедливо в Q- . В этой же работе Л.И.Мальцев сформулировал ряд ванных понятий теории конструктивных алгебр и нелегал программу дальнейших исс 'едо-ваний.
Ю.І.Ершов [VJ ввел понятие сильно конструктивной модели. Конструктивная модель (Tlfl^j называется сильно конструктивней, если существует алгоритм, который по произвольной формуло СіпТ^;..,^..,,} УШ сигнатуры модели otfl и по произвольным натуральным числам Щ„_,. . . ууг, _ определяет истинна или нет формула UL\Ji^TL0>., .} $11. ^.,^) в модели ^0. . Это понятие привело к плодотворному применению методов теории моделей при изучении конструктивных систем. Оно породило ряд новых проблем, аналогичных пробоемам теории моделей, одни из которых уже решены, а другие еще остаются открытыми. В дальнейшем конструктивные и сильно конструктивные модели начали изучаться в теской взаимосвязи,
В настоящее ь^эмя теория конструктивных моделей - бурно развивающаяся область математики, которая находится на стыке алге 'ры, математической логики и теории алгоритмов. Она находит важные применения в теоретическом программировании и в, : теории баз данных. Существенный вклад в эту область внесли как советские математики А.И.Мальцев, Ю. Л.Ершов, С.С.Гончаров, М.Г.Пзретятькин, так и рдрубелшыэ - P.Boot, Ы.Морли, А.Нероуд и другие. Основные проблеми и результаты данной области изложены в мое графин Ю.Л.Ершова \ъ\ .
Основными проблемами (см. J5, с.ЗОСу) теории конструк -тивных моделей являются:
Ї) проблема существования (сильной) ковструктивизации у заданной модели;
-
проблема существования (сильно) конструктивизируемой подели у заданной теории;
-
проблема перекоса, единственности конструктивизаций, и т.д.
Исследована, этих проблем проводятся как длч общей теории -оделей, та: и длу ко.лсретных классов алгебр. В настоящее время .зчболее полно изучены проблемы конструктивных булев' : ал-
гебр. Основино результати этой ооласти изложен» в ионограсдои С.С.Г> ічарова [f\ .
Исследования по теории конструктивних аболевнх групи начаты работой А.И.Мальцева |l8j . Здесь Л.И.Мальцев следующим образом характеризует проблемы данной области: "остоствопь возникает общая задача - определить, какие конетру тиенно нумерации допускают те или иные аоотрактно задашшо группы, какие из подгрупп -той или иной конструктивной группы является 09 рекурсивными или рекурсивно поречисл; ыми подгруппаї.а, и т.н." Конструктивные абелевн группы в дальнейшем исследовались з раоотах D.Л.Ершова., С.С.Гончарова, В.Д.Дзгоева, В.П.Добрица, С.Лин, А.В.Молокова, А.Т.Нуртазина, и.Ричшнз, П.Смксэ и других.
Целью оаботи является исследования указан ж проблем в теории конструктивних аболевнх групп.
Ооно в) пт: г,;о тодзтли являются комбинации методов приорито-та, теории нумераций и построения групп порождающими эяогон-тами и определяющими соотношениями.
Научная новизна. Все основные результаты диссертации яв
ляются новыми. В работе ешэна основное проблемы теории кон
структивных абелевых групп. Проблема сущестг вания конструк-
тивизаций абеловой р -группы А оводона к оценкаг. алгорит
мической сложности подгруппы А элементов бесісонечноіі высоты
и.фактор-группы А/А .' , что является первым результатом
такого типа з теории конструктивных моделей, ^ терминах базис
ных формул, описаны теории абелевых групп, имеющие конструкта
визируемте модели. Решена проблема соотношений, конструктиви-
зируемости и сильной коштруктивкзкруакасг моделей колгсіх
теорий абелевых групп. Установлена cov-'ноиеиия классов ариф
метической иерархии для абэлэшх групп без кручения, р-групп
и периодических груші. Ка основа поггченныХ'-результатов pi лен
ряд широко лзвос.лщх вопросов Теорий конструктирчых Селевых
групп. ' ',. .
Пра-'ткческ"і и : ,о\ дтическая ценность. Результаті- р. боти представля-.р теоретический интерес. Он.! нашли применения в ть -ории конструктивных полей и общей теории нумераций. На ос.^ве результатов д. ^сертации были прочитаны спецкурсы в Казахском Государственном Университете.имени С.М.Кирова и написаны jrm-
ломныз и курсовые работы. Они таете могут быть использованы в дальнейших 'исследованиях по теории конструктивных моделей, при чтения спецкурсов.
І т>обация работы и публикации. Содержание диссертации п. частям докладывались на общегородском семинаре "Математическая логика" г.Ллма-Лты, на итоговых конференциях Института математики и механики АН КазССР; на семинарах "Теория нумераций", "Теория конструктивных моделей", "Алгебра и логика" Ыо-1 -сибирского Университет^, на общеинститутском математическом семинаре ИМ СО АН СССР, на "-й Зсесоюгчой школе по прикладной логике; на П - IX Всесоюзных конференциях по математической лс тасо; на XII - XIX Всесоюзных конференциях по алгебре; на Международной конференции по алгебре, посвященной памяти А.И.Мальцева (1909-1967); на пленарных докладах 6-й и 8-й Всесоюзных конференциях по математической логике. Все основные результаты опубликованы в статьях [41 - 60] . Результаты совместней работы {4lJ получаны в нераздельном соавторстве. Остальные результаты диссертации получены лично автором.
Объем и структура работы. Диссертационная работа состоит
из введения, трех глав, разбитых на 13 параграфов и списка ли
тера ...уры, насчитывающего 90 наименований. Общий объем работы
293 страницы. , "