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

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

Механико-математическим факультет

РГ6 ОД На правах рукописи

О9 ФЕВ 1993 удк5ю

ДУРНЕВ Валерий Георгиевич

ИССЛЕДОВАНИЕ НЕКОТОРЫХ АЛГОРИТМИЧЕСКИХ ПРОБЛЕМ ДЛЯ СВОБОДНЫХ ГРУПП И ПОЛУГРУПП

01.01.06 - математическая логика, алгебра и теория чисел

АВТОРЕФЕРАТ

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

Москва - 1997

Работа выполнена на кафедре алгебры п математической логик! Ярославского государственного университета им. II. Г. Демидова

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

доктор физико-математических наук, профессор Н.К.Косовский

доктор физико-математических наук Г.С.Макании

доктор физико-математических наук, профессор М.Л.Тапцлин

Ведущая организация:

Санкт-Петербургское отделение Математического Института имени В.А.Стеклова РАИ

Защита диссертации состоится года

в 16.15 на заседании диссертационного совета Д.053.05.05 при Московском государственном университете имени М.И.Ломоносова по адресу: 119899 ГСП, Москва, Норооьевы горы, МГУ, механико-математический факультет, аудитория 14-08.

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

Автореферат разослан ".....1998 года

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

профессор В.Н.Чубарнкон

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

Актуальность темы. Первым примером неразрешимой алгоритмической проблемы, возникшей вне математической логики, послужила проблема равенства слов для полугрупп (ассоциативных систем), сформулированная А.Туэ в 1914г. задолго до появления самой теории алгоритмов. Алгоритмическая неразрешимость проблемы равенства слов для полугрупп была установлена в 1947г. независимо А.Л.Марковым1 и Э.Постом.2 В 1952г. U.C.Новиковым3 была доказана алгоритмическая неразрешимость проблемы равенства слов для конечно-определенных групп.

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

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

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

Основное содержание диссертации и прежде всего двух ее первых глав вписывается в указанную программу С.И.Адяна.

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

^lapKon Л.Л. Невозможность некоторых алгорифмов н теории ассоциативных систем // ДЛИ СССР. 1917. Т.55. С.587 - 590.

2Post К. 1 < И'ТШмvr unsolvability of a problem of Time // Л. Symbolic Logic. 1947. V. 12, N 1. P. 1 - 11.

MlomiKon U.C. OG алгоритмической неразрешимости проблемы тождества теории групп // ДАН СССР. 1952. Т.85. С. 709 - 712.

4 Мальцев Л.И. О некоторых пограничных вопросах алгебры и математической логики // Междунлр. конгр. математиков. Москва, 19GG. М., "Мир", 1968. С.217 - 231.

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

Результаты первой и третьей глав диссертации вписываются в указанную программу А.И.Мальцева.

Цель работы и научная новизна. В диссертации исследуются простые фрагменты элементарной теории свободной полугруппы с целью установления их алгоритмической неразрешимости. Рассмотрены некоторые алгоритмические проблемы для уравнений в свободных полугруппах и группах, связанные с вопросами о существовании решений с теми или иными свойствами, доказана их алгоритмическая неразрешимость. Исследовано несколько алгоритмических проблем для дпофантовых множеств в свободных полугруппах с целью установления их алгоритмической разрешимости пли неразрешимости. Установлена Л^'Р-полнота проблемы разрешимости уравнений в свободной полугруппе, не содержащих переменных в правой части, а констант - в левой. Исследованы простые фрагменты эле- ■ ментарных теорий относительно свободных групп разрешимых многообразий групп, а так же целочисленных линейных групп: общих, специальных и проективных.

Все основные результаты диссертации являются новыми. К основным результатам диссертации можно отнести следующие:

1. Доказана алгоритмическая неразрешимость позитивной УЗ3-теории свободной нециклической полугруппы, а также следующих двух фрагментов элементарной теории свободной полугруппы 113 со свободными образующими «ь аг, <'з:

а) множества формул вида

15

(Вш)(У1/)(3.г1)(В.г2)(В.г3)(\/ = ''О.

¿=1

где 111, хц - слова в алфавите {и1, у, ;Г1, :г2, ,гз, ,02, аз},

б) множества формул вида

(Ни1) (Уу) (З.Г1)... (З.гц) (и = т.),

7ie и. v - слона в алфавите {w, у, ,ri,..., .Гц, (i¡, я2, яз}.

2. Доказана неразрешимость ряда алгоритмических проблем 1ля уравнений в свободных полугруппах и группах, в частности, [оказаны следующие утверждения:

2.1. при любом }>7 > 2 можно указать такое число н, такое множество Л С { {i,j} | 1 < í< j < п } и такое однопарамет])нческое ;емейство уравнений

w(.r, .гь ...,.г„,Я1, я2) - и(.г,.гь ...,.гп,яья2)

' неизвестными .('i,.....г„, константами «1,я2 и параметром .г, что не

:уществует алгоритма, позволяющего для произвольного натурального числа к определить, имеет ли уравнение

ш(Я[, .г х......г„,я1,я2) = u(«i',.ri,...,.rn,aba2)

гакое решение < A'i.....Хп > в свободной полугруппе II,,,, что при

{i,j) € /1 совпадают п])оекцпн слов X¡ и Xj па каждую из образующих Я1 11 Пп\

2.2. для любой свободной группы Fm со свободными образующими fli, . .. , am (m > 2) можно построить такое уравнение

u)(.г, .гь . . . , Хп, яь (12 ) = 1

с неизвестными .14,.г2,.....сп, константами а\, я2 и параметром

.г, что не существует алгоритма, позволяющего для произвольного натурального числа к определить, существует ли такое решение .71, ••■. 9п уравнения

ш( а\. Ti, ... , ,гп, «ь я2 ) = 1,

что

3: е Fr\l\ ..., д, е f,\¡\

где Fp,1' - коммутант группы Fm, а I - некоторое фиксированное число между 1 и )?;

2.3. при любом m > 3 не существует алгоритма, позволяющего по произвольному уравнению в группе Fm

VU{XU ...,.Т„,Я1, ...,я,„) = 1

определить имеет ли оно такое решение д\.....д„, что дi £ /'„,, гд

Рт - двойственная коммутанту подгруппа группы F,n.

В то же время доказано, что существует алгоритм, позволяю lmifi по любому уравнению с одним неизвестным

w{xu оь ... , а,„ ) = 1

в группе F,n определить имеет ли оно такое решение д\, ч то дi £ Г-! где И - либо s—п коммутант группы Fm, либо s-ft член (F\n) ее нижнего центрального ряда, либо подгруппа Рт.

3. Доказано, что проблема разрешимости уравнений в свободно! группе Fm линейно сводится к проблеме разрешимости уравненш с одним коэффициентом и группе F„,+ i, а проблема разрешнмогп систем уравнений в группе Fm полиномиально сводима к проблем! разрешимости уравнений с одним коэффициентом в группе Fm+i Установлена Л'Р- трудность проблемы разрешимости для уравие нин с одним коэффициентом и свободной нециклической группе.

4. Для относительно свободных групп конечных рангов разре шнмых многообразии групп доказана их различимость пози тивным! формулами с приставками типа V""3V" при подходящих ?н п п, тел самым для них решена проблема Л.Тарского.

5. У*-тсорня группы G - это множество всех истинных на труп не G замкнутых формул, предваренная нормальная форма которы: содержит лишь один кванторный блок, причем он состоит из к кваи торов V.

Доказано, что при п > т группы ClL(n.Z) и GL(m,Z) PGL(n,Z) и PGL{m,Z), SL(n.Z)" и SL(m,Z), PSL{n,Z) i PSL(m, Z) имеют различные \/2-теорпн,' более того, если п-четно< число, либо »-нечетное число, но при этом » > т + 1, то V1 -тсорш указанных групп различны.

При нечетном п V1 -теории групп SL(п, Z),SL(n— 1, Z), а такж< групп GL(n,Z) и GL(n — 1 ,Z) совпадают.

Это усиливает результаты Л.И.Мальцева5 о несовпадении npi п > m элементарных теорий групп GL(n,Z) н GL(m,Z), PGL(n,Z н PGL(m, Z), SL{n,Z) n SL{m\z), PSL(ii,Z) n PSL{m,Z).

G. Доказано, что для свободной метабелепой группы ^(©2) ран га 2 со свободными образующими а,Ь имеет место эквивалентнос ть

J Мальцев Л.И. Об элементарных свойствах линейных групп // Нскоторьи проблемы математики и механики. Новосибирск, 1961. С.110 - 132.

G

аналогичная известной 'жвпвалеитпостн Л.И.Мальцева для свобол-моп группы

для элементов y,h группы А(6з) разрешимо относительно с «дно из уравнений

ф.ф-1 = МГ (с G {-1. + 1})

тогда п только тогда, когда </,/( - свободные образующие группы F2 (©•>).

Ото позволило доказа ть алгори тмическую неразрешимость позитивной 3-теории с одной константой любой свободной исабелевой разрешимой группы.

ОПщиг ммгоды исследования. Проводимые в диссертации исследования базируются на следующих фундаментальных результатах математической логики и теории алгоритмов: теореме о существовании конечно определенных полугрупп с неразрешимыми проблемами равенства слои, доказанной независимо Л.Л.Марковым1 и ').11octomj. теореме Ю.Н.Матпясеппча6 о существовании полугруппы с :5 определяющими соотношениями, имеющей алгоритмически неразрешимую проблему равенства фиксированному слову, теореме М.Минского' о неразрешимости проблемы применимости для операторных алгори тмов, теореме Ю.Н.Матпясевпча8 о дпофантопостп рекурсивно иеречпелимых множеств.

И диссертации используются общие методы математической логики и теории алгоритмов: для установления алгоритмической неразрешимости проблем к ним сводя тся известные алгоритмически неразрешимые проблемы. Для установления A''P-трудпостн проблемы к пей полиномиально своди тся известная А'Л-трудпая проблема.

Практическая и теоретическая ценность. Работа носит теоретический характер. Ее результаты могут быть использованы при исследовании алгоритмических проблем для групп и полутрупп, при изучении фрагментов '»лемен гарпых Теорий групп и полугрупп.

"Млтмяггвпч Ю.В. Простые примеры неразрешимых ассоциативных исчислений // ЛАМ СССР. ИШ7. Т. 17.3, N(i. С. 12(11 - Г2(;0.

' Minsky M.I,. Recursive inisolvability '>f Post's problem of "TAC!" ami topics in theory of l uring machines // Ann. Math. Н)Г>1. Y.71. P. 1.37 - 1!i.r>.

*Матиясевнч Ю.В. Днофлнтовос-i i, церечпслпмых множеств // ЛАП СССР. 1!)7(>. Г. 130. N3. С.1ПГ» - -198.

Апробация работы. Результаты диссертации докладивалнп па семинарах кафедры математической логики и теории алгоритмом механико-математического факультета МРУ: семинаре но математической логике под руководством чл.-корр. РАН. профессор; С.И.Адяна и профессора И.А.Успенского, семинаре но алгоритмическим проблемам алгебры иод руководством чл.-корр. РАН, профессора С.И.Адяна, на семинаре лаборатории математической логикг ПОМ И им. Н. А. Стек лова РАН иод руководством чл.-корр. РАН, профессора Ю.В.Матиясевича, на алгебраических семинарах в ТГПИ ЯрРУ и МГИИ, на IV Всесоюзном симпозиуме по теории групп (Новосибирск,1974), па III Всесоюзной конференции по математической логике (Новосибирск,1974), на IV Всесоюзной конференции по математической логике (Кишинев, 1976), па VIII Всесоюзной конференции по математической логике (Москва, 1970), на XIX Всесоюзной алгебраической конференции (Львов,1987), на X Всесоюзной конференции по математической логике (Ленинград, 1988), на XI Всеосюз-ном симпозиуме но теории групп (Свердловск,1989), на Международных конференциях ио алгебре (Новосибирск,1989 и Барнаул, 1991), на Международном симпозиуме "Логические основы информатики" (Ярославль, 1997).

Публикации. Основные результаты автора по теме диссертации опубликованы в 18 работах, указанных в конце автореферата.

Структура и объем диссертации. Диссертация состоит из введения, трех глав, списка литературы (182 наименования) и занимает '202 страницы машинописного текста.

В работе принята следующая нумерация теорем: теоремы нумеруются в пределах главы, причем они снабжаются двойным номером типа п.111, где и обозначает номер главы, а ш-норядковмй поме]) теоремы в пределах этой главы.

СОДКРЖ А И И К Д И С(' К РТА Ц И И

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

И первом параграфе исследуются фрагменты элементарной теории свободной полугруппы. Еще в 1910г. В.Куайн9 доказал алгоритмическую неразрешимость элементарной теории свободной нециклической полугруппы. В 1973г. автором10 была доказана неразрешимость позитивной 3V33- теории свободной полугруппы. Отот результат составляет содержание следующей теоремы и ее следствия.

Теорема 1.1. Можно построить такую формулу Ф(.г) с одной спо-бодпоп переменной г. имеющую /шд

15

(3I,')(V.7)(B.r1)(3,r2)(3.r.,)( V »' = 'V).

1 = 1

где и,-, г¡ - слова л алфавите

{.Г. !/\|/,.П. .Г2,.Г.Ч,Я1.Л2,«з},

ч то не существует алгоритма, позволяющего но произвольному эле-мепту а полугруппы П_> определить пепшп а ли и а полугруппе ll.j /¡юрмулн '¡'(у)-

Следствие. Почт пиная 3V3''-ТГО/)//Я 1юлуг1>уппы Из ЛJIlOI>llTMII-чегки нер;препшма.

В 1982г. ('.('.Марчепков" усилил резуль та т рабо ты автора"1 с точки зрения числа квапторпых блоков в приставках расматрива-емых форму.ч. доказав алгоритмическую неразрешимость позитивной УЗ^-теории свободной полугруппы. Однако общее число кванторов в формулах, рассматриваемых в работах 1(1 и 11, одно и тоже - один квантор V п четыре кван тора 3. Следующая теорема усиливает указанные результаты автора и Г.С'.Марчепкова как с точки зрения числа кванторных блоков, так и с точки зрения общего числа кванторов.

^thiiiio \V. Concatenation as a basis for arithmetic // J.Symbolic Logic. I9HÍ. V. 11 . V. 1(15 - 111.

,0Луригв В.Г. Ho ¡in шитая теория свободной полугруппы // ЛАП СССР. 1973. Т. ill, N I. С.772 - 771.

11 Марченкгт С.С. Неразрешимость позитивной УЗ^-теорнн спободноп полугруппы // Спб.матем.журп. 1982. 'Г.23. N I. СМ 90- 198.

Теорема 1.3. f/ри ж > '2 нозп тинная V З'-теорпя свободной полу группы Пт алгоритмически неразрешима.

Из фундаментального результата Г.С.Макапипа1" о существовании алгоритма, позволяющего по произвольному уравнению г свободной полугруппе определить, имеет ли оно решение, следует алгоритмическая разрешимость экзистенциальной и универсальной теорий свободной полугруппы, т.е. при любых in п п 3"-теорня н V-теория полуг1)уппи II,,, алгоритмически раз[>епшмы.

Формулы, рассматриваемые в работе С.С.Марченкова" и в теореме 1.3, имеют более прос тую кванторную приставку с точки зрения числа кпанторных блоков, чем формулы из теоремы 1.1, однако пх бескванторная часть содержит достаточно много вхождений знака дизъюнкции, которые, конечно, можно удалить, используя результат 11.К.Косовского13, однако, это приведет к значительному усложнению кванторпой приставки, в то время, как удаление знака дизъюнкции из формул, рассматриваемых в теореме 1.1, приводит к незначительному усложнению кванторпой приставки. Точнее имеет место следующая теорема.

Теорема 1.2. Можно построить т акую формулу Ф(.г) с одной свободной переменной .г, имеющую пил

(3ic) (Viy) (3.i'i)... (Е.г11) ((/ = ,-),

где и, г - слона и алфавите

{.г, i<\ i/, .г]------1'п , «! • «2. «з} .

что ие существует алгоритма, позволяющего но произвольному элементу a полугруппы 11_> определить истинна ли на полугруппе Ид формула Ф(</).

IJ §2 исследуются некоторые алгоритмические проблемы для дпофаптовых множеств в полугруппе llj. Заметим, что в силу уже упоминавшегося выше фундаментального результата Г.С.Ма-канпна1" проблема вхождения для любого днофаптова множества, а

Макании Г.С. Проблема разрешимости уравнений в свободной полугруппе И Матем. сб. 1977. Т.103(115), N 2(6). СМ17- 2Л(>.

'^Косовский U.K. Элементы математической ло1 ики и ее приложении к теории субрекурсивных алгоритмов. И1-В0. ЛГУ. Ленинград. 1981. 192 с.

значит п для его дополнения, алгоритмически разрешима. Поэтому предетаиляет интерес нахождение "достаточно простых" алгоритмически неразрешимых проблем для диофантовых множеств в свободной полугруппе. В §2 диссертации ус тановлена алгоритмическая неразрешимость проблемы определения но заданию диофантова множества Л/ является ли его дополнение пустым, в то же время проблема определения по заданию диофантова множества М является ли пустым само множество М алгоритмически разрешима; строится пример диофантова множества, дополнение которого не являе тся дпофаптовым (хотя п является рекурсивным).

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

М.И .Дехтярь1'1 доказал Л'Л-иолноту проблемы разрешимос ти в свободных полугруппах для уравнении, не содержащих переменных в правой части.

В tjli существенно усиливается ->тот результат, а именно доказывается .\'P-no:niu r;\ п/юбле.мы определения но урншкчшю /шла

»'(•''I......г„ ) = Ц-

где w ( ,Г|......гп ) - mono п алфнш/те неизвестных { .rj......г„ }, а ц -

элемент полугруппы имеет ли оно решение.

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

Ксли ;/ - слово в некотором алфавите, a b - буква что го алфавита, то через |f/|(, обозначается число вхождений буквы Ь в слово ц. т.е. длина проекции слона г/ на букву Ь.

Изучение уравнений в свободных полугруппах было начато Л.Л.Марковым в связи с попытками отрицательного решения 10-ой проблемы Д.Гильберта: проблема существования решения для произвольной системы уравнений в свободной полутруппе сводится к проблеме существования решения в натуральных числах для диофантова уравнения. Им же был построен алгоритм, позволяющий по

11 Лехтярь М.И. Сложность решения одного кллега уравнений м слонах // VII Всесоюзная конференция по ма'1 . ло! ике. Тезисы докладом. 11овоспопрск. 1!)8 1. С.58.

1 1

любому уравнению .с двумя неизвестными к свободной полугруппе определить имеет ли оно решение. Соответствующий алгоритм для уравнений с тремя неизвестными был построен Ю.И.Хмелевскнм15.

Как уже отмечалось выше, Г.С.Макании 12 построил алгоритм, позволяющий по произвольному уравнению в свободной полугруппе определить имеет ли оно решение. Ю.В.Матнясеннч16 показал, что н вопрос о существовании решения системы уравнений в словах и длинах в свободной полугруппе так же сводится к 10-ой проблеме Д.Гильберта, это сделало актуальным изучение в свободной полугруппе уравнений в словах и длинах, а так же систем уравнений в свободных полугруппах с различными другими аналогичными условиями на решения, например, неравенства между длинами, равенство проекций на образующие и т.д. Интересные результаты в этом направлении получены II.К.Косовским1',18,19.

Полагаем

А/(») = { {».Л I 1 <'<■><»} •

Основное содержание §'1 составляет :

Теорема 1.7. При т > 2 можно укачл /ъ такое число п. такое подмножество .1 ¡множества М(ч) н такое одиоиарамет/шческос семейство урапиепий

и(.г,. Г]......гп.аи(1',) = »(.»-,.г 1......г„,

с петнестш.шп .Г)......г„, константами ч\, а2 и ллр<шет/нш .г, что не

существует алгоритма, позволяющего для произвольного па гура;п,-иого числа к■ определит!,, имеет ли урапиеппе

1/( «1 , 1......г„.«1.я-->) = . .Г 1......г„,0 |,(12)

1г'Хме.тевскпи Ю.И. Уравнения в свободной полугруппе // Груды Матсм. пи-та. АН СССР. 1971. Т.107. 280 С.

10МатиясТ1П1Ч Ю.В. Свять систем уравнений n словах и длинах с 10-ой ироблсмлп Гильберта // Исследования но koik i руктнвной математике и математической логике.. Записки научных семинаров Ленннгр. отд. матем. нч-та. АН СССР. Л..1968. Т.8. С. 132- МЛ.

''КосопскиЙ U.K. Некоторые свойства решений уравнений в свободной полугруппе// Записки научи, семинаров Лешип р. отд. Матем. ни l a. All СССР. Л.,1972. Т..42. С.21 - 28.

18Косовскии U.K. О множествах, представнмых в виде решений уравнении в словах и длинах // Вторая всесоюзная конфер. по матем. логике. Тпнсы кратких сообщений. М.,1972. С.23.

19Косовскнй U.K. С) решении систем, состояншх одновременно m уравнений в словах н неравенств в длинах слов // Заипскн научи, семинаров Леиингр отд. Мат ем. ии-та. All C'C'CI'. Л..1973. Т.33. С.2 1- 29.

такое решение < Х\, ...,Л'П > в свободной полугруппе 1Т1П. что при {í,j}Gvl:

= 1 l^ila, = I-Y; |я, ■

Утверждение теоремы 1.7 будет верно, если равенство |g|a2 = |Л|Яа заменить равенством |jf| = |/i|. Эти результаты были получены автором в начале 70-х годов (опубликовании в 1974г. в20), в 1988 году появилась работа Д.Бюхи и С.Сенгера21, в которой доказывались аналогичные утверждения. По-видимому, им была не известна работа 20.

В пятом параграфе рассматриваются системы уравнений в словах, длинах и с эндоморфизмами в свободных полугруппах.

Свободная полугруппа Пг "бедна" автоморфизмами: кроме тождественного она обладает лишь одним автоморфизмом у>, переставляющим образующие, поэтому в §4 рассматриваются системы уравнении в словах, длинах и с одним фиксированным ннъектпвным эндоморфизмом. Основной результат §4 - это теорема 1.9.

Тсорома 1.9. Можно построить такой ииъективиый эндоморфизм ¡р полугруппы 112 п такую систему уравнений Ф(х, .г ¡, ...,.г„) вила

w = и fr &{ij)6fi|.r¡| = I.гJI fr vs(.ri) = .г2,

что lie существует алгоритма, позволяющего для произвольного натурального числа b определить имеет ли система

Ща\,.п,...,*„)

решение в II 2.

Инъективиый эндоморфизм <р можно заменить на автоморфизм ■ф, но при этом приходится равенство длин заменить на равенство проекций на а\. В результате получаем следующую теорему.

Тесфема 1.10. Можно построить такую систему уравнений

Ф(.т,.ть ...,.г„)

20Дурнев В.Г. ОО уравнениях на свободных полугруппах н группах // Ма-тем. заметки. 1974. Т. 16, N 5. С.717- 72-1.

21 Buclii J.R. and Senger S. Definability in the existential theory of concatenation and undecidablc extensions of this theory // Z. Mat. Log. und Gründl. Math. 1988. V.31, N -1. P. 337 - 342.

вида

и> - и к = = .с2,

что не существует алгоритма, позволяющего по произвольному па туральному числу к определить имеет ли снстел1а

Ф(й1 , ,гь ...,х„)

решение в Щ-

Из других результатов этого параграфа выделим алгоритмическую неразрешимость проблемы существования решений для урав нений с одним автоморфизмом п одним эндоморфизмом в свободно! полугруппе, причем эти эндоморфизмы входят лишь в левую част! уравнения, а также алгоритмическую неразрешимость проблемы существования для произвольной системы уравнений с неизвестным! .С1,...,.т„ в словах и длинах в свободной полугруппе Из такого решения < /ц, ..., кп >, что 1ц £ Я, где Н - достаточно просто опре деляемая подполугруппа полугруппы Из (проблема вхождения в И разрешима в линейное время).

В §6 рассматривается вопрос о выразимости некоторых предикатов на свободной полугруппе формулами с "простыми" кпаиторнымг приставками.

В начале параграфа приводится доказательство теоремы об элиминируемости последнего кванторного У-блока в позитивных формулах, относящихся к свободным полугруппам. Затем, несколькс усиливая результаты II.К.Косовского 13 о невыразимости предикате (,с| = |у| в 3-теорин полугруппы Пт, доказывается, что этот предикат |.к| = |(/| па свободной полугруппе ГЬ не выразим в ее З-теории даже с использованием предиката |.г|а = ||у|а, но выразим в позитивной З-теории с использованием двух предикатов |.т|а = ||/|а и |л:|4 = |т/]¿,, исследуется вопрос о выразимости каждого из трех предикатов

М = |у|, Ма = |у|а, |х\ь = |у|ь

через остальные. В основе доказательств лежит техника полузацепленных систем слов II.К.Косовского13.

Построены такие слова

и<(х,у,г,у,х1,х2,аиа2) и и(х, у, 2, у, хг, х2, «1, а2) в алфавите

{х,у,г,и,х1,х2,аиа2},

что для любых A,B,C,D из свободной полугруппы Пт ранга m (m > 2) со свободными образующими ai,...,am имеет место эквивалентность :

(А = В V С = D) <=>

Пт \= (3x1x2)w(A,B,C,D,x,ä) = u(A,B,C,D,x,â).

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

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

Еще в 1918 г. К.Нильсен"" рассмотрел в свободной группе уравнение xyx~ly~l — aba~lb~x и описал множество его решений. Изучению уравнений в свободных группах посвящено немало работ различных авторов.

Р.Лнндон23 описал множество решений уравнения с од-

ним неизвестным в свободной группе в терминах параметрических слов, а А.А.Лорешг4 значительно упростил это описание.

Ю.И.Хмелевскнй25 изучал системы уравнений специального

вида в свободной группе н получил ряд интересных результатов. Г.С.Маканнн26 построил алгоритм, позволяющий по произвольному уравнению в свободной группе определить имеет ли оно решение. А.А.Разборов27 дал описание множества решений произвольной совместной системы уравнений в свободной группе, а Р.И.Грнгорчук

22Nielson J. Die Isomorpliismen tier allgemeinen undeiidlichen Gruppe mit zwei Erzengenden // Math. Ann. 1918. P.385 - 397.

23 Lyndon R. Equations in free groups // Trans. Amer. Math. Soc. 1960. V.96. P. 145 - -157.

24 Jlopenn A.A. О представлении множеств решений систем уравнений с одним неизвестным в свободных группах // ДАН СССР. 1968. 'Г.178, N 2. С. 290 - 292.

25Хмелевскпй Ю.И. Системы уравнений в свободной группе. // Изв. АН СССР. Сер. матем. 1971. Т. 35, N 6. С. 1237 - 1268.

2е'Макатш Г.С. Уравнения в свободных группах // Изв. АН СССР.Сер.матем. 1982. Т. 16, N 6. С.1199- 127-1.

27Разборов A.A. О системах уравнений в свободной группе // Изв. АН СССР. Сер. матем. 1984. Т.48, N 4. С. 779- 832.

и Н.Ф.Курчанов28 в других терминах описали множество решений произвольного квадратичного уравнения в свободной группе.

В то же время ряд задач сводится к определению имеет ли некоторое уравнение в свободной группе решение с теми пли иными свойствами. Так вопрос о разрешимости позитивной теории свободной группы, решенный положительно Г.С.Маканиным29, был ранее сведен Ю.И.Мерзляковым30 к следующей проблеме:

построить алгоритм, позволяющий для произвольного уравнения

и>(.Т1, ... , .с,,, «1, ... , ят ) = 1 определить, имеет ли оно такое решение дь ... ,дп € Г,п, что

51 6 , 32 6 /'та, •■•></« £ Кг, , ГДе 11Ц < 1П2 < ■ ■ ■ < Ш, II

Гт, - свободная группа с образующими я ь ... , ат,.

В §1 гл.II устанавливается алгоритмическая неразрешимость вопроса о существовании у уравнения в свободной группе Рт такого решения, часть компонент (фиксированная) которого принадлежат

т-,( 5 )

в-ому коммутанту !',„ или Б-ому члену нижнего нейтрального ряда (Кг)! этой группы Гт. Эта тематика связана с исследованиями но проблеме 9.25 из "Коуровской тетради".

Основное содержание §1 гл.II составляет теорема 2.1.

Теорема 2.1. Для любой свободной группы Рт со свободными образующими а 1... . , а,„ (т > 2) можно построить такое уравнение

и'(х, ,сь.....сп, «ь я-2) = 1

с неизвестными х 1, ,г2.....;гп, константами я 1, я2 и параметром х,

что не существует алгоритма, позволяющего для произвольного натурального числа к определить, существует ли решение уравнения

и>(а\, х 1, . .. , х„, яь а2 ) = 1

28Грпгорчук Р.И., Курчанов II.Ф. Об оппсашш множества решений квадратичных уравнений в свободных группах // Тезисы докладов Международной алгебраической конференции. Новосибирск. 1989. С.30.

29Макании Г.С. Разрешимость универсальной и позитивной теорий свободной группы // Изв. АН СССР. Сер. матем. 1984, N -1. С.735 - 749.

30Мерзляков Ю.И. Позитивные формулы на свободных группах // Алгебра II логика. 196С. Т.5, N 4. С.25 - 42.

С условием

•l'l G [/•'„,. /'',»],.....>'f G [fm, /'ж],

где - коммутант группы /•'„,. a I - некоторое фиксированное

число между I и п.

Н следствиях in этой теоремы показывается, что при замене коммутанта F,i!' на s-ый коммутан т Fm ' пли на s-ын член (F,,,)., нижнего центрального ряда группы /''„, (я > 2) также получается алгоритмически неразрешимая задача.

'Георему 2.1 интересно сравнить со следующей теоремой 2.2, в которой доказывается, ч то аналогичная задача для уравнений с одним неизвестным является алгоритмически разрешимой.

(1)

Пусть Г! s-fi коммутант /•„, свободной группы /*'„, или .ч-й член (F,„)., ее нижнего центрального ряда.

Теорема 2.2. Сущсстпуст алгоритм, позволяющий по любому уравнению с одним ненчвестным

!/' ( .Г,, II, , . . , (1,„ ) = 1 (*)

в группе /•',„ определить имеет ли оно решение ц, in П.

И i¡2 гл.11 устанавливается алгоритмическая неразрешимое ti. проблемы существования решении для уравнений с автоморфизмом и эндоморфизмом в свободной группе. ')та тематика связана с вопросом 10.20 из "Коуровской тетради", кроме того, в целом ряде работ'51исследовался вопрос об алгоритмической природе элементарных теории некоторых классов групп в сигнатурах, содержащих обозначения для эндоморфизмов и автоморфизмов.

Основное содержание этого параграфа заключено в теоремах 2.Ü и 2.5.

Теорема 2.3. Можно указать такие автоморфизм (/', чндолю/и/шгм свободной груши,i =-С (i,h и семейс тво уравнений

И'(.г..1-1, ..,.(■„, 0(.r„),v-(.i-i).....¡f(.vt),a,l>) = 1

"Кокорпн Л.И., Мари.янон В.И. Унпперсальные расширенные теории // Алгебра. Вып.2. Иркутск. 197.3. (М07 - 113.

í2Мартьянов В.И. О iеорпи абелевых групп с предикатом, выделяющим под! руины и операциями шломорфтмов // Алгебра и логика. 1975. Г. I I, N Г>. с.536 - 512.

с неизвестными .г 1......с„. константами а.Ь н па]>аметром .г, что не

существует алгоритма, позволяющего для произвольного ппчу/шль-пого числа к определить, имеет ли у/>авпение

«'(«*',.»•!......г,,,е(.г„), ^(-П ), ...,г-{.г,),а. Ь) = 1

решение в группе / V

Интересно отметить, что автоморфизм с применяется лишь к одной переменной. Переходя от группы Р-> к труппе /-"з, можно до-бнться, чтобы и эндоморфизм у применялся лишь к одной переменной (следствия 2 и теоремы 2А).

Далее определяется подгруппа Рш свободной группы Рш. двойственная коммутант}' этой группы. А именно, обозначим через 1>, (/=1....."() эндоморфизм свободной труппы Рш, заданный равенствами

</',(«,) = I'ч(«]) = 1 при ] ф /, (*)

тогда

пг = п /=1

Если теперь следующими равенствами (**), двойственными равенствам (*),

у",(а,) = 1, ^¡((1]) = 11] прп./'^/ (**)

определим эндоморфизмы у?,- (/=1.....>н) и положим

ш

1',п = Р| Кч'г■/.

то подгруппу Р,п можно рассматривать как двойственную коммутанту /•',',". Но аналогии с группами кос элементы подгруппы Рш назовем гладкими члемеитамн свободной группы.

Заметим, что Р> = рУ\ Поэтом}- представляет ин терес следующая теорема 2.5.

Теорема 2.5. При ш > Я не существует алгоритма, позволяющего по произвольному уравнению в группе /'',„

»'(.Г!......Г„,(1Ь ...,«,„) = 1

определить имеет ли оно такое решение Ц\.....дп, что tj\ Е Рт.

Теорема '2.5 представляет интерес eme и потому, что проблема вхождения в подгруппу Рш линейно сводится к проблеме тождества для группы Fm-1, а поэтому относится к числу "легко" решаемых проблем для свободной группы F,„.

H теореме 2.6 доказывается, что подгруппу Рт в теореме 2.5 можно заменить на любой коммутант F,'?1 при s > 2.

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

В (¡4 гл.11 доказана алгоритмическая неразрешимость позитивной 3'' V Зч-теории свободной неабелевой труппы в сигнатуре, расширенной предикатом равенства длин. Этот результат является усилением основного результата работы3"' об алгоритмической неразрешимости элементарной теории свободной группы п расширенной сигна туре, содержащей предикат равенства длин.

В целом ряде работ изучались элементарные теории классов алгебраических систем с дополнительным предикатом, основную информацию по этому вопросу можно получить, например, из обзора34 н работ31.32.35,3*."

В Ü5 гл.11 устанавливается алгоритмическая неразрешимость ряда достаточно простых, с точки зрения кнанторных приставок, ограниченных теорий с дополни тельным предика том.

Отметим неко торые теоремы из этого параграфа.

Т<!ор<;ма 2.10. Можно указать такое число />, что VJ З^-тсо/шя класса всех свободных нециклических груш/ с дополнительным Н]>е-дикатом, а так же \/23t' -теория любой нециклической свободной группы с дополнительным и/>сликатом алгоритмически неразрешима.

" НпЬст-Oyson V The l'wtei'¡(hihility of Kipp Cirmips wilh a I.englli Function // l'iiivcisity of Cal^ai y, Matlicmatics Uesearcli Paper. 197-1. N 221. P. 1 - 2(i.

^Koh'opiui Л.М., Ilmiyc А.Г. Вопросы разрешимости расширенных теорий // Успехи матем. наук. 1978. Т.33, N 2. С. 19 - 8 1.

^''Козлов Г.Т., Кокорпп А.И. 'Элементарные теории абеленых групп без кручения с предикатом, выделяющим подгруппу // Алгебра п логика. 1969. Г.8, N 3. С.320 - 33 1.

"'Луковпиков II.F., Мартьянов В.И. Универсальные j.'icMemiio-

иодгрупповые теории абелевых групп // V Всесоюзная конференция по матем. лотке. Кпшенев. 1976.

Теорема 2.10 усиливает известный результат 1\1.А.Тайплнпа'!' о неразрешимости элементарной тео]>пн свободной группы с дополнительным предикатом.

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

Теорема 2.14. Существует такое натуральное число п. что любой класс абеленых r¡>yun. содержащий свободную а белену группу ранга 2. имеет неразрешимую V23" Л-элементно-нолгрупновую теорию.

Теорема 2.M дает уточненный отвез- на вторую часы, вопроса из35 "Разрешима ли универсальная по подмоделям элементно-подгруиповая теория абеленых групп (без кручения)?", на первую часть этого вопроса ответ получен ранее в работах'8,',!\'10, однако теорема 2.14 уточняет этот ответ.

Обозначим через А,„ свободную абелеву группу ранга m со свободными образующими <ii.....«„,, а через <х„, - сигнатуру

< *, 1. «i.....ч,„. К >,

где К - двуместный предикатный символ, интерпретируемый па группе А,„ следующим образом: для ij.lt 6 А,,,

А,„ (= K(y.h) <==> "г/ — степень h ".

Хо|юшо известно, что элементарная теория труппы Ai в сигнатуре <Т) алгоритмически неразрешима в то время, как 3-теорпя группы А] разрешима'11,'1-.

я'Тапц.'ии1 М.Л. 1'лцо несколько примером неразрешимых теорий // Алгебра и логика. 1967. Т.Н. N 3. С. 10) -111.

18 Слободской A.M.. Фридман О.И. С) теориях абеленых групп с предикатом, выделяющим подгруппы // Алгебра и логика- 1975. I .14, N 5. С. 572 - 575.

^Baudisch A. A note on the elementary theory of torsion flee Ahelian ginup^ with one predicate for subgroups // Wiss. Humboldt. Univ. Berlin. Math.-natur wis. R. 1977. Y.2G. N 5. P. (ill - 1Л2.

40Baur \Y. Decidability and undecidability of theories of Ahelian gioups with predicates for subgioiips // Compos. Math. 1975. V.31. N 1. I'. 23 - 30.

41 Бельгюкон А.П. Ратрешимость уиинерсалыюй теории натуральных 'ill-се.т со сложением и делимостью // Чаппски паучп. семинаром Ленппгр. отд Матем. нп-та. АН C'C'C'I'. Л..1976. T.tiO. N 7. С, 15- 28.

42l/ipshitz L. The Diophantine problem for addition and divisibility // Trans Amcr. Math. Soc. 1978. Y.235. P.271 - 283.

И конце §5 доказывается алгоритмическая неразрешимость позитивной 3-теорин группы Л2 в сигнатуре его и как следствие получается доказательство неразрешимости одной достаточно просто формулируемой задачи для систем линейных диофаитовых уравнений (теорема 2.13).

В §6 гл.II рассматриваются в свободной группе Fm уравнения

вида

"'(.Г1......е„) = д, (*)

где it(.vi,.....г„) - групповое слово от неизвестных .([......i„, а у -

элемент группы Fm.

Уравнения вида (*) мы называем уравнениями с олннм коэффициентом. Они рассматривались в целом ряде работ"'0."1'1,'11,45. Основное содержание §6 заключено в теоремах 2.16 и 2.17.

Теорема 2.1G. Проблема разрешимости уравнении в свободной группе /•',„ (in > 2) линейно сводится к проблеме разрешимости уравнений с омним коэффициентом в группе f\. где к= 2[( ш-f 1)/2], а проблема разрешимости систем уравнений в группе /■',„ полиномиально сводима к проблеме разрешимости уравнений с одним коэффициентом в группе Fk.

'Георема 2.16 оказалась несколько неожиданной, так как традиционно счи талось, что изучение уравнений вида (*) является, в некотором смысле, более простой задачей, чем изучение произвольного уравнения.

В заключительной части (¡(> рассматривается вопрос о сложности ус тановления имеет ли уравнение вида (*) решение и доказывается теорема 2.17.

Теорема 2.17. Проблема рн з]>ешимос ги уравнений с одним коэффициентом в свободной группе F-> является \Р-трудной задачей.

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

*1!®<'iiirii П.II. Об уравнениях и нплыютептнмх группах // X Всесоюзный симпозиум по теории групп. Тезисы докладом. N1., 198-1.

Романвков В.Л. О неразрешимости проблемы зндоморфной сводимости в свободных ннлыютептных группах И в свободных кольцах // Алгебра п логика. 1977. Т. 1 (>, N I. С. 157 - -171.

4'У<1шрр Р.1С. On 11 ю substitution problem for fiee groups // Proc. Anier. Math. Soc. 1909. V.23. N 2. P.121 - 123.

15 третьей главе рассматриваются вопросы, связанные с совпадением и несовпадением "простых" ограниченных элементарных теорий групп некоторых бесконечных серий, прежде всего, целочисленных линейных групп GL(n.Z). SL(n.Z). PGI.(n.Z). PSI.(n.Z). групп кос fí{n). симметрических групп S(n) п трупп, свободных в некоторых многообразиях. Устанавливается алгори тмическая неразрешимость ряда ограниченных элементарных теорий.

В §1 гл.III получены усиления результатов Л.И.Мальцсваг': при it > ш элементарные теории групп Gl.(n.Z) п Gl.(ni.Z). PG L(n. Z) и PGL(m/Z). SI.(ii,Z) n Sl.(m.Z). PSL(n.Z) и PSL(m.Z) различны, а именно, доказано, что

при п > и i группы GL(n.Z) n GI.(in,Z). PGL(n.Z) и PGL(in. Z). SL(ii.Z) и SL(in. Z), PSI-(n. Z) и PSL(»>. Z) имеют различные У2-теории, более того,

если п-четиое число, либо п-иечетное число, но при >том п > in + 1. toV1 -теории указанных групп различны;

при нечетном п V1 -теории групп SI.(n. Z), SL(n — 1. Z), а также групп GL(n.Z) п GL(» — 1. Z) сонпалают.

В §2 гл.111 показано, ч то при п > 6 поштнииые V'-теории симметрических групп S(n) и S(ii — 1) различны.

В заключительной части параграфа доказывается, что n¡)ii п > 5 V2-теории групп кос И{п) и U(n — 1) различны н то время. как их У1-теории совпадают.

Тематика §3 гл.111 связана с известной проблемой А.Тарского об элементарной эквивалентности свободных групп конечных рангов, аналогичная проблема для групп, свободных в некоторых многообразиях. была исследована автором еще в работе'10, позже в работах'1' п'18 она получила название проблема А.Тарского для групп, свободных п многообразиях.

В §3 гл.111 исследуе тся проблема А.Тарского для групп, свободных в многообразиях, в некотором смысле, "близких" к многробра-зню разрешимых групп, прежде всего в многообразиях, задаваемых

■^'Дурнев В.Г. С) позитивных формулах на группах // Уч. чаи. матом,

кафедр Тульского гос. пел. им га. Геометрия II атгеОра. 1970, N 2. С.215- 2 11.

4 ' Lawicnce J. Tarski's рюЫсш foi variot ies of groups wit h commutator ¡(lent it у

// J. Symbolic Logic. 198(1. V. 51. N 1. 1'. 75 - 78.

"Rogers P., Smith II. and Solitar D. Tarski's problem for solvable groups //

I'ioc. Amer. Math. Soc. 198(1. Y.H(1, N 1. I1. (108 - (171.

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

Основные результаты §3 были получены автором в конце 60-х годов и онубликованны в работе46. 13 появившихся значительно позже работах 47 и48 доказывались аналогичные результаты.

В §<1 гл.111 рассматривается уравнение Л.И.Мальцева ф.у]::-1 = М]

в свободной метабелевон группе /'2(62) ранга 2 со свободными образующими я, Ь и доказывается, что для Р\(&2) имеет место эквивалентность, аналогичная известной эквивалентности Л.И.Мальцева для свободной группы F-2:

для элементов g,h группы /'2(62) разрешимо относительно : одно пзуравнений

= [ff,/«]=-' = МГ (е € {-1, + 1})

тогда и только тогда, когда r/Ji - свободные образующие группы

/•Ы62).

Ото позволило в §5 гл.III установить алгоритмическую перазре-шпмость позитивной 3-теорпп с одной константой любой свободной разрешимой пеабелевой группы. Отметим, что вопрос об алгоритмической разрешимости В-теории (без констант) свободной разрешимой группы представляет собой хорошо известную открытую проблему.

В §6 гл.111 устанавливается алгоритмическая неразрешимость позитивной V2 Зр-теории любого многообразия иплыютептпых групп ступени < с (с > 2), а так же любой свободной в этом многообразии нециклической группы, исследуется вопрос о возможности дальнейшего усиления этого результата.

В §7 гл.III доказывае тся, что при некотором фиксированном ?п и при любом п > 3 элемен тарная \/2Зг"-теорпя (без констант) группы C!L(n, Z), также как н труппы SL(n, Z), алгоритмически неразрешима. О то усиливает известный результат Л.И.Мальцева 5 о неразрешимости элементарных теорий указанных групп.

2.3

В §8 гл.111 устанавливается алгоритмическая неразрешимость некоторых ограниченных теории коммутативных полугрупп.

Коммутативные полугруппы являются более сложным объектом, чем коммутативные группы, так, например, Л.Тарский49 доказал, что элементарная теория класса всех коммутативных полугрупп алгоритмически неразрешима, а М.А.Тапцлнн50 получил аналогичный результат для класса всех коммутативных полугрупп с сокращением. Для класса всех коммутативных полугрупп М.Л.Тайнлпн51 доказал эффективную неотделимость множества тождественно истинных и конечно опровержимых формул, в то время, как Ю.Л.Ершов52 доказал алгоритмическую разрешимость элементарной теории класса всех конечных коммутативных полугрупп с сокращением.

В §8 гл.III доказано, что позитивная теория класса всех коммутативных полугрупп алгоритмически разрешима.

М.Л.Тайнлпн в работе53 для конечно определенных коммутативных полугрупп ¿(01,03) с конечным множеством образующих элементов 21 и конечным множеством определяющих соотношений ® рассмотрел следующую проблему, названную им ''проблемой А ':

" Существует ли алгоритм, позволяющий по произвольным 21 п Ш п по произвольной замкнутой формуле Ф исчисления предикатов с равенством сигнатуры

<т( 21) =< *. {и, С„ |а е Я} >,

где для каждого а из 21 Са - одноместный предикатный символ, определить, истинна ли формула Ф на коммутативной полугруппе ¿(21, "В) при условии, что для каждого а б' 21 предикат С„(.с) интерпретируется в L{21,23) следующим образом:

" .г равен некоторой степени а".

49Tarski Л., Mostowski Л., Ilobinson Н.М. Undecidable theories. N11, 1953. X +98 p.

ьоТапил1ш М.А. Неразрешимость элементарной теории коммутативных полугрупп с сокращением // Снб. матем. жури. 1902. N 3. С. 308 - 309.

51Танцлин М.А. Эффективная неотделимость множества тождественно истинных II конечно опровержимых формул элементарной теории структур // Алгебра II логика. 1962. T.l, N 3. С. 24 - 38.

52Ершов Ю.Л. Новые примеры неразрешимых теорий // Алгебра н логика. I960. Т. 5, N 5. С. 37 - 48.

53Тайцлнн М.А. Об алгоритмической проблеме для коммутативных полугрупп // ДАН СССР. Сер. мат. - фнз. 1968. Т.178, N 4. С. 786- 789.

В этой же работе М.Л.Тайцлии построил алгоритм, разрешающий "проблему А '.

В §8 гл.Ill доказано, что некоторое естественное обобщение "проблемы А" приводит к неразрешимой алгоритмической проблеме даже для свободной абелевой полугруппы Лг ранга 2, а именно, установлена

алгоритмическая неразрешимость позитивной Э-теорпн полугруппы Л2 в сигнатуре < *, aj, «2, А' >, где К - двуместный предикатный символ, интерпретируемый в Л-> следующим образом: для 7, h G А2

Аг |= K(g,/i) <£=>- "д — степень Л".

Выражаю глубокую благодарность чл.-корр.РАП С.И.Адяну за внимание к работе и поддержку на протяжении многих лет, за постоянное обсуждение результатов и многочисленные полезные советы по поводу нх изложения.

ГАВОТЫ АВТОРА ПО ТЕМЕ ДИССЕРТАЦИИ

[1] Дурней В.Г. О позитивных формулах на группах // Уч. зап. матем. кафедр Тульского гос. иед. пн-та. Геометрия и алгебра. 1970, N 2. С.215 - 241.

[2] Дурнев В.Г. О позитивной теории свободной полугруппы// Вопросы теории групп и полугрупп. Тула. 1972. С. 122 - 172.

[3] Дурнев В.Г. Позитивная теория свободной полугруппы // ДАН СССР. 1973. Т. 211, N 4. С.772 - 774.

[4] Дурнев В.Г. О позитивных формулах на свободных полугруппах // Спб. матем. жури. 1974 Т.25, N 5. С. 1131 - 1137.

[5] Дурнев В.Г. Об уравнениях на свободных полугруппах и группах // Матем. заметки. 1974. Т.16, N 5. С.717 - 724.

[6] Дурнев В.Г. О системах уравнении на свободных нильпо-теитных группах // Вопросы теории групп и гомологической алгебры. Ярославль, 1984. С.66 - 69.

[7] Дурнев В.Г. О формулах с функцией длины на свободной группе // Десятая Всесоюзная конференция по матем. логике. Тезисы докладов. Ленинград. 1988. С.56.

[8] Дурнев В.Г. Об уравнении Мальцева - Нильсена на свободной метабелевой группе ранга 2 // Матем. заметки. 1989. Т. 46, N 6. С. 57 - 60.

[9] Дурнев В.Г. О проблеме Тарского для свободных групп некоторых многообразий // Вопросы теории групп п гомологической алгебры. Ярославль, 1990. С. 25 - 35.

[10] Дурнев В.Г. Об одном обобщении задачи 9.25 из "Коуров-ской тетради" // Матем. заметки. 1990. Т.47, N 2. С. 15- 19.

[11] Дурнев В.Г. Об уравнениях с эндоморфизмами в свободных полугруппах // Дискретная математика. 1992. Т.4, N 2. С. 136 -141.

[12] Дурнев В.Г. Об уравнениях в словах и длинах с эндоморфизмами // Изв. ВУЗ'ов. Математика. 1992. N 8. С.ЗО - 34.

[13] Дурнев В.Г. Об уравнениях с ограничениями на решения в свободных группах // Матем. заметки. 1993. Т.53, N 1. С. 36 - 40.

[14] Дурнев В.Г. Об уравнениях с нодгрупиовыми ограничениями на решения в свободных группах // Дискретная математика 1995. Т.7, N 4. С.60 - 67.

[15] Дурнев В.Г. Неразрешимость позитивной \/3'5-теорпн свободной полугруппы // Спб. матем. журн. 1,995. Т.36, N 5. С.1067 -1080.

[16] Дурнев В.Г. Об элементарных теориях целочисленных линейных групп // Известия Российской академии наук. Серия математическая. 1995. Т.59, N 5. С.41 - 58.

[17] Дурнев В.Г. К проблеме разрешимости уравнений с одним коэффициентом // Матем. заметки. 1996. Т.59, N 6. С.832 - 846.

[18] Durnev V. Studying Algorithmic Problems for Free Semigroups and Groups // Lecture Notes in Computer Science. 1997. V.1234. P.88 - 101.