Оглавление
Введение ...................................................... 4
1. Алгебра с конечным базисом Грёбисра, и неразрешимой проблемой делителей нуля ............................................ 9
1.1 Илам построения алгебры с идеалом соотношений, задан-
ным конечным базисом Грёбпера, в которой вопрос, является ли элемент делителем нуля, алгоритмически неразрешим ...................................................... 9
1.2 Универсальная машина Тыориш'а и определяющие соотношения ...................................................... 12
1.3 Делители нуля и остановка машины......................... 14
2. Вспомогательные сведения о машине Минского.....................26
3. Реализация Машины Минского в конечно-определенной полугруппе ........................................................35
3.1 План построения полугруппы с полуцелой размерностью
Гельфанда- Кириллова..................................... 35
3.2 Определяющие соотношения................................. 36
3.3 Приведение к каноническому виду......................... 38
3.4 Работа основного механизма............................... 43
3.5 Система инвариантов...................................... 46
3.6 Преобразование для увеличения количества нормальных
слов..................................................... 51
4. Построение полугруппы с рекурсивной размерностью Гельфанда-
Кириллова .....................................................52
4.1 План построения полугруппы с рекурсивной размерностью
Гсльфаида-Кириллова...................................... 52
4.2 Определяющие соотношения................................. 54
4.3 Приведение к каноническому виду........................ 55
4.4 Система инвариантов...................................... 60
_____________________________Оглавление_______________________________3
4.5 Присоединение................................................ 63
4.6 Создание машины Минского в полугруппе ....................... 65
5. Конструкция конечно-определенной полугруппы, содержащей пениль потентный ниль-идеал..........................................69
Библиография......................................................76
ВВЕДЕНИЕ
Широко известна бернсайдова проблематика, охватывающая большой круг вопросов, как в теории групп, так и в смежных областях. Проблемам берисайдовского типа посвящена обзорная статья Е.И.Зельмаиова [20]. В Р1-случае вопросы локальной конечности алгебраических алгебр решаются положительно. В ассоциативном случае соответствующий результат был получен И.Капланским и Д.Левицким. Чисто комбинаторное доказательство для ассоциативного случая получается из теоремы Ширшова о высоте [21]. [22]. Для Р1-алгебр Ли соответствующий результат был получен Е.И.Зельмаиовым и А.И.Кострикиным. Подробная библиография по этому вопросу изложена, в монографии [24].
Первый контрпример к “неограниченной” проблеме был найден Е. С. Голодом в 1964 году на основе универсальной конструкции Е. С. Голода- И. Р. Шафаревича. Вопрос о локальной конечности групп с тождеством хп = 1 был решен отрицательно в знаменитых работах П. С. Новикова и С. И. Адяна [1968]: было доказано существование для любого нечетного п ^ 4381 бесконечной группы с т > 1 образующими, удовлетворяющей тождеству хп = 1. Эта оценка была улучшена до п ^ 665 С. И. Адяном [1975]. Позднее А. Ю. Ольшанский предложил геометрически наглядный вариант доказательства для нечетных п > Ю10. В конечно-определенном случае все подобные вопросы сильно усложняются. В этом направлении работают многие исследователи, и определенного прогресса достигли М. Сапир и И. Рипс.
Построения в группах, как правило, более сложны, чем в полугруппах. Например, вопрос о существовании конечно-порожденной ниль-полугруппы, 'го есть полугруппы, каждый элемент которой в некоторой степени обращается в нуль, имеет тривиальный положительный ответ: уже в алфавите из двух букв имеются слова сколь угодно большой длины, не содержащие трех подряд одинаковых подолов (кубов). Первая конструкция такого рода принадлежит Туэ [1912]. Однако, если потребовать от полугруппы возможность ее задания конечным числом определяющих соотношений, ситуация сильно усложняется - вопрос о суще-
Введение
5
ствовании такой полугруппы открыт (см. [Свердловская Тетрадь]).
На проблематику, связанную с построением разного рода экзотических объектов с помощью конечного числа определяющих соотношений обратил внимание В. Н. Латышев. Им же была поставлена проблема существования конечно определенного ниль-кольца [23].
В качестве продвижения в решении этого вопроса можно рассматривать результаты Хигмана, Г. П. Кукина, В. Я. Беляева о вложениях рекурсивно-определенных объектов в конечно-определенные. [7],
[9], в частности, теорема Хигмана о вложении рекурсивно-определенных групп в конечно-определенные. В этом контексте можно рассматривать результат о существовании конечно-определенной полугруппы, содержащей ненилыютентиый ииль-идеал, рассматриваемый в настоящей диссертации.
Хотя до сих пор и не удается построить контрпримеры к проблемам Бернсайдовского типа с помощью конечного набора определяющих соотношений, были построены конечно определенные объекты с разного рода “экзотическими''’ свойствами. В. А. Уфиаровским был построен пример коисчно-определсной алгебры с промежуточным ростом [3]. Этот пример представляет собой универсальную обертывающую алгебру алгебры Ли со степенным ростом. В дайной диссертации приведена конструкция конечно определенной полугруппы с нецелой размерностью Гельфанда-Кириллова.
Для построения конечно-определенных полугрупп с подобными “экзотическими” свойствами чрезвычайно эффективным оказывается подход, связанный с использованием машины Минского. Машина Минского эквивалентна Машине Тьюринга, но в ее конструкции используется только два регистра. Этим объясняется ее удобство при использовании в алгебраических конечно-определенных системах.
В настоящей диссертации данный подход используется для посторое-ния конечно-определенной полугруппы с размерностью Гельфанда- Кириллова, равной N + от, іде а - некоторое рекурсивное число, N - натуральное число, зависящее от а. В процессе построения в полугруппе реализуется машина Минского, вычисляющая соответствующее рекурсивное а. Кроме того, система соотношений определяет канонический вид слова для реализации требуемой размерности Гельфанда- Кириллова.
Построение разного рода конечно определенных экзотических объектов тесно связано с алгоритмической проблематикой. Известно, что про-
Введение
6
блема равенства в конечно-определенной полугруппе, а следовательно, и алгебре, алгоритмически неразрешима. С другой стороны, эта проблема разрешима, если идеал соотношении задан конечным базисом Грёбнера, замкнутым относительно композиции [12]. В этой связи В. Н. Латышев в 1980 году поставил опрос о существовании алгоритма определения, является ли данный элемент делителем нуля или нильпотентом в случае, когда идеал соотношений задан конечным базисом Грёбнера.
Кроме этого, В. Н. Латышевым был поставлен также аналогичный вопрос для мономиальных автоматных алгебр. Для этого случая существование алгоритма проверки, является ли данный элемент нильпотентом, было установлено В. В. Борисенко, а существование алгоритма для делителей нуля - А. Я. Беловым и В. В. Борисенко |2). Аналогичный результат для некоторого класса квадратичных алгебр был получен II. К. Иы-уду [13], [14] а также Д. И. Пиоитковским [15]. Все эти результаты вытекают из разрешимости системы линейных рекуреитов на дереве [17]. Из результата работы [17] вытекает также существование алгоритма для установления делителей нуля для целого класса алгебр с ограничений переработкой (аналогичной условию малых сокращений в теории групп.
Определение 0.0.1. Пусть на мономах алгебры А с фиксированной системой образующих есть порядок, для которого существует нормальный базис, т.е. базис из мономов, не представимых в виде линейной комбинации меньших. Алгебра .4 называется алгеброй с ограниченной переработкой справа, если при некотором de N для любого нормального слова W в алгебре А и любой образующей сц выполняется равенство
Wal = W-(YJ (0.1)
3
где Аj е F для всех j, кроме того, WWj суть нормальные слова алгебры А, \Wj\ ^ 2d, а слово W есть начальный кусок слова W длины \W\ - d.
Если множество слов нормального базиса образует регулярный язык, каждому слову отвечает вершина автомата и все коэффициенты А^ зависят только от типа вершины графа, отвечающего слову W, то /1 есть автоматная алгебра с ограниченной переработкой справа.
Аналогичным образом определяется (автоматная) алгебра с ограниченной переработкой слева.
Один из основных результатов данной диссертации показывает, что условие ограниченной переработки является необходимым. Мы стро-
- Киев+380960830922