Введение к работе
Актуальность темы. Первым примером неразрешимой алгоритмической проблемы, возникшей вне математической логики, послужила проблема равенства слов для полугрупп (ассоциативных систем), сформулированная Л.Туэ в 1914г. задолго до появления самой теории алгоритмов. Алгоритмическая неразрешимость проблемы равенства слов для полугрупп была установлена в 1947г. независимо А.А.Марковым1 и Э.Постом.2 В 1952г. П.С.Новиковым3 была доказана алгоритмическая неразрешимость проблемы равенства слов для конечно-определенных групп.
Позже была доказана неразрешимость многих алгоритмические проблем как в алгебре, так и в топологии, теории чисел, анализе, теории дифференциальных уравнений и т.д. Это привело к убеждению, что неразрешимые алгоритмические проблемы широко распространены в самых различных разделах математики.
При этом следует отметить следующее обстоятельство: до середины 50-х годов основное внимание уделялось установлению самого факта существования неразрешимых алгоритмических проблем без учета простоты их формулировок, а примерно с конца 50-х годов все большее внимание стало уделяться построению "простых" примеров неразрешимых алгоритмических проблем.
Вопрос об установлении границы между разрешимыми и неразрешимыми алгоритмическими проблемами был явно сформулирован С.И.Адяном в 60-тыс годы.
Основное содержание диссертации и прежде всего двух ее первых глав вписывается в указанную программу С.И.Адяна.
А.И.Мальцев в докладе4 на Международном математиче-
ском конгрессе, состоявшемся в 1966т. в Москве, сформулировал проблему исследования алгоритмической природы различных ограниченных теорий, определяемых прежде всего типом кваиториых
Маркой Л.Л. Невозможность некоторых алгорифмов и теории ассоциативных систем // ДЛИ СССР. 1917. Т.55. С.587 - 590.
Post E.L. Kccuisivc unsolvability of a problem of Time // Л. Symbolic Logic. 1947. V. 12, N 1. P. 1 - 11.
Новиков П.С. OG алгоритмической неразрешимости проблемы тождества теории групп // ДАН СССР. 1952. Т.85. С. 709 - 712.
Мальцев Л.И. О некоторых пограничных вопросах алгебры и математической логики // Межлунар. конгр. математиков. Москва, 19GG. М., "Мир", 1968. С.217- 231.
приставок рассматриваемых формул, а также проблему исследования возможности различения алгебраических систем формулами с "простыми" кванторнымн приставками. Исследованию алгоритмической природы ограниченных элементарных теорий посвящены работы большого числа авторов.
Результаты первой и третьей глав диссертации вписываются в указанную программу А.И.Мальцева.
Цель работы и научная новизна. 13 диссертации исследуются простые фрагменты элементарной теории свободной полугруппы с целью установления их алгоритмической неразрешимости. Рассмотрены некоторые алгоритмические проблемы для уравнении в свободных полугруппах и группах, связанные с вопросами о существовании решений с теми пли иными свойствами, доказана их алгоритмическая неразрешимость. Исследовано несколько алгоритмических проблем для дпофантовых множеств в свободных полугруппах с целью установления их алгоритмической разрешимости или неразрешимости. Установлена Л^'Р-полнота проблемы разрешимости уравнении в свободной полугруппе, не содержащих переменных в правой части, а констант - в левой. Исследованы простые фрагменты элементарных теорий относительно свободных групп разрешимых многообразий групп, а так же целочисленных линейных групп: общих, специальных п проективных.
Все основные результаты диссертации являются новыми. К основным результатам диссертации можно отнести следующие:
1. Доказана алгоритмическая неразрешимость позитивной V33-теорпп свободной нециклической полугруппы, а также следующих двух фрагментов элементарной теории свободной полугруппы Из со свободными образующими «i, сіг, аз:
а) множества формул вида
(Зш)(У1/)(3.г1)(3.г2)(3.гз)(\/ «і = ''О.
1 = 1
где Ui,Vi - слова в алфавите {и1, у, :rj, :г2,.гз,«і,а2.яз},
б) множества формул вида
(3ic)(Vy)(3.74)...(3.1^) (и = ,>),
vie к. v - слона в алфавите {w, у, xi,..., ,сц, «і, я2, яз}.
2. Доказана неразрешимость ряда алгоритмических проблем 1ля уравнений в свободных полугруппах и группах, в частности, [оказаны следующие утверждения:
2.1. при любом т > 2 можно указать такое число ?і, такое
множество Л С { {i,j} | 1 < і: < j < п } и такое однопарамет])ическое
;емейство уравнений
u'(.r,.rb ...,.г„,яі,я2) = и(.г,.гь ...,.гп,пья2)
неизвестными .('і, г„, константами «і, «2 ' параметром .г, что не
:уществует алгоритма, позволяющего для произвольного натурального числа к определить, имеет ли уравнение
ш(а}",.гі, г„,яі,я2) = it(a\,xl,...,xn,aua2)
такое решение < Л"і Л'„ > в свободной полугруппе II,,,, что при
{'>./} Є /1 соппадают проекции слов Лг,- и Xj па каждую пз образующих «і и п2;
2.2. для любой свободной группы F„, со свободными образую
щими flj,... , яП1 (т > 2) можно построит!» такое уравнение
!/>(.Г, Л-1, ... , ,Т„, ЯЬ Я2) = 1
с неизвестными .гі,.г2, сп, константами яі, Я2 и параметром
х, что не существует алгоритма, позволяющего для произвольного натурального числа к определить, существует ли такое решение Зі, . 9п уравнения
w(a\. Ті, ... , .г„, аь я2) = 1,
9\ Є F\...,gt Є F\
где F„, - коммутант группы F,n, a I - некоторое фиксированное число между 1 и п;
2.3. при любом т > 3 не существует алгоритма, позволяющего
по произвольному уравнению в группе Fm
u,'(.ri, ...,я;п,я1,...,ят) = 1
определить имеет ли оно такое решение д\ д„, что gi Є /'„,, гд
Рт - двойственная коммутанту подгруппа группы Fm.
В то же время доказано, что существует алгоритм, позволяю шип но любому уравнению с одним неизвестным
w(.r,i, 01, ... , <1„, ) = 1
в группе F,n определить имеет ли оно такое решение д\, что Є VI где И - либо s—и коммутант F,„ группы Fm, либо s-ft член (Fm) ее нижнего центрального ряда, либо подгруппа /-",„.
3. Доказано, что проблема разрешимости уравнений в свободно!
группе Fm линейно сводится к проблеме разрешимости урапиенпі
с одним коэффициентом в группе F„,+ i, а проблема разрешнмогп
систем уравнений в группе Fm полиномиально сводима к проблемі
разрешимости уравнений с одним коэффициентом в группе Fm+i
Установлена XV- трудность проблемы разрешимости для уравпе
ний с одним коэффициентом в свободной нециклической группе.
-
Для относительно свободных групп конечных рангов разре шимых многообразии груші доказана их различимоеть позитивным! формулами с приставками тина V'"3V" при подходящих ?н и п, тел самым для них решена проблема Л.Тарского.
-
У*-тсорня г[)уппы G - это множество всех истинных на груп пс G замкнутых формул, предваренная нормальная форма которы: содержит лишь один кванторный блок, причем он состоит из k квап торов V.
Доказано, что при п > т группы GL{n,Z) и GL{m,Z) PGL(n,Z) и PGL(m,Z), SL(n,Z)"u SL(m,Z), PSL(n,Z) і PSL(m, Z) имеют различные \/2-теории,' более того, если п-четио<
ЧИСЛО, ЛНбо Н-НСЧСТ1ЮС ЧИСЛО, НО При ЭТОМ Н > »Н + 1, ТО Vі -ТСО])Ш
указанных групп различны.
При нечетном п Vі -теории груші SL(n, Z),SL(n — 1, Z), а такж< групп GL(n,Z) и GL(n — l,Z) совпадают.
Это усиливает результаты Л.И.Мальцева5 о несовпадении нрі п > m элементарных теорий групп GL(n,Z) и GL(m,Z), PGL(n,Z и PGL{m,Z), SL{n,Z) и SL{m,Z), PSL(n,Z) и PSL{m,Z).
6. Доказано, что для свободной метабелепой группы ^(2) ран га 2 со свободными образующими а,Ь имеет место эквивалентность
J Мальцев Л.И. Об элементарных свойствах линейных групп // Пекоторьи проблемы математики и механики. Ноиогнбпргк, 1961. С.110 - 132.
аналогичная іпнгстпон эквивалент: пости А.И.Малі>цсвл для свободной группы l\:
для элгментон і/,/і группы A(6v) разрешимо относительно z одно из уравнении
ф.ф"1 = [Я.Ь]< (с є {-1, + 1})
тогда " только тогда, когда (/,/( - оюбодные образующие групиы F2 (:>).
Ото позволило доказать алгоритмическую неразрешимость позитивной 3-теории с одной константой любой свободной неабелевой разрешимой группы.
Общие методы исследования. Проводимые в диссертации исследования базируются на следующих (фундаментальных результатах математической логики и теории алгоритмов: теореме о существовании конечно определенных полугрупп с неразрешимыми проблемами равенства слов, доказанной независимо Л.А.Марковым1 и ').Постом"\ геореме Ю.В Матпясевича6 о существовании полугруппы с ІЇ определяющими соотношениями, имеющей алгоритмически неразрешимую проблему равенства (фиксированному слову, теореме М.Минского' о неразрешимости проблемы применимости для операторных алгоритмов, теореме Ю.Н.Матпясевпча8 о днофантоностп рекурсивно нерсчислимых множеств.
И диссертации используются общие методы математической логики и теории алгоритмов: для установлення алгоритмической неразрешимости проблем к ним сводятся известные алгоритмически неразрешимые проблемы. Для установления Л'Л-трудпостп проблемы к ней полиномиально сводится известная Л'Л-трудпая проблема.
Практическая и теоретическая ценность. Работа носит теоретический характер. Ее результаты могут быть использованы 111>п исследовании алгоритмических проблем для групп и полугрупп, при изучении фрагментов элементарных теорий групп и полугрупп.
"Млтмясевпч IO.B. Простые примгрм неразрешимых ассоциативных исчислений // ЛАМ СССР. ИЖ7. Т.17.3, КС. С.12(11 - 12t;t>.
1 Mitisky ML. Recursive inisolvahility of Post's problem of "ТЛ(Ї" ami topics in theory of Turing machines // Ann. Math. Н)Г>1. Y.71. P. 1.37 - 1!ї.г>.
Матняссвпч К).В. Диофантоносї і, перечпелпмых множеств // ЛАП СССР. |!)7(). Г. 1.30. N3. С..|!1Г> - 198.
Апробация работы. Результаты диссертации докладыналпп на семинарах кафедры математической логики и теории алгоритмом механико-математического факультета МГУ: семинаре по математической логике под руководством чл.-корр. РАН. профессор; С.И.Адяна и профессора И.А.Успенского, семинаре по алгоритмическим проблемам алгебры под руководством чл.-корр. РАН, профессора С.И.Адяна, на семинаре лаборатории математической логикг ПОМ И им. В. Л. Стек лова РАН под руководством чл.-корр. РАН, профессора Ю.В.Матнясевнча, па алгебраических семинарах и ТГІІИ. ЯрГУ и МГИИ, па IV Всесоюзном симпозиуме по теории групп (Новосибирск,1974), на III Всесоюзной конференции по математической логике (Новосибирск,1974), на IV Всесоюзной конференции по математической логике (Кишинев, 1976), па VIII Всесоюзной конференции по математической логике (Москва, 1970), на XIX Всесоюзной алгебраической конференции (Львов,1987), на X Всесоюзной конференции по математической логике (Ленинград, 1988), на XI Всеосюз-пом симпозиуме по теории групп (Свердловск,1989), на Международных конференциях по алгебре (Новосибирск,1989 и Барнаул,1991), на Международном симпозиуме "Логические основы информатики" (Ярославль, 1997).
Публикации. Основные результаты автора но теме диссертации опубликованы в 18 работах, указанных в конце автореферата.
Структура и объем диссертации. Диссертация состоит из введения, трех глав, списка литературы (182 наименования) п занимает 202 страницы машинописного текста.