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

Первые алгоритмические проблемы для групп и полугрупп были поставлены еще в начале XX века: проблема равенства для групп М. Деном в 1911 г., [129], проблема равенства для полугрупп А. Туэ в 1914 г., [162]. В 30−50-х годах XX века были разработаны и исследованы различные математические версии понятия алгоритма (см. библиографию в [5], [71], [74], [107]). В результате этого в математике оформилось новое направление — исследование алгоритмических проблем, то есть вопросов существования алгоритмов для решения массовых задач из того или иного класса. Среди таких проблем стали различать разрешимые (соответствующий алгоритм существует) и неразрешимые (такого алгоритма нет) алгоритмические проблемы.

Первый пример неразрешимой алгоритмической проблемы в алгебре был найден А. Тарским: в 1943 году он построил многообразие универсальных алгебр с неразрешимой эквациональной теорией (см. [128], [159], [161]). В 1947 году А. А. Марков и, независимо, Э. Пост доказали неразрешимость проблемы равенства в многообразии всех полугрупп [67], [68], [153]. Дальнейшее развитие исследований по проблеме равенства и другим тесно связанным с ней алгоритмическим вопросам отражено в обзорах [4], [16], [79], [87], [135], [138], [155].

В работах [69], [70] А. А. Марков предложил весьма общий подход к изучению алгоритмических проблем на языке распознаваемости свойств, впоследствии получивших название марковских. Абстрактное свойство алгебраических систем из класса К называется марковским, если существуют две конечно определенные в К системы, одна из которых обладает этим свойством, а другая не вложима изоморфно ни в какую конечно определенную в К систему с этим свойством [18]. Рассматриваемую здесь алгоритмическую проблему, будем называть проблемой распознавания марковских свойств:

Существует ли алгоритм, который по конечному заданию алгебраической системы из класса К отвечает на вопрос, обладает ли она некоторым наперед заданным марковским свойством ?

Важные алгоритмические проблемы, связаны с рассмотрением тождеств. Фундаментальное исследование таких проблем для универсальных алгебр проведено в работах Г. Мак Нал-ти [143], [144]. Тождествам полугрупп, групп и колец посвящены книги и обзоры [3], [9], [10], [12], [44], [59], [114]. Тождества решеток подмногообразий и подалгебр рассматривались в [33], [51], [83], [112], [113], [156]. Среди проблем, связанных с тождествами, мы выделим как наиболее важные проблемы распознавания эквациональной рекурсивности, границы разрешимости, конечной и независимой базируемости и близкие к ним проблемы.

Всякий пример конечно определенной универсальной алгебры с неразрешимой проблемой равенства слов легко можно модифицировать в пример конечно базируемого многообразия универсальных алгебр с неразрешимой эквациональной теорией. Используя это, А. И. Мальцев в работе [65] построил конечно базируемое многообразие квазигрупп с неразрешимой эквациональной теорией и поставил в [61] вопрос о существовании конечно базируемых многообразий полугрупп, групп и колец с неразрешимой эквациональной теорией. Положительный ответ на этот вопрос для полугрупп получен в [77]. Пример конечно базируемого многообразия групп с неразрешимой эквациональной теорией построен в работе [57]. В [117] анонсировано утверждение о том, что произвольное конечно базируемое многообразие ассоциативных колец имеет разрешимую эквациональную теорию. В связи с перечисленными результатами актуальной становится проблема распознавания экващюнальной рекурсивности:

Существует ли алгоритм, определяющий по произвольной конечной системе тождеств данной сигнатуры, разрешима ли эквациональная теория многообразия, заданного этой системой тождеств?

К 90-м годам XX века было получено большое количество результатов по разрешимости теорий первого порядка классов алгебраических систем (см. книги [42], [142], обзоры [2], [5], [16], [21], [43], [64], [74], [87], работы [46] - [49] и библиографию к ним). Это позволило Ю. М. Важенину поставить в статье [19] проблему описания всех, в рамках некоторой иерархии, разрешимых теорий данного класса алгебраических систем и для решения ее развить в работах [19], [20], [22] - [25] продуктивную концепцию критических теорий и границ разрешимости. Указанная проблема в случае схемно-альтернативной иерархии решена для многообразия всех полугрупп и периодических многообразий коммутативных полугрупп в работах [19], [116], для многообразия Ьсех групп, нильпотентных и разрешимых многообразий групп в работах [19], [24], [26], [27]. Критические теории многообразий всех колец, ассоциативных, коммутативных, антикоммутативных, нильпотентных, лиевых, йордановых и альтернативных колец найдены в работах [19], [22], [23], [168], [167], [118], [86]. Типы границ разрешимости над-коммутативно-ассоциативных многообразий колец указаны в [85], [173]. В работе [29] найдены границы разрешимости для некоторых псевдомногообразий колец. Эти результаты позволяют сформулировать проблему распознавания границы разрешимости:

Существует ли алгоритм, определяющий по произвольной конечной системе тождеств данной сигнатуры, какова граница разрешимости многообразия, заданного этой системой тождеств ?

В [60] Л. А. Бокуть поставил общую проблему выводимости тождеств для групп: «Существует ли алгоритм, который по любой системе групповых слов /1, — ., /т (от фиксированного множества переменных хг, Х2,—) и отдельному слову / выяснял бы, следует ли тождество / = 1 из тождеств /1 = 1,., /т = 1.» Отрицательное решение этого вопроса получено в [56]. Общую проблему выводимости тождеств можно сформулировать и для произвольных алгебраических систем:

Существует ли алгоритм, который по любой системе тождеств данной сигнатуры Р1, ¦¦¦¦> 'Рт от фиксированного множества переменных Жг, ••- и отдельному тождеству ¡-р выяснял бы, следует ли тождество <�р из тождеств <�р, .,<�рт.

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

Первые примеры многообразий полугрупп, не имеющих конечного базиса, были приведены в работах [17], [122]. Примеры многообразий групп с тем же свойством построены в [3], [80], [163]. В [75] доказано существование многообразия альтернативных алгебр над полем характеристики 2, не имеющего конечного базиса. Многообразие алгебр Ли простой характеристики р с этим же свойством найдено в [38]. Примеры многообразий полугрупп и колец, порожденных конечной алгеброй и не имеющих конечного базиса, построены в работах [149], [84]. Целый ряд работ посвящен проблеме конечной базируемости многообразий универсальных алгебр (см. обзор [83]). В частности, в работе [123] доказано, что любое конгруэнц-дистрибутивное многообразие конечной сигнатуры, порожденное конечной алгеброй, конечно базируемо. Более того, в ней показано, что по порождающей алгебре можно эффективно выписать конечную систему тождеств, задающую соответствующее многообразие. К настоящему времени накоплена весьма обширная информация о конечно базируемых многообразиях (см. обзоры [10], [114] и книгу [9]). Основной вопрос, возникающий в исследованиях этого направления, заключается в следующем: по данной бесконечной системе тождеств определить, является ли многообразие, заданное этой системой, конечно базируемым? Этот вопрос позволяет сформулировать проблему распознавания конечной базируемости:

Существует ли алгоритм, определяющий по произвольной бесконечной системе тождеств данной сигнатуры, является ли многообразие, заданное этой системой тождеств, конечно базируемым?

Первый пример многообразия полугрупп, не имеющего независимого базиса, построен в работе [104]. Другие примеры многообразий полугрупп с этим свойством указаны в работах [95], [105], [152]. В [152] приведен пример системы тождеств моноидов, в [55] — инверсных полугрупп, в [58] — групп, не имеющих независимого базиса. В [95] доказано, что существует многообразие полугрупп, порожденное конечной полугруппой и не имеющее независимого базиса. В работе [35] доказано, что любая двуэлементная алгебра конечной сигнатуры порождает конечно базируемое квазимногообразие и следовательно все квазимногообразия, порожденные двуэлементными алгебрами, независимо базируемы. В [34] построено квазимногообразие, порожденное трехэлементной алгеброй и не имеющее независимого базиса. Эти результаты стимулируют постановку проблемы распознавания независимой базируемости:

Существует ли алгоритм, определяющий по произвольной бесконечной системе тождеств данной сигнатуры, является ли многообразие, заданное этой системой тождеств, независимо базируемым?

Обозначим через С множество всех бесконечных систем тождеств из Т таких, что если X — многообразие, заданное системой тождеств из С, то X — независимо базируемое многообразие и существует строго включающее его многообразие 2), в котором многообразие 3? не обладает покрывающим многообразием и, значит, X не является независимо базируемым в многообразии 2). Вопрос о принадлежности той или иной системы тождеств множеству С мы сформулируем как алгоритмическую проблему, которую назовем проблемой распознавания относительной покрываемости:

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

Пусть Б — множество всех бесконечных систем тождеств из Т таких, что если X — многообразие, заданное системой тождеств из Б, то X не является независимо базируемым многообразием и имеет покрытие в любом строго включающем его конечно базируемом многообразии 2) • Вопрос о принадлежности той или иной системы тождеств множеству Б мы сформулируем как алгоритмическую проблему распознавания относительной конечной покрываемости:

Существует ли алгоритм, определяющий по произвольной бесконечной системе тождеств данной сигнатуры, принадлежит ли она множеству Б ?

Приступим к краткому изложению содержания работы.

Проблема распознавания марковских свойств.

Неразрешимость проблемы распознавания марковских свойств для любого марковского свойства полугрупп доказана в работе [70], групп — в [1], ассоциативных алгебр — в [13], алгебр Ли — в [14]. В свете результата [70] естественно ставить вопрос о разрешимости проблемы распознаваемости марковских свойств для наиболее интересных классов полугрупп. Неразрешимость этой проблемы для любого марковского свойства полугрупп с сокращениями доказана в работе [120], инволютированных и инверсных полугрупп анонсирована в [18].

Проблема Бернсайда о периодических группах [127] породила целое направление, которому посвящены, например, книги [3], [59]. Она стимулировала исследования в смежных областях, в частности, в теории полугрупп (см., например, работы [98], [130], [132], [133]). Обозначим через,, г2 многообразие полугрупп, заданное тождеством хГг — хГз, где Г и Г2 — натуральные числа такие, что > г^ > 2. Следуя [138] (см. пункт 3.3.4), многообразие Г2 будем называть бернсайдовским многообразием полугрупп индекса г и периода Г2 — Г]. Следующая теорема дает, в частности, первый пример собственного многообразия полугрупп, для которого неразрешима проблема распознавания марковских свойств.

Теорема 1. Проблем, а распознавания любого марковского свойства, которым обладает одноэлементная полугруппа, для многообразия) Гз неразрешима.

Следуя [138], проблемой конечности назовем вопрос о существовании алгоритма, определяющего по произвольной конечно определенной в многообразии X полугруппе, является ли она конечной, а проблемой тривиальности — вопрос о существовании алгоритма, определяющего по произвольной конечно определенной в многообразии X полугруппе, является ли она одноэлементной. Поскольку свойства полугрупп «быть конечной» и «быть одноэлементной» являются марковскими и этими свойствами обладает одноэлементная полугруппа, из теоремы 1 с очевидностью вытекает утвердительный ответ на вопрос 3.10 из [138]. А именно, справедливо.

Следствие 1. В многообразии 53Г1 проблемы тривиальности и конечности неразрешимы.

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

В работе [148] доказана неразрешимость проблемы распознавания эквациональной рекурсивности для многообразия всех универсальных алгебр, сигнатура которых состоит из символов двух бинарных операций и двух констант. В [144] неразрешимость этой проблемы установлена для многообразия всех универсальных алгебр произвольной нетривиальной сигнатуры. В работе [57] доказана неразрешимость проблемы распознавания эквациональной рекурсивности для многообразия всех групп. В [117] анонсирована разрешимость эквациональной теории произвольного конечно базируемого многообразия ассоциативных алгебр над коммутативным нетеровым кольцом и, стало быть, для таких многообразий проблема распознавания эквациональной рекурсивности разрешима. Для некоторых собственных многообразий полугрупп разрешимость проблемы распознавания эквациональной рекурсивности можно получить из известных результатов по разрешимости элементарных теорий, позитивных теорий и проблемы равенства. Соответствующая картина для многообразий всех колец и всех полугрупп иная. А именно, справедлива.

Теорема 2. Проблема распознавания эквациональной рекурсивноети для многообразия всех полугрупп неразрешима.

Из этой теоремы непосредственно вытекает.

Следствие 2. Проблема распознавания границы разрешимости для многообразия всех полугрупп неразрешима.

Рассмотрение проблемы эквациональной рекурсивности для многообразия всех колец основано на интерпретации определяющих соотношений полугрупп кольцевыми тождествами. Это позволяет в нижеследующей теореме 3 и следствиях 5, 4, 6 установить тесную связь между алгоритмическими свойствами класса конечно определенных полугрупп и класса конечно базируемых многообразий колец. Прежде чем приступить к формулировке этой теоремы, введем ряд вспомогательных определений. Обозначим через S класс всех конечно определенных полугрупп, т. е. полугрупп, заданных конечным множеством определяющих соотношений и конечным множеством порождающих. Для рекурсивно перечислимых множеств натуральных чисел Nx и ЛГ2 говорят, что Мх сводимо по Тьюрингу к iV2 и пишут N <�т N2, если характеристическая функция Хщ (х) множества Ni является рекурсивной относительно функции Хщ (х)> т-е- (ж) получается из элементарных функций и Xn2 (х) с помощью операций суперпозиции, примитивной рекурсии и минимизации [16]. Рассмотрим следующее отношение эквивалентности: Nx N2 ОNt A N2.

Рх УУРх — {(х ((((((х (ух))х)х)х)х)х))х), Фх ¦ У уфх = ((ж (((((((а-(?/ж))ж)а-)ж)а-)а-)ж))ж).

Для произвольной полугруппы S с множеством образующих ai, a2,., a"} и множеством определяющих соотношений ai, a2,. ., an) = Vi (ax, a2,. ¦ ¦, a") | 1 < i < m] и для x El F обозначим через Axj, i? {1,2,., n}, отображение, определенное на элементах кольца F следующим образом: yAxj = уфх<�ргхфх, где у<�р1х — y<�рх. Пусть.

3Es — многообразие колец, заданное тождествами.

2х = 0, {xy)(zt) = О, ущ (Ах, 1, АХ12,., AXin) = yvi (AXil, AXi2,. ., AXtn),.

1 < i < го, а — многообразие всех метабелевых колец характеристики два, т. е. многообразие, заданное тождествами 2х = 0, (xy)(zt) = 0. Обозначим через Fffi и F3? s кольца счетного ранга, свободные в многообразиях £Н и соответственно и имеющие множество {ei, е2,., еп,.} свободных образующих, а через F]$K и Fk3? s кольца ранга к, свободные в многообразиях и X, s соответственно. Пусть, наконец, X = [ S? §}.

Теорема 3. Имеют место следующие четыре утверждения:

1. Семейство X рекурсивно и многообразие Жз однозначно определяется полугруппой S G §, причем отображение S —"¦ ?s инъективно.

2. В полугруппе S разрешима проблема равенства тогда и только тогда, когда ЗС, д — многообразие с разрешимой эквациональной теорией.

3. Если S — полугруппа с неразрешимой проблемой равенства тьюринговой степени неразрешимости а, то тьюрингова степень неразрешимости проблемы равенства в кольце F^ j? s для любого fc? N тоже равна а.

4. Если S — полугруппа с неразрешимой проблемой равенства, причем твюринговы степени неразрешимости проблем равенства фиксированным словам в ней равны ai, «2, ¦ ¦ -, то тьюринговы степени неразрешимости проблем равенства фиксированным словам в кольце Fk%s для любого к G N тоже равны ai, «2,.

Согласно [126] множество конечно определенных полугрупп с разрешимой проблемой равенства не является рекурсивно перечислимым. Отсюда в силу пунктов 1, 2 теоремы 3 множество многообразий вида Xs с разрешимой эквациональной теорией тоже не является рекурсивно перечислимым. Таким образом из пунктов 1, 2 теоремы 3 непосредственно вытекает.

Следствие 3. Проблема распознавания эквациональной рекурсивпости для многообразия всех колец неразрешима.

А.И.Мальдев в работе [64] поставил вопрос: какие степени неразрешимости могут иметь элементарная, универсальная, квазиэквациональная и эквациональная теории рекурсивно аксиоматизируемого класса алгебраических систем. Обзор результатов по этой проблеме можно найти в [16], [87]. В [125] доказано, что существует конечно определенная полугруппа с наперед заданной тьюринговой степенью неразрешимости проблемы равенства. Отсюда и из пункта 3 теоремы 3 очевидным образом вытекает.

Следствие 4. Для любой тьюринговой степени неразрешимости a существует конечно базируемое многообразие колец X такое, что эквациональная теория X и проблема равенства в кольце FtX для любого к G N имеют степень неразрешимости а.

В работах [108], [109], [125], [158] независимо доказано существование конечно определенной полугруппы с заданной тьюринговой степенью неразрешимости проблемы равенства фиксированному слову. Отсюда и из пункта 4 теоремы 3 очевидным образом вытекает.

Следствие 5. Для любой тьюринговой степени неразрешимости существует конечно базируемое многообразие колец X такое, что для любого к G N кольцо F^X имеет заданную тьюрингову степень неразрешимости проблемы равенства фиксированному элементу кольца.

В работе [158] доказано существование конечно определенной полугруппы, для которой тьюринговы степени неразрешимости проблемы равенства фиксированным словам могут быть произвольными из данного рекурсивно перечислимого набора тьюринговых степеней неразрешимости и тьюрингова степень неразрешимости проблемы равенства произвольна, но не меньше объединения предыдущих степеней. Отсюда и из пунктов 3, 4 теоремы 3 очевидным образом вытекает.

Следствие 6. Существует конечно базируемое многообразие колец X такое, что для любого к G N в кольцах F^X тьюринговы степени неразрешимости проблемы равенства фиксированным элементам кольца могут быть произвольными из данного рекурсивно перечислимого набора тьюринговых степеней неразрешимости. При этом тьюрингова степень неразрешимости эквациональной теории многообразия X произвольна, но не меньше объединения предыдущих степеней.

В работе [46] получено описание многообразий полугрупп с неразрешимой элементарной теорией. Это описание позволило в [116] сформулировать следующее утверждение:

Для произвольного многообразия 9Л коммутативных периодических полугрупп следующие условия эквивалентны:

1) элементарная теория многообразия ffil неразрешима,.

2) многообразие Ш1 содержит хотя бы одно из многообразии var {ж2 = х, ху = ух}, var{xyz = t2, xy = ух} и var{хру = у, ху = ух} V var{a:y = zt}, где р — простое число,.

3) граница разрешимости многообразия ЯН равна {3V~i A V}.

Несложно убедиться в том, что из этого результата вытекает разрешимость проблемы распознавания границы разрешимости для периодических коммутативных многообразий полугрупп. Следующее утверждение обобщает результат работы [116] на случай многообразий с перестановочным тождеством.

Теорема 4. Произвольное конечно базируемое периодическое многообразие полугрупп X, удовлетворяющее перестановочному тождеству, имеет либо пустую границу разрешимости, либо его граница разрешимости равна {3V-" Л V}.

Заметим, что из приведенного выше результата из [116] вытекает существование многообразий как с пустой границей разрешимости, так и с границей разрешимости {ЗУ-> А V}. При этом существует алгоритм, определяющий по конечному списку тождеств, задающему периодическое многообразие полугрупп, удовлетворяющее перестановочному тождеству, какова его граница разрешимости. Стало быть, проблема распознавания границы разрешимости для периодических многообразий полугрупп, удовлетворяющих перестановочному тождеству, разрешима.

Априори ясно, что вопрос о разрешимости элементарных и позитивных теорий, представляя собой самостоятельную задачу, тесно связан с рассмотрением проблемы распознавания границы разрешимости. Неразрешимость элементарной теории любой немоногенной свободной полугруппы и любой немоногенной свободной инверсной полугруппы доказана в работах [154] и [164] соответственно. Ю. М. Важенин и Б. В. Розенблат в [31] доказали разрешимость позитивной теории свободной полугруппы счетного ранга. В [40] и [89] доказана неразрешимость позитивной теории свободной полугруппы конечного ранга и свободной инверсной полугруппы конечного ранга соответственно. В работе [32] доказано, что для свободной счет-нопорожденной алгебраической системы позитивная теория без констант, позитивная теория с константами, хорновская позитивная и диофантова теории разрешимы или неразрешимы одновременно. В работе [91] доказана разрешимость элементарных теорий полугрупп, свободных в конечно базируемых многообразиях полугрупп, удовлетворяющих перестанивочному тождеству, откуда непосредственно вытекает разрешимость позитивных теорий соответствующих многообразий. В обзоре [15] Л. А. Бокуть поставил вопрос о разрешимости позитивной теории свободных ассоциативных (лиевых) алгебр (конечного ранга, бесконечного ранга, с единицей, без единицы). Немалый интерес представляет также исследование разрешимости различных фрагментов позитивной теории, в частности, УЗЛ-теории, т. е. проблемы разрешимости уравнений. Г. С. Маканин в [62] доказал разрешимость проблемы совместности уравнений в свободных полугруппах, Для свободных ассоциативных (лиевых) колец проблема совместности уравнений, как показал в [92] В. А. Романьков, неразрешима. В работах [20], [22], [28], [30] доказана неразрешимость проблемы совместности уравнений для ряда других свободных колец. Изучению вопросов, связанных с совместностью уравнений в группах, посвящены работы [39], [41], [92], [93], [94]. В обзоре [15] Л. А. Бокуть поставил вопрос о разрешимости проблемы совместности уравнений в свободных ассоциативных (лиевых) алгебрах над алгебраически замкнутым полем.

Нижеследующие теоремы 5, 6, 7 содержат важную информацию о разрешимости позитивных теорий многообразий полугрупп и колец. Пусть X — непериодическое многообразие полугрупп. Обозначим через Хп^ класс всех конечных полугрупп из многообразия X. Пусть ЕХ — полугруппа счетного ранга, свободная в многообразии X. В свете перечисленных выше результатов представляет интерес следующая теорема, устанавливающая связь между позитивными теориями свободных полугрупп счетного ранга и классов конечных полугрупп.

Теорема 5. Для любого языка,? С Р теория ЬХ совпадает с теорией ЬХ П.

В силу результатов [31], [91] из теоремы 5 непосредственно вытекает.

Следствие 7. Разрешимы позитивные теории класса всех конечных полугрупп и класса всех конечных полугрупп, принадлежащих непериодическому конечно базируемому многообразию полугрупп, удовлетворяющему перестанивочному тождеству.

Следствие 7 позволяет описать границу разрешимости класса всех конечных полугрупп в рамках схемно-альтернативной иерархии БА. А именно, справедливо.

Следствие 8. Границей разрешимости класса всех конечных полугрупп является множество {У-^}.

Отметим, что согласно этому следствию и работе [19] граница разрешимости многообразия всех полугрупп совпадает с границей разрешимости класса всех конечных полугрупп.

Пусть X — произвольное многообразие колец, заданное полиоднородными тождествами [10]. Обозначим через X П ^ класс всех конечных колец из многообразия X, а через ЕХ кольцо счетного ранга, свободное в многообразии X.

Теорема 6. Позитивные теории кольца ЕХ, многообразия X и класса X П ^ совпадают.

Пусть 2) — произвольное многообразие полугрупп, групп, колец или алгебр над полем, jF2) — полугруппа (группа, кольцо, алгебра) счетного ранга, свободная в многообразии 2), 2) Л F класс всех свободных полугрупп (групп, колец, алгебр) из многообразия 2). Обозначим через L — множество предложений вида.

Vx (fi (z) = gi (S) А. Л fm (x) — дт (х) -«¦ f0(x) = д0(х)).

Теорема 7. Позитивные теории и L-теории F2) и класса 2) П F совпадают.

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

Из неразрешимости проблемы равенства в многообразии йордановых колец [106] в силу теоремы 1 из [173] вытекает, что граница разрешимости многообразия йордановых колец равна {V3,V-iV}. Следующая теорема устанавливает аналогичный факт для классов конечных альтернативных и йордановых колец и дает, в частности, отрицательный ответ на вопрос из [15] о разрешимости проблемы равенства для классах конечных альтернативных и йордановых колец.

Теорема 8. Границей разрешимости класса всех конечных альтернативных и класса всех конечных йордановых колец является множество {V3, V-'V}.

Рассмотрим теперь вопрос о возможности характеризации многообразий с разрешимой эквациональной теорией на языке решетки подмногообразий. В работе [76] построено минимальное многообразие полугрупп с неразрешимой проблемой равенства. Другие примеры минимальных многообразий полугрупп с неразрешимой проблемой равенства указаны в [97], [99]. Минимальные псевдомногообразия полугрупп с неразрешимой проблемой равенства построены в работе [157]. В работах [100], [102] указано минимальное многообразие ассоциативных алгебр с 1 над полем характеристики 0 с неразрешимой проблемой равенства. Пример многообразия алгебр Ли с неразрешимой проблемой равенства, каждое собственное подмногообразие которого имеет разрешимую проблему равенства, приведен в [137]. Примеры минимальных многообразий групп с неразрешимой проблемой равенства анонсированы в [138] (теоремы 6.8 и 6.9, см. также [НО]). В работе [111] доказано существование бесконечных цепочек многообразий алгебр Ли над полем характеристики 0 и групп, в которых многообразия с разрешимой и неразрешимой проблемой равенства чередуются. В обзоре [138] (теорема 3.16) сформулировано утверждение о том, что для любого непериодического многообразия полугрупп и для любого периодического многообразия полугрупп, все группы которого локально конечны, следующие два условия эквивалентны: 1) всякое конечно базируемое подмногообразие имеет разрешимую эквациональную теорию, 2) все нильполугруппы в многообразии локально конечны. В свете перечисленных результатов, а также теоремы 2 и следствия 3 естественно возникает вопрос о существовании бесконечных цепочек многообразий, в которых многообразия с разрешимой и неразрешимой эквациональной теорией чередуются. Ответ на этот вопрос для полугрупп и колец дают следующие четыре теоремы.

Теорема 9. Существует последовательность типа ш конечно базируемых многообразий неассоциативных колец aic®ica2c®2c. такая, что для каждого i эквациональная теория 21? неразрешима, а эквациональная теория разрешима.

Теорема 10. Существует последовательность типа си* конечно базируемых многообразий неассоциативных колец aiD"iDa2D"2D. такая, что для каждого i эквациональная теория 21, — неразрешима, а эквациональная теория IBi разрешима.

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

211С"1с212С®2С. такая, что для каждого i эквациовальная теория многообразия 21, — и класса 21гП § всех конечных полугрупп из многообразия 21, неразрешима, а эквациональная теория многообразия 03, — я класса 03 г П ^ всех конечных полугрупп из многообразия 03, — разрешима.

Теорема 12. Существует последовательность типа ш* конечно базируемых многообразий полугрупп такая, что для каждого г эквациональная теория многообразия 21ги класса 21гП ^ всех конечных полугрупп из многообразия 21, — неразрешима, а эквациональная теория многообразия 03, и класса 03, — П $ всех конечных полугрупп из многообразия 03- разрешима.

Естественно поставить вопрос: можно ли в цепочках из теорем 9−12 отношение включения заменить отношением покрытия. В частности, существуют ли конечно базируемые многообразия X и 3) такие, что многообразие 2) покрывает X и эквациональная теория X разрешима, эквациональная теория 2) неразрешима- [эквациональная теория X неразрешима, эквациональная теория 2) разрешимаэквациональная теория X неразрешима, эквациональная теория 2) неразрешима]. В связи с этим представляют интерес следующие три теоремы.

Теорема 13. Существует конечно базируемое многообразие колец X с неразрешимой эквациональной теорией и бесконечная последовательность конечно базируемых многообразий колец 2) г-, г? М, такие, что для любого г € N эквациональная теория многообразия 2) г-неразрешима и многообразие 2) гпокрывает многообразие X.

Теорема 14. Для произвольного собственного многообразия полугрупп X существует многообразие полугрупп 2) такое, что 2) покрывает многообразие X, 2) конечно базируемо, если X — конечно базируемое, эквациональная теория многообразия 2) разрешима тогда и только тогда, когда разрешима эквациональная теория многообразия X.

Теорема 15. Пусть X — произвольное многообразие полугрупп, заданное тождествами, зависящими от конечного числа переменных, все периодические группы которого локально конечны. Тогда все ниль полугруппы из многообразия X локально конечны или в многообразии X существует подмногообразие 2) с неразрешимой эквациональной теорией, имеющее бесконечное множество покрывающих многообразий с неразрешимой эквациональной теорией.

В работе [121] Д. Алберт, Р. Балдингер и Д. Роудз построили конечно базируемое многообразие полугрупп с неразрешимой эквациональной теорией класса всех конечных полугрупп. В связи с этим результатом и теоремами 11 и 12 представляет интерес следующая.

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

Легко понять, что разрешимость эквациональной теории многообразия равносильна разрешимости проблемы равенства в свободной алгебре счетного ранга. Заметим, что в многообразии полугрупп, построенном в работе [77], неразрешима проблема равенства во всех немоногенных свободных полугруппах. В связи с этим представляют интерес следующие две теоремы.

Теорема 17. Для любого натурального числа п существует конечно базируемое многообразие полугрупп [колец] Х&bdquoтакое, что проблема равенства в полугруппе [кольце] ^тХ&bdquoранга т, свободной [свободном] в многообразии Х&bdquo-, разрешима тогда и только тогда, когда т <�п.

Теорема 18. Существует многообразие колец X с неразрешимой эквациональной теорией такое, что для любого натурального п проблема равенства в кольце РПХ ранга п, свободном в многообразии X, разрешима.

В работе [145] рассматриваются следующие два определения разрешимости проблемы равенства для многообразия универсальных алгебр 21:

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

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

Там же построены три примера многообразий универсальных алгебр, имеющих неразрешимую проблему равенства в смысле 1-го определения и разрешимую в смысле 2-го. В частности, модификацией примера из работы [166] в [145] построен пример многообразия универсальных алгебр с неразрешимой эквациональной теорией, а значит и неразрешимой проблемой равенства в смысле 1-го определения, имеющего разрешимую проблему равенства в смысле 2-го определения. Другой пример многообразия универсальных алгебр с неразрешимой эквациональной теорией, имеющего разрешимую проблему равенства в смысле 2-го определения, построен в работе [131]. Несложной модификацией многообразия Ж, построенного в доказательстве теоремы 18, можно получить.

Следствие 9. Существует многообразие колец с разрешимой проблемой равенства в смысле определения 2 и неразрешимой проблемой равенства в смысле определения 1.

Пусть 1С — некоторая алгебраическая система, varК- — многообразие, порожденное 1С. Очевидно, что если К. свободна в многообразии var 1С, то разрешимость проблемы равенства в К равносильна разрешимости эквациональной теории К. Однако, если К не будет свободна в var/C, то это не всегда так. В работе [57] построен пример группы с тремя образующими, для которой разрешима проблема равенства и неразрешима эквациональная теория. Там же отмечено, что существует группа с двумя образующими, удовлетворяющая тем же условиям. Следующая теорема дает аналогичный пример для колец.

Теорема 19. Существует моногенное кольцо с разрешимой проблемой равенства, эквациональная теория которого неразрешима.

Общая проблема выводимости тождеств.

В [78] доказана неразрешимость общей проблемы выводимости тождеств для группоидов. Там же отмечено, что эта проблема неразрешима и для полугрупп. Неразрешимость обсуждаемой проблемы для многообразий групп доказана в [56]. Следующие три теоремы показывают, что общая проблема выводимости тождеств неразрешима для многообразий колец, классов конечных колец и классов конечных полугрупп.

Теорема 20. Не существует алгоритма, определяющего по произвольному конечно базируемому многообразию колец, удовлетворяет оно тождеству (xy)(zt) = 0 или нет.

Теорема 21. Не существует алгоритма, определяющего по произвольному конечно базируемому многообразию колец, удовлетворяет ли класс всех конечных колец из этого многообразия тождеству (xy)(zt) = 0.

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

Проблема распознавания конечной базируемости.

Как показано в [78], не существует алгоритма, определяющего по произвольному конечно базируемому многообразию группоидов, будет ли всякое его подмногообразие конечно базируемым. В работе [53] доказано, что произвольное многообразие ассоциативных алгебр над полем характеристики 0 конечно базируемо. Отсюда вытекает разрешимость проблемы распознавания конечной базируемости для таких многообразий. Имеется довольно много условий, позволяющих в ряде частных случаев ответить на вопрос о конечности базиса многообразия полугрупп (см., например, [54], [96], [114] теорема 2.2 и теорема 3.2, [149], [150], [151], [165]). Из этих результатов можно получить разрешимость проблемы распознавания конечной базируемости для некоторых собственных многообразий полугрупп. Однако имеет место.

Теорема 23. Проблема распознавания конечной базируемости для многообразия всех полугрупп [групп, колец] неразрешима.

Проблема распознавания независимой базируемости.

Существование независимого базиса тождеств для локально конечных разрешимых многообразий групп доказано в [81]. В работах [7] и [72] доказано, что каждое многообразие полугрупп, заданное уравновешенными и О-приведенными тождествами, обладает независимым базисом. Следовательно, проблема распознавания независимой базируемости разрешима для локально конечных разрешимых многообразий групп и многообразий полугрупп, заданных уравновешенными и О-приведенными тождествами. Несложно убедиться в том, что произвольное однородное многообразие колец независимо базируемо. Поэтому для таких многообразий колец проблема распознавания независимой базируемости разрешима. Однако справедливы.

Теорема 24. Проблема распознавания независимой базируемости для многообразия всех полугрупп [моноидов, колец] неразрешима.

Теорема 25. Не существует алгоритма, определяющего по произвольной конечной [бесконечной рекурсивной] системе тождеств полугрупп [групп, колец], будет ли она независима.

Изучение бесконечно базируемых многообразий показало, что отсутствие независимого базиса тождеств — не исключение, а типичное явление. Та же ситуация имеет место и для квазимногообразий (см., например, [36], пункт 6.3). Более того, до сих пор не известно ни одного примера конечной алгебры, имеющей бесконечный независимый базис квазитождеств (см. [36], пункт 6.4). В связи с этим естественно возникает стремление к рассмотрению каких-либо аналогов независимости для многообразий, не имеющих независимого базиса.

Будем говорить, что множество тождеств? независимо разбиваемо, если существует разбиение? = и"ем?га такое, что уаг£ ф уаг££&bdquoдля любого п? N. Множество? предложений языка логики первого порядка называется конечно независимо разбиваемым, если существует разбиение? = ипеи? п такое, что ?" конечно и уаг? ф уаг ??" для любого п € N (см. [36], пункт 6.3).

В [34] доказано (см. также [36], следствие 6.4.2), что существует многообразие универсальных алгебр К и трехэлементная алгебра, А такие, что, А не имеет независимо разбиваемого базиса в многообразии К. Там же (см. также [36], теорема 6.3.2) построен пример многообразия универсальных алгебр К, содержащего континуум подквазимногообразий, имеющих в К независимо разбиваемый базис квазитождеств, но не имеющих в К независимого базиса квазитождеств, и поставлен вопрос:

Верно ли, что если квазимногообразие К' имеет относительно квазимногообразия К конечно независимо разбиваемый базис квазитождеств, то К' имеет относительно К независимый базис квазитоокдеств ?

Отрицательный ответ на этот вопрос дает следующее.

Предложение 1. Существует квазимногообразие К, содержащее 2Ш подквазимногообразий, имеющих относительно квазимногообразия К конечно независимо разбиваемый базис квазитождеств и не имеющих относительно К независимого базиса квазитождеств.

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

Теорема 26. Существуют многообразия полугрупп X С 2) такие, что X не имеет независимо разбиваемого базиса в многообразии 2).

Теорема 27. Существуют многообразия полугрупп X С 2) такие, что X — независимо базируемо, X имеет конечно независимо разбиваемый базис в многообразии 2), но не имеет независимого базиса в многообразии 2).

Проблемы распознавания относительной покрываемости и распознавания относительной конечной покрываемости.

Рассмотрим следующие два утверждения.

А. Многообразие полугрупп X обладает независимым базисом тождеств.

Б. Многообразие полугрупп X облагает покрывающим многообразием в любом интервале вида [3?-2)], где 2) — многообразие полугрупп, строго содержащее X.

В [103] А. Н. Трахтман сформулировал следующую задачу (вопрос 2.55): а) всегда ли из утверждения, А следует утверждение Б, б) всегда ли из утверждения Б следует утверждение А.

В работе [58] доказано, что существуют многообразия групп X и 2) такие, что X С 2), X независимо базируемо, но не имеет в многообразии 2) покрывающего многообразия и, значит, X не является независимо базируемым в многообразии 2}. В связи с этим результатом представляет интерес следующая теорема, дающая, в частности, отрицательный ответ на вопрос 2.55.а).

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

В работе [58] доказано, что если многообразие групп ЭДТ независимо базируемо [в многообразии 25], то для каждого конечно базируемого [в многообразии 23] многообразия Э ЭДТ существует подмногообразие ШТ2 С, покрывающее Ш1. В свете этого результата и вопроса 2.55.6) представляет интерес следующая.

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

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

Пусть ы- — слово, х — буква, не участвующая в записи ги. Очевидно, что пара тождеств иих = Х1Л = но выполняется в некоторой полугруппе 5 тогда и только тогда, когда 5 содержит нуль 0, и каждое значение слова ад в 5 равно 0. Поэтому указанную пару тождеств можно записывать в виде одного символического тождества и> = 0 [114]. Система тождеств {-«- = ?-г | г? 1} называется независимой, если никакое из тождеств этой системы не является следствием всех остальных (см., например, [9], стр. 148). Говорят, что многообразие алгебраических систем независимо базируемо (в многообразии 3), если существует независимая система тождеств, являющаяся базисом этого многообразия (в многообразии 3).

Тождество и = V называется уравновешенным, если каждая буква входит в слова и и V одинаковое число раз [114].

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

Обозначим через I функцию, определенную на элементах свободной полугруппы и принимающую значения на множестве натуральных чисел, такую, что ((и) — длина слова и для любого и.

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

Подстановкой называется любой гомоморфизм одной свободной полугруппы в другую. Слово и/ называется изотермом для тождества и = V [147], если для любой подстановки <-р из того, что <�р (и) является подсловом в слове ги, следует, что. Говорят, что слово и избегает слово V, если среди подслов слова и нет слов <�р{ь) ни для какой подстановки <�р [124], [50]. Будем говорить, что и — бесквадратное слово, если и избегает слово х2.

Пусть & — многообразие всех полугрупп. Для произвольного многообразия полугрупп X обозначим через ГХ полугруппу, свободную в многообразии X, имеющую счетное множество свободных образующих {е, ., еп,.}, через Р"Х — полугруппу ранга п, свободную в многообразии X, множество свободных образующих которой равно множеству {е], в2,., е&bdquo-}.

Обозначим через X = {х, Х2, ¦ ¦ - У, У1, У2 ¦ • ¦} некоторый алфавит переменных. Рассмотрим отображение 6, определенное следующим образом: —> х,., еп —> хп,&bdquo-. Для произвольного многообразия X равенство и = V выполняется в полугруппе РХ тогда и только тогда, когда тождество ©-(и) = 0(/и) выполняется в многообразии X (см., например [66]). Используя это соотношение, мы в дальнейшем часто будем переходить от рассмотрения тождеств в многообразии к равенствам в свободной полугруппе, не делая дополнительных оговорок.

Обозначим через 9Т2 многообразие нильполугрупп ступени 2, т. е. многообразие, заданное тождеством х2 = 0 или системой тождеств х2у = ух2 = х'1. Пусть 23Г1, г2 — многообразие полугрупп, заданное тождеством хГ1 = хГ2, где Г и г2 — натуральные числа такие, что ri > г2 > 2.

В доказательствах основных результатов мы будем существенно использовать технику, развитую в работе [77], а также некоторые результаты из этой работы. Поэтому ниже мы приведем необходимые нам сведения из этой работы в удобных для нас формулировках и обозначениях.

Пусть S — произвольная полугруппа, {ai, аз,., а&bdquo-} множество образующих полугруппы S, {иц = Щ2 I г е О — множество определяющих соотношений полугруппы S. Рассмотрим слова Ркл = хук+1×2, к > 3, г G {1,2., к}, из работы [77]. Пусть к = п + 4 и {Un{x, y) = Ui2{x, y) I i G 1} — множество тождеств, полученное из множества определяющих соотношений {щ = «?2 | г G /} заменой каждого вхождения aj, 1 < j < п, на вхождение слова Pk, k-iPk, jPk, k-2¦ Обозначим через Xs многообразие полугрупп, заданное тождествами {Unix, у) = Ui2(x, у) | г G /}. В работе [77] доказана.

Лемма 1. Для любого к > 3 множество слов Р = {Рк, 1, Рк, 2, ¦ ¦ ¦, Pk, k-i} удовлетворяют следующим двум условиям:

1. Всякое слово вида Pk, iiPk, i2 ¦ ¦ ¦ Pk, in содержит лишь п вхождений слов из Р.

2. Если слово Pkj1 Pk, i2 ¦ ¦ ¦ Pk, in содержит подслово ip (Pk, iPk, j) для некоторой подстановки ip, то либо (р (х) = х и ip (y) = у, либо слово ii ?2. in не является бесквадратным.

Слова вида Pk, i1Pk, i2 ¦ ¦ -Pk, in Для n> 1 в дальнейшем будем называть Р-словами.

Для произвольного w слово w назовем Р-разбиением слова w, если w не содержит подслов, являющихся Р-словамислово uviu2 назовем Р-разбиением слова w, если — произведение Р-слов, Р-слова не являются подсловами слов «i, и2 и слово w графически равно слову слово U1V1U2V2. v, rvrur+i при г > 2 назовем Р-разбиением слова w, если.

1. для любого j слово vj — произведение Р-слов,.

2. Mi и ur+i — возможно пустые слова,.

3. «2, U3,., ur — непустые слова,.

4. слова «i, «2,., Hr+i не содержат подслов, являющихся Р-словами,.

5. w графически равно UIVU2V2. .urvrur+1.

Если слово w является Р-разбиением слова w, то будем говорить, что слово w имеет Р-разбиение ранга 0. Если слово uiviu2 является Р-разбиением слова w, то будем говорить, что слово w имеет Р-разбиение ранга 1. Если слово U1V1U2V2. urvrur+i при г > 2 является Р-разбиением слова w, то будем говорить, что слово w имеет Р-разбиение ранга г.

Если (Л- <) — частично упорядоченное множество и a, Ь C А, то, а иЬ называются сравнимыми, если, а < Ь или Ь < а. В противном случае a и 6 называются несравнимыми и пишется, а || Ь. Говорят, что, а покрывает b или b покрывается a, и пишут b -< a, а >- 6, если, а > 6 и не существует с G А, такого, что, а > с > Ь. Элемент, а называется покрытием элемента b в частично упорядоченном множестве (А-<).

Тождество u = v называется уравновешенным, если каждая буква входит в слова и и v одинаковое число раз [114].

Ю.М. Важенин в [19] предложил эффективный метод описания разрешимых теорий классов алгебраических систем на языке критических теорий. Пусть S — элементарный язык некоторой конечной сигнатуры сг, т. е. совокупность всех формул логики первого порядка этой сигнатуры, записанных в пренексной нормальной форме. Множества L С? будем называть языками. Для класса алгебраических систем /С сигнатуры, а и языка L через L/C обозначим совокупность всех предложений из L, истинных на К, и назовем ее L-теорией или, просто, теорией класса К. Пусть H — некоторое семейство языков, упорядоченное включением и покрывающее весь элементарный язык ?. Подобные семейства будем называть иерархиями языков. Иерархия языков H определяет для данного класса К иерархию теорий НК, = {ЫС | L G H}. Теория LK называется критической для данной иерархии Н, если в иерархии H Кона является минимальной неразрешимой теорией. Множество критических теорий данного класса X. называется границей разрешимости и обозначается через В (Х). Если иерархия H рекурсивна, т. е. рекурсивно отношение включения на ней, и удовлетворяет условию минимальности, то, очевидно, для языка L G H теория LK, разрешима тогда и только тогда, когда она не включает в себя ни одной критической теории. Поэтому для таких иерархий описание критических теорий данного класса автоматически дает описание всех разрешимых теорий.

Дадим определение схемно-альтернативной иерархии, построенной Ю. М. Важениным в работе [19]. Обозначим через {V, 3}° множество всех альтернирующих слов из V, 3, включая пустое слово. Если х — некоторый символ, то х1 = х и ж° — пустой символ. Пусть п < ш-, 9 = л Vпв = | / < «}.

Пусть.

Сг.С^т А" V? ^ {Ягх-.Шfftl Д¹ -Шкц | € {V, 3}а, вг/п <1 <�р, яда ^ сг < тг, идп ^< то> ж, у — всевозможные наборы переменных- / < & или (I = к и = С]) — € {0,1}- с1, е^ Е — атомные формулы }.

Схемно-альтернативной иерархией называется упорядоченная включением совокупность БА ^ А&tradeУ?, С1. Ск->т А" V* | С1. СЬ е {У, 3}а, т, п, р е {0,1}}, где А" V" — о о о о о о о о о о о зуэузу узузуз эуэуз-. зузузл зузуэу узузу-. узузуа уэуэуу зуэу-.л зуэу-.у зуэуау узуз-.л узуз-гу узузлу зуз-.ау уэу-.лу эузуз узузу зузу-ч зузул зузуу узуз-" уз? зл узузу зуз-1л зуз-|у зузлу узу->л узу-^у узулу зу->ду уэ-<�лу зузу узуз зуз-. зузл зуэу узу-" уэул узуу зу-1л зу-.у зулу уз-.л уэ-.у узлу э-1лу у-.лу зуз узу зу-. зул зуу уз-1 уза узу 3-*л э-.у злу у-.л у-.у улу -1ау зу уз 3−1 зл зу у-" ул уу ->лiv лу.

Диаграмма схемно-альтернативной иерархии БА.

Граница разрешимости класса К алгебраических систем — это список всех языков L из схемно-альтернативной иерархии SA таких, что теория LK, является критической, т. е. минимальной в иерархии SAK неразрешимой теорией. В работе [19] доказано, что иерархия SA рекурсивна и удовлетворяет условию минимальности. Поэтому как отмечено выше описание границы разрешимости дает описание всех в рамках иерархии SA разрешимых теорий данного класса К,', теория LK, для L G SA разрешима тогда и только тогда, когда L не включает ни один из языков, принадлежащих границе разрешимости класса /С.

При доказательстве теорем мы будем активно использовать интерпретацию работы двух-ленточных машин Минского [63]. Впервые этот метод в нужной нам форме был использован Ю. Ш. Гуревичем [37] при доказательстве неразрешимости квазиэквациональной теории классов конечных полугрупп и ассоциативных колец. Подробное изложение методов интерпретации машин Минского, а также обзор результатов можно найти в [138].

Пусть V — некоторое рекурсивно перечислимое нерекурсивное множество натуральных чисел, р — частичная характеристическая функция множества V. Обозначим через м двух-ленточную машину Минского, вычисляющую функцию р [146]. В дальнейшем мы будем полагать, что до, qi, 42, ¦ ¦ •, Чт — внутренние состояния машины М, где gi — начальное состояние,^о — заключительное состояние. Если машина находится в состоянии qi и j-я лента сдвинута на ¿-у ячеек влево, то будем говорить, что М находится в конфигурации [gi^i^]-Конфигурации [gi2n0], п 6 N, будем называть начальными. Конфигурацию [(/о 10] будем называть заключительной.

Программа машины М состоит из команд вида qiS^S-j —"¦ qj? ?2, где д, — внутреннее состояние машины перед выполнением команды, qj — внутреннее состояние машины после выполнения команды, 6к — символ в обозреваемой ячейке ¿—ой ленты, £к 6 {—1, 0,1}, если £к = — 1, то в результате выполнения команды к-я лента сдвигается на одну ячейку влево, если? k = 1, то в результате выполнения команды к-я лента сдвигается на одну ячейку вправо, если? t = 1, то в результате выполнения команды к-я лента остается неподвижной, к&euro- {1,2}.

Для любой конфигурации [qi{i&l существует, причем единственная, команда машины М, выполняющаяся в этой конфигурации. Если в результате выполнения команды машина переходит из конфигурации [ф&^г] в конфигурацию ^щщ], мы будем писать: [</?44²] —> [щЩ/'!?]-Если существует конечная последовательность [gi^i^] — [(ljrhrl2} — [дтТг], то будем говорить, что существует конечное вычисление, переводящее машину м из конфигурации [?"&&] в конфигурацию [дт^г], и писать {qib[дтт2].

Произвольную машину Минского можно рассматривать как граф (см., например, [82]). По этому графу можно построить граф G конфигураций машины. При этом множество всевозможных конфигураций машины М будет образовывать множество вершин графа G, G будет иметь ребро с концами в вершинах [дг^^г] и [gjf/1%] тогда и только тогда, когда [qjmm] или [qfnim] -* fe-66]- Будем писать [gi?i6]<-~* [ijmm], если существует конечный связный подграф G ' графа G такой, что [qiti&j и [q3 t/j г/2] — вершины G '.

Лемма 2. Если для некоторого п имеет место соотношение [gi2n]<~~^ [go 10], то.

Доказательство леммы 2. Допустим, что для некоторого натурального числа п имеет место соотношение [qi2n]<~^> [<7оЮ]. Тогда [gi2n]>—> [golO] или [go10]>—> [gi2″ ], либо выполняется условие: Существует конечная последовательность конфигураций [gaiAfg1A7l], [g"2 А^ АТ2], ., такая, что.

1. [gi2″ 0]>—"[g^A^J или ["i2″ 0],.

2. [golO]>-^ gcti-Vi A7! или qajX^Xf^ [golO],.

3- W] или [""^/S^tJ^^+i^+i^+i] Для любого к 6.

1,2,.,/-1}.

Очевидно, что существование конечного вычисления, при помощи которого машина М переходит из конфигурации [до 10] в конфигурацию [gi2″ 0] невозможно, поскольку по определению машины М [gj2n] — начальная конфигурация, а [доЮ] — заключительная конфигурация.

Рассмотрим теперь случай, когда выполняется условие (*). Заметим, что, вообще говоря, может существовать несколько последовательностей [iai-ViA-yJ, [Ча^/з^ч-А- ¦ ¦ ¦ > [?<*!-Vi ] • Поэтому зафиксируем некоторую последовательность вида [gaiA/3jA7l], [ga2A, g2A72], .,., [qaiXfj, 7,] такую, что число I минимально. Если I = 1, то в силу того, что [gi2n] — начальная конфигурация, [до 10] — заключительная конфигурация, [д12&trade-]>—> [д^А^ А71] и [(/а1Лгз1 А7, ]>—> [доЮ]. Поэтому [?12™]>—> [доЮ], что и требовалось. Следовательно в дальнейшем мы можем полагать, что / > 1. Предположим, что А (д, 1А7!1]>—> [д", А, з, А7, ]. Так как [доЮ] — заключительная конфигурация, [да, Хр1 Л7,]>—> [д0] ()]. Отсюда вытекает, что А71&bdquo-1]>—> [(/оЮ]. Следовательно конфигурацию [да, мы можем исключить из рассмотрения, и вместо последовательности [да1 А) д1А71], [д"2Ад2А72], ., А/з, А7,] мы можем рассматривать последовательность [(/", А (з1 А71], [да2А/з2 А72], ¦••, [?"!! Ад^з^ АТгг], что противоречит нашему предположению о минимальности числа I. Поэтому [д^А^, А7!]>—> [да^А/^ А-у,^]. Заметим, что по определению машины Минского для любых трех конфигураций [дТ1 т2г3], [дТ4т5те], [дТ7г8т9] если [дТ1Т2Тг]^ [д^тцте-] и [(¡-Т1 т-17−3]>—> [дТ7Г8Гд], то одно из этих двух вычислений является начальной частью другого. Так как [до 10] — заключительная конфигурация, очевидно, что конечное вычисление, при помощи которого машина м переходит из конфигурации [да, Ад, А7, ] в конфигурацию [доЮ], не может быть начальной частью вычисления, при помощи которого машина М переходит из конфигурации [.

1. Важенин Ю. М. Критические теории некоторых классов неассоциативных колец // Алгебра и логика. 1989. Т. 28. № 4. С. 393 401.

2. Важенин Ю. М. Проблема равенства в неассоциативных кольцах // Алгебра и логика. 1991. Т. 30. № 1. С. 17−27.

3. Важенин Ю. М. О границах разрешимости многообразий нильпотентных и разрешимых групп //XI Межреспубликанская конференция по математической логике. Тез. сообщ. Казань: КГУ, 1992. С. 32.

4. Важенин Ю. М. Множества, логика, алгоритмы. 3-е изд. Екатеринбург: УрГУ, 1999.

5. Важенин Ю. М., Попов В. Ю. Критические теории многообразий нильпотентных и разрешимых групп // Международная алгебраическая конференция памяти А. Г. Куроша. Тезисы докладов. Москва. 1998. С. 146.

6. Важенин Ю. М., Попов В. Ю. Границы разрешимости многообразий нильпотентных и разрешимых групп // Алгебра и логика. 2000. Т. 39. № 2. С. 127 133.

7. Важенин Ю. М., Попов В. Ю. Критические теории свободных нильпотентных колец некоторых типов // Изв. вузов. Математика. 1991. № 3. С. 74 76.

8. Важенин Ю. М., Попов В. Ю. Границы разрешимости псевдомногообразий конечных полугрупп, групп и колец // Третья международная конференция по алгебре памяти М. И. Каргаполова, Красноярск, август 1993 г.: Сборник тезисов. Красноярск, 1993. С. 61.

9. Важенин Ю. М., Попов В. Ю., Шибаков А. Ю. Критические Теории свободных нильпотентных колец и кольца целых чисел с делимостью //I Международная конференция по алгебре: Тезисы докладов по теории колец, алгебр и модулей. Новосибирск, 1989. С. 28.

10. Важенин Ю. М., Розенблат Б. В. Разрешимость позитивной теории свободной счетно-¦ порожденной полугруппы // Матем. сб. 1981. Т. 116(158). № 1. С. 120 127.

11. Важенин Ю. М., Розенблат Б. В. О позитивных теориях свободных алгебраических систем // Известия вузов. Математика. 1983. № 3. С. 70 73.

12. Волков М. В. Многообразия полугрупп с модулярной решеткой подмногообразий // Докл. РАН. 1992. Т. 326. № 3. С. 409 413.

13. Горбунов В. А. Покрытия в решетках квазимногообразий и независимая аксиоматизируемость // Алгебра и логика. 1977. Т. 16. № 5. С. 340 369.

14. Горбунов В. А. Квазитождества двухэлементных алгебр // Алгебра и логика. 1983. Т. 22. № 2. С. 121 127.

15. Горбунов В. А. Алгебраическая теория квазимногообразий. Новосибирск. Научная книга. 1999.

16. Гуревич Ю. Ш. Проблема равенства слов для некоторых классов полугрупп // Алгебра и логика. 1966. Т. 5, № 5. С. 25 35.

17. Дрёнски В. С. О тождествах в алгебрах Ли // Алгебра и логика. 1974. Т. 13. № 3. С. 265 290.

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

19. Дурнев В. Г. О позитивных формулах на свободных полугруппах- // Сибирский математический журнал. 1974. Т. 15. № 5. С. 1131 1137.

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

21. Ершов Ю. Л. Проблемы разрешимости и конструктивные модели. М.: Наука, 1980.

22. Ершов Ю. Л., Лавров И. А., Тайманов А. Д., Тайцлин М. А. Элементарные теории // Успехи мат. наук. 1965. Т. 20. № 5. С. 37 108.

23. Жевлаков К. А., Слинько А. М., Шёстаков И. П., Ширшов А. И. Кольца, близкие к ассоциативным. М.: Наука, 1978.

24. Жуков А. И. Приведенные системы определяющих соотношений в неассоциативных алгебрах // Матем. сб. 1950. Т. 27. № 2. С. 267 280.

25. Замятин А. П. Предмногообразия полугрупп, элементарная теория которых разрешима // Алгебра и логика. 1973. Т. 12. № 4. С. 417 432.

26. Замятин А. П. Неабелево многообразие групп имеет неразрешимую элементарную теорию // Алгебра и логика. 1978. Т. 17. № 1. С. 20 27.

27. Замятин А. П. Предмногообразия ассоциативных колец, элементарная теория которых разрешима // Сиб. матем. журн. 1978. Т. 19. № 6. С. 1266 1282.

28. Замятин А. П. Разрешимость элементарных теорий некоторых многообразий колец // Алгебраические системы. Многообразия. Решетки подсистем. УРГУ, Свердловск, 1983. С. 52 74.

29. Зимин А. И. Блокирующие множества термов // Матем. сб. 1982. Т. 119. С. 363 375.

30. Кацман С. И., Репницкий В. Б. Коммутативные полугруппы, решетка подполугрупп которых удовлетворяет нетривиальному тождеству // Матем. сборник. 1988. Т. 137(179). № 4. С. 462 482.

31. Кейслер Г., Чэн Ч. Ч. Теория моделей. М.:Мир, 1977.

32. Кемер А. Р. Конечные базисы тождеств ассоциативных алгебр // Алгебра и логика. 1987. Т. 26. С. 597 641.

33. Клейман Е. И. О базисах тождеств многообразий инверсных полугрупп // Сиб. матем. журн. 1979. Т. 20. № 4. С. 760 777.

34. Клейман Е. И. Об условии покрытия в решетке многообразий инверсных полугрупп // Исследов. алгебраическ. систем по свойствам их подсистем. Свердловск, 1980. С. 76 -91.

35. Клейман Ю. Г. Тождества и некоторые алгоритмические проблемы в группах // ДАН СССР. 1979. Т. 244. № 4. С. 814 818.

36. Клейман Ю. Г. О тождествах в группах // Труды ММО. 1982. Т. 44. С. 62 108.

37. Клейман Ю. Г. О некоторых вопросах теории многообразий групп // Изв. АН СССР. Сер. матем. 1983. Т. 47. № 1. С. 37 74.

38. Кострикин А. И. Вокруг Бернсайда. М.: Наука, 1986.

39. Коуровская тетрадь, 7-е изд. Новосибирск, 1980. Вопрос 3.4.а. С. 35.

40. Коуровская тетрадь, 10-е изд. Новосибирск, 1986.

41. Маканин Г. С. Проблема разрешимости уравнений в свободной полугруппе // Матем. сб. 1978. Т. 103(145). № 2. С. 147 237.

42. Мальцев А. И. Алгоритмы и рекурсивные функции. М.:Наука, 1965.

43. Мальцев А. И. О некоторых пограничных вопросах алгебры и математической логики // Межд. конгресс математиков. Москва, 1966. С. 217 231.

44. Мальцев А. И. Тождественные соотношения на многообразиях квазигрупп // Матем. сб. 1966. Т. 69. № 1. С. 3 12.

45. Мальцев А. И. Алгебраические системы. М.:Наука, 1970.

46. Марков А. А. Невозможность некоторых алгорифмов в теории ассоциативных систем // Докл. АН СССР. 1947. Т. 55. № 7. С. 587 590.

47. Марков А. А. Невозможность некоторых алгорифмов в теории ассоциативных систем. II // Докл. АН СССР. 1947. Т. 58. № 3. С. 353 356.

48. Марков А. А. Невозможность некоторых алгорифмов в теории ассоциативных систем // Докл. АН СССР. 1951. Т. 77. № 1. С. 19 20.

49. Марков А. А. Теория алгорифмов // Тр. Мат. ин-та АН СССР. 1954. Т. 42. С. 1 376.

50. Марков А. А., Нагорный Н. М. Теория алгорифмов. М.: Наука, 1984.

51. Мартынова Т. А. Группоид 0-приведенных многообразий полугрупп // Исследов. по современ. алгебре. Свердловск. 1979. С. 96 115.

52. Матиясевич Ю. В. Диофантовость перечислимых множеств // ДАН СССР. 1970. Т. 191. № 2. С. 279 282.

53. Матиясевич Ю. В. Об исследованиях по некоторым алгоритмическим проблемам алгебры и теории чисел // Тр. Матем. ин-та АН СССР им. В. А. Стеклова. 1984. Т. 168. С. 218 235.

54. Медведев Ю. А. Пример многообразия разрешимых альтернативных алгебр над полем характеристики 2, не имеющего конечного базиса тождеств // Алгебра и логика. 1980. Т. 19. № 3. С. 300 313.

55. Мельничук И. Л., Сапир М. В., Харлампович О. Г. Проблема равенства в многообразиях полугрупп, колец и алгебр Ли // Сибирский математический журнал. 1986. Т. 27. № 6. С. 144 156.

56. Мурский В. Л. Несколько примеров многообразий полугрупп // Матем. заметки. 1968. Т. 3. № 6. С. 663 670.

57. Мурский В. Л. Нераспознаваемые свойства конечных систем тождественных соотношений // ДАН СССР. 1971. Т. 196. № 3. С. 520 522.

58. Носков Г. А., Ремесленников В. Н., Романьков В. А. Бесконечные группы. Итоги науки и техники. Сер. «АЛГЕБРА. ТОПОЛОГИЯ. ГЕОМЕТРИЯ» Т. 17. Москва. 1979.

59. Ольшанский А. Ю. О проблеме конечного базиса тождеств в группах // Изв. АН СССР. Сер. мат. 1970. Т. 34. № 2. С. 376 384.

60. Ольшанский А. Ю. О некоторых бесконечных системах тождеств // Тр. сам. Петровского. 1978. Т. 3. С. 139 146.

61. Павлоцкая Л. М. Разрешимость проблемы остановки для некоторых классов машин Тьюринга // Матем. заметки. 1973. Т. 13. № 6. С. 899 909.

62. Пинус А. Г. Конгруэнц-дистрибутивные многообразия алгебр. Итоги науки и техники. Сер. «АЛГЕБРА. ТОПОЛОГИЯ. ГЕОМЕТРИЯ» Т. 26. Москва. 1988.

63. Полин С. В. О тождествах конечных алгебр // Сиб. матем. журн. 1976. Т. 17. № 6. С. 1356 1366.

64. Попов В. Ю. О критических теориях над-коммутативно-ассоциативных многообразий колец // Одиннадцатая межреспубликанская конференция по математической логике, Казань, октябрь 1992 г.: Тезисы сообщений. Казань, 1992. С. 87.

65. Попов В. Ю. Критические теории многообразий нильпотентных колец // Сибирский математический журнал. 1997. № 1. С. 82 91.

66. Ремесленников В. Н., Романьков В. А. Теоретико-модельные и алгоритмические вопросы теории групп. Итоги науки и техники. Сер. «АЛГЕБРА. ТОПОЛОГИЯ. ГЕОМЕТРИЯ» Т. 21. Москва. 1983.

67. Роджерс X. Теория рекурсивных функций и эффективная вычислимость. М.:Мир, 1972.

68. Розенблат Б. В. О позитивных теориях свободных инверсных полугрупп // Сибирский математический журнал. 1979. Т. 20. № 6. С. 1282 1298.

69. Розенблат Б. В. Позитивные теории некоторых многообразий полугрупп // Исслед. по соврем, алгебре. Свердловск, 1981. С. 117 132.

70. Розенблат Б. В. Перестановочные многообразия полугрупп // XVII Всесоюзн. алгебраическая конф., 2 часть: Тезисы докл. Минский государственный университет, Минск, 1983. С. 195 196.

71. Романьков В. А. О неразрешимости проблемы эндоморфной сводимости в свободных нильпотентных группах и свободных кольцах // Алгебра и логика. 1977. Т. 16. № 4. С. 457 471.

72. Романьков В. А. Об уравнениях в свободных метабелевых группах // Сиб. матем. журн. 1979. Т. 20. № 3. С. 671 673.

73. Романьков В. А. О некоторых алгоритмических вопросах для разрешимых групп // Тезисы 6 симпозиума по теории групп. Киев, 1978. С. 52.

74. Сапир М. В. Малые, кроссовы и предельные многообразия полугрупп// 16 Всесоюзн. алгебраическ. конф. Тезисы докладов. Ч. 2. Ленинград. 1981. С. 142 143.

75. Сапир М. В. Проблемы бернсайдовского типа и тождества конечных полугрупп // 18 Всесоюзная алгебраическая конференция. Тезисы докладов. Кишинев. 1985. Ч. 2. С. 151.

76. Сапир М. В. Алгоритмические проблемы в многообразиях полугрупп // Известия высших учебных заведений. 1985. № 12. С. 71 74.

77. Сапир М. В. Проблемы бернсайдовского типа и конечная базируемость в многообразиях полугрупп // Изв. АН СССР, сер. матем. 1987. Т. 51. № 2. С. 319−340.

78. Сапир М. В. Алгоритмические проблемы в многообразиях полугрупп // Алгебра и логика. 1988. Т. 27. № 4. С. 440 463.

79. Сапир М. В. Минимальное многообразие ассоциативных алгебр с неразрешимой проблемой равенства // Математический сборник. 1989. Т. 180. № 12. С. 1691 1708.

80. Сапир М. В. Ограниченная проблема Бернсайда для многообразий полугрупп // Изв. АН СССР. Сер. мат. 1991. Т. 55. № 3. С. 670 679.

81. Сапир М. В., Харлампович О. Г. Проблема равенства в многообразиях ассоциативных алгебр и алгебр Ли // Известия высших учебных заведений. 1989. № 6. С. 76 84.

82. Свердловская тетрадь. Нерешенные задачи теории полугрупп. Свердловск, 1979.

83. Трахтман А. Н. Многообразие полугрупп без неприводимого базиса тождеств// Матем. заметки. 1977. Т. 21. № 6. С. 865 872.

84. Трахтман А. Н. Шестиэлементная полугруппа, порождающая многообразие с континуумом подмногообразий // Алгебраические системы и их многообразия. Свердловск, 1988. С. 138 143.

85. Умирбаев У. У. Проблема равенства для йордановых и правоальтернативных алгебр // Некоторые проблемы и задачи анализа и алгебры. Новосибирск: Новосибир. ун-т, 1985. С. 120 127.

86. Успенский В. А., Семенов А. Л. Теория алгоритмов: ее основные открытия и приложения. Алгоритмы в соврем, мат. и ее прил. Материалы междунар. симпоз., Ургенч (УзССР), 16 22 сент. 1979. 4.1. Новосибирск, 1982, С. 99 — 372.

87. Фридман А. А. Степени неразрешимости проблемы тождества в конечно определенных группах // Докл. АН СССР. 1962. Т. 147. № 4. С. 805 808.

88. Фридман А. А. Степени неразрешимости проблемы тождества для конечно определенных групп. М.:Наука, 1967.

89. Харлампович О. Г. Проблема равенства в многообразии ZA^A // Известия высших учебных заведений. 1988. № 11. С. 82 84.

90. Харлампович О. Г. Проблема равенства для разрешимых алгебр Ли и групп // Математический сборник. 1989. Т. 180. № 8. С. 1033 1066.

91. Шеврин Л. Н. Полугруппы с некоторыми типами структур подполугрупп // Докл. АН СССР. 1961. Т. 138. № 4. С. 796 798.

92. Шеврин Л. Н. Полугруппы с дедекиндовой структурой подполугрупп // Докл. АН СССР. 1963. Т. 148. № 2. С. 292 295.

93. Шеврин Л. Н., Волков М. В. Тождества полугрупп // Изв. высш. уч. зав. Математика. 1985. № 11. С. 3 47.

94. Ширшов А. И. О специальных J-кольцах // Матем. сб. 1956. Т. 38. № 2. С. 149 166.

95. Баясгалан Б. Критические теории некоторых многообразий полугрупп // Conferense on Algebra. Ulaanbaatar, 1990. Theses of reports. P. 1−2.

96. Belov A. J. Solution of one Maltzev problem //II Международная конференция «Полугруппы: теория и приложения» в честь профессора Е. С. Ляпина: Тезисы докладов. Санкт-Петербург, 2−9 июля 1999 г. С. 9.

97. Попов В. Ю. Critical thiories of varieties of nilpotent rings // Тезисы докладов алгебраической конференции. Нижний Новгород. 1995. С. 91.

98. Холл М. Теория групп. М.: ИЛ, 1982.

99. Addison J. W. One some points of the theory of recursive functions. Dissertation, Univ. Wisconsin, 1954.

100. Albert D., Baldinger R., Rhodes J. Undecidability of the identity problem for finite semigroups // J. Symbolic Logic. 1992. V. 57. № 1. P. 179 192.

101. Austin A. K. A closed set of laws which is not generated by a finite set of laws //Quart. J. Math. 1966. V. 17. № 65. P. 11 13.

102. Baker K. A. Finite equational bases for algebras in a congruence-distributive equational class // Adv. Math. 1977. V. 24. № 3. P. 207 243.

103. Bean D. R., Ehrenfeucht A., McNulty G. Avoidable patterns in strings of simbols // Pacific J. Math. 1979. V. 85 P. 261 294.

104. Boone W. W. Word problems and recursively enumerable degrees of unsolvability. A first paper on Thue systems // Ann. Math. 1966. V. 83. № 3. P. 520 571.

105. Boone W. W., Rogers H., Jr. On a problem of J.H.C.Whitehead and a problem of Alonzo Church // Math. Scand. 1969. V. 19. № 2. P. 185 192.

106. Burnside W. On an unsettled question in the theory of discontinuous groups // Quart. J. Pure and Appl. Math. 1902, V. 33. P. 230 237.

107. Chin L. H., Tarski A. Distributive and modular laws in the arithmetic of relation algebras. University of California. 1951.

108. Dehn M. Uber unendliche diskontinuierliche Gruppen // Math. Ann. 1911. V. 71. P. 116 -144.130. de Luca A., Varricchio S. On a conjecture of Brown // Semigroup Forum. 1993. V. 46. № 1. P. 116−119.

109. Friedman H. On decidability of equational theories // Journal of pure and applied algebra. 1976. № 7. P. 1 3.

110. Guba V. S. The, word problem for relatively free Burnside semigroup satisfying Tm = Tm+n, with m > 4 or m = 3, n 1 // Internat. J. Algebra Comput. 1993. V. 3. № 2. P. 125 — 140.

111. Guba V. S. The word problem for relatively free semigroup satisfying Tm = Tm+n, m > 3 // Internat. J. Algebra Comput. 1993. V. 3. № 3. P. 335 347.

112. Jacobson N. Structure of rings. AMS: Providence, Rhode Island, 1956.

113. Kargapolov M. I. Some questions in the theory of soluble groups. Lect. Notes Math. 1974. V. 372. P. 389 394.

114. Keisler H. 3. Limit ultraproducts // J. Symb. Logic. 1965. V. 30. P. 212 234.

115. Kharlampovich O. G., Gildenhuys D. Varieties of Lie algebras with solvable word problem // Communications in Algebra. 1993. V. 21. № 10. P. 3571 3609.

116. Kharlampovich O. G., Sapir M. V. Algorithmic problems in varieties // Internat. J. Algebra Comput. 1995. V. 5, № 4 5. P. 379 — 602.

117. Lyndon R. C. Properties preserved under homomorphism // Pacific J. Math. 1959. V. 9. P. 143 154.

118. Lyndon R. C. Properties preserved in subdirect products // Pacific J. Math. 1959. V. 9. P. 155.

119. Los J. On the extending of models, I // Fund. Math. 1955. V. 42. P. 38 54.

120. McKenzie R., Valeriote M. The Structure of Decidable Locally Finite Varieties. Birkhauser, Progress in Mathematics. V. 79.1989.

121. McNulty G. The decision problem for equational bases of algebras // Annals of Mathematical logic. 1976. V. 11. P. 193 259.

122. McNulty G. Undecidable properties of finite sets of equations // The Jornal of Symbolic Logic. 1976. V. 41. № 3. P. 589 604.

123. Mekler A., Nelson E., Shelah S. A variety with solvable, but not uniformly solvable, word problem // Proc. London Math. Soc. (Ser. 3). V. 66. № 2. P. 225 256.

124. Minsky M. L. Recursive unsolvability of Post’s problem of «TAG» and topics in theoty of Turing machines // Ann. Math. 1961. V. 74. P. 437 455.

125. Perkins P. Decision problems for equational theories of semigroups and general algebras // Ph. D. thesis. Univ. of California. Berkeley. Calif. 1966.

126. Perkins P. Unsolvable problems for equational teories // Notre Dame Jornal of Formal Logic. 1967. V. 8. P. 175 185.

127. Perkins P. Bases for equational theories of semigroups //J. Algebra. 1969. V. 11. № 2. P. 298 314.

128. Pollak G. On the consequences of permutation identities // Acta sci. math. 1973. V. 34. P. 323 333.

129. Pollak G. On hereditarily finitely based varieties of semigroups // Acta sci. math. 1975. V. 37. № 3 4. P. 339 — 348.

130. Pollak G. Some lattices of varieties containing elements without cover// Noncommutative structures in algebra and geometric combinatorics. Rome. 1981. P. 91 96.

131. Post E. Recursive unsolvability of a problem of Thue // J. Symbol. Log. 1947. V. 12. № 1. P. 1 11.

132. Quine W. Concatenation as a basis for arithmetic //J. Symb. Log. 1946. V. 11. P. 105 114.

133. Remeslennikov V. N., Romanovskii N. S. Algorithmic problems for solvable groups. Word problems II. Amsterdam New York — Oxford, North Holland, 1980. P. 337 — 346.

134. Repnitskii V. B. On subsemigroup lattices without non-trivial identities //Algebra Universalis. 1994. V. 31. P. 256 265.

135. Sapir M. Weak word problem for finite semigroups //In J. Rhodes, editor, Monoids and semigroups with applications. Proceedings of Berkeley Workshop in Monoids. Berkeley, 1989. P. 206 219.

136. Shepherdson J. C. Machine configuration and word problems of given degrees of unsolvability // Z. math. Log. und Grundl. Math. 1965. V. 11. № 2. P. 149 175.

137. Tarski A. Some metalogical results concerning the calculus of relations //J. Symbolic Logic. 1953. № 18. P. 188 189.

138. Tarski A. Contributions to the theory of models, I, II // Koninkl. Ned. Akad. Wetensch. Proc., Ser. A. 1954. V. 57. P. 572 588.

139. Tarski A., Givant S. A formalization of set theory without variables. AMS. Providence. Rhode Island, 1987.

140. Thue A. Probleme uber Veranderungen von Zeichenreichen nach gegebenen Regeln. Videnskapsselskapets Skrifter. I. Math. Naturwiss. Kl., 1914. 10, 34S.

141. Vaughan-Lee M. R. Uncountably many varieties of groups // Bull. London Math. Soc. 1970. V. 2. № 6. P. 280 286.

142. Vazenin Ju. M. On the elementary theory of free inverse semigroups // Semigroup Forum. 1974. V. 9. № 3. P. 189 195.

143. Volkov M. V. Finite basis theorem for systems of semigroup identities // Semigroup Forum. 1984. V. 28. № 1 3. P. 93 — 99.

144. Wells B. Pseudorecursive varieties and their word problems. Ph.D. thesis. University of California. Berkley, 1982. Работы автора no теме диссертации.

145. Попов В. Ю. Разрешимые теории альтернативных колец // Советско-французский коллоквиум по теории моделей, Караганда, июнь 1990 г.: Тезисы докладов. Караганда, 1990. С. 41.

146. Попов В. Ю. Разрешимые теории йордановых колец // X Всесоюзная конференции по математической логике, Алма-Ата, ноябрь 1990 г.: Тезисы докладов. Алма-Ата, 1990. С. 134.

147. Попов В. Ю. Об эквациональных теориях многообразий метабелевых и коммутативных колец // Вторые математические чтения памяти М. Я. Суслина. Сборник тезисов. Саратов, 1991. С. 91.

148. Попов В. Ю. О рекурсивности эквациональных теорий многообразий колец // Международная конференция по алгебре, посвященная памяти А. И. Ширшова, Барнаул, август 1991 г.: Тезисы докладов. Новосибирск, 1991. С. 113.

149. Попов В. Ю. О проблеме выводимости тождеств для колец // Третья международная конференция по алгебре памяти М. И. Каргаполова, Красноярск, август 1993 г.: Сборник тезисов. Красноярск, 1993. С. 272.

150. Попов В. Ю. Эквациональные теории многообразий метабелевых и коммутативных колец // Алгебра и логика. 1995. Т. 34. № 3. С. 347 361.

151. Попов В. Ю. Критические теории над-ассоциативно-коммутативных многообразий колец // Сиб. математ. журн. 1995. Т. 36. № 6. С. 1364 1374.

152. Попов В. Ю. О разрешимости проблемы равенства в относительно свободных кольцах // Международная алгебраическая конференция памяти Д. К. Фаддеева. Тезисы докладов. Санкт-Петербург, 1997. С. 259 260.

153. Попов В. Ю. О разрешимости эквациональных теорий многообразий колец // Математические заметки. 1998. Т. 63. № 6. С. 873 881.

154. Попов В. Ю. О некоторых алгоритмических свойствах классов полугрупп и колец // Деп. в ВИНИТИ 6.7.99. № 2203-В99. 145с.

155. Попов В. Ю. О некоторых свойствах бесконечных систем тождеств // Деп. в ВИНИТИ 29.10.99. № 3228-В99. 64с.

156. Попов В. Ю. О некоторых алгоритмических свойствах многообразий моноидов // Деп. в ВИНИТИ 29.10.99. № 3232-В99. 98с.

157. Попов В. Ю. О зависимых системах тождеств // Деп. в ВИНИТИ 29.10.99. № 3231-В99. 62с.

158. Попов В. Ю. О некоторых алгоритмических свойствах бесконечных систем тождеств // Деп. в ВИНИТИ 29.10.99. № 3229-В99. 84с.

159. Попов В. Ю. О некоторых алгоритмических свойствах систем полугрупповых тождеств // Деп. в ВИНИТИ 24.11.99. № 3462-В99. 78с.

160. Попов В. Ю. О тождествах полугрупп и колец // Деп. в ВИНИТИ 24.11.99. № 3461-В99. 85с.

161. Попов В. Ю. О многообразиях колец с условием покрытия // Деп. в ВИНИТИ 25.11.99. № 3165-В99. 63с.

162. Попов В. Ю. Об эквациональных теориях многообразий антикоммутативных колец // Математические заметки. 1999. Т. 65. № 2. С. 230 245.

163. Попов В. Ю. Об эквациональных теориях классов конечных колец // Сибирский математический журнал. 1999. Т. 40. № 3. С. 666 675.

164. Попов В. Ю. Об эквациональных теориях классов полугрупп //II Международная конференция «Полугруппы: теория и приложения» в честь профессора Е. С. Ляпина: Тезисы докладов. Санкт-Петербург, 2−9 июля 1999 г. С. 94 95.

165. Попов В. Ю. О проблеме выводимости тождеств в многообразиях колец // Сибирский математический журнал. 1999. Т. 40. № 5. С. 1121 1126.

166. Попов В. Ю. О проблеме распознавания зквациональной рекурсивности // Логика и приложения. Тезисы международной конференции, посвященной 60-летию со дня рождения академика Ю. Л. Ершова. Новосибирск, 4−6 мая 2000 г. ИДМИ, ИМ СО РАН, НГУ. С. 84.

167. Попов В. Ю. О некоторых алгоритмических проблемах, связанных с многообразиями неассоциативных колец // Математические труды. 2000. Т. 3. JV2 2. С. 146 170.

168. Попов В. Ю. Об эквациональных теориях многообразий колец конечной характеристики // Фундаментальная и прикладная математика. 2000. Т. 6. № 4. С. 1193 1203.

169. Попов В. Ю. О связи проблемы равенства и разрешимости эквациональной теории // Сибирский математический журнал. 2000. Т. 41. № 5. С. 1122 1125.

170. Попов В. Ю. Неразрешимость проблемы равенства в относительно свободных кольцах // Математические заметки. 2000. Т. 67. № 4. С. 582 594.

171. Важенин Ю. М., Попов В. Ю. О позитивных и критических теориях некоторых классов колец // Сибирский математический журнал. 2000. Т. 41. № 2. С. 278 283.

172. Попов В. Ю. Об эквациональных теориях многообразий полугрупп // Известия Уральского государственного университета. 2000. N" 18. Математика и механика. Вып. 3. С. 162 175.

173. Попов В. Ю. Об эквациональных теориях классов конечных полугрупп // Алгебра и логика. 2001. Т. 40. № 1. С. 97 116.

174. Попов В. Ю. Критические теории многообразий полугрупп с перестановочным тождеством // Сибирский математический журнал. 2001. Т. 42. № 1. С. 153 155.

175. Попов В. Ю. Многообразие колец, не обладающее независимым базисом // Математические заметки. 2001. Т. 69. № 5. С. 713 732.

176. Попов В. Ю. О проблеме выводимости тождеств в конечных кольцах // Известия высших учебных заведений. Математика. 2001. № 9(472). С. 51 58.

177. Попов В. Ю. О разрешимости эквациональных теорий покрытий многообразий полугрупп // Сибирский математический журнал. 2001. Т. 42. № 6. С. 1361−1374.