Машина Минского, свойства нильпотентности и размерность Гельфанда-Кириллова в конечно-определенных полугруппах тема автореферата и диссертации по математике, 01.01.06 ВАК РФ

На правах рукописи УДК 512.552+512.532

Иванов-Погодаев Илья Анатольевич

Л

МАШИНА МИНСКОГО, СВОЙСТВА НИЛЬПОТЕНТНОСТИ И РАЗМЕРНОСТЬ ГЕЛЬФАНДА-КИРИЛЛОВА В КОНЕЧНО-ОПРЕДЕЛЕННЫХ ПОЛУГРУППАХ

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

АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата физико-математических наук

Москва — 2006

Работа выполнена на кафедре высшей алгебры Механико-математического факультета Московского государственного университета им. М. В. Ломоносова.

«

«

Научные руководители: * доктор физико-математических наук,

профессор А. В. Михалев

доктор физико-математических наук, А. Я. Белов

Официальные оппоненты:, доктор физико-математических'наук,

доцент И. Б. Кожухов

кандидат физико-математических наук, Р. В. Михайлов

Ведущая организация: Тульский государственный

педагогический университет им. Л. Н. Толстого

Защита диссертации состоится 17 ноября 2006 г. в 16 ч. 15 мин. на заседании диссертационного совета Д.501.001.84 в Московском госу- • дарственном университете им. М. В. Ломоносова по адресу: 119992, ГСП-2, Москва, Ленинские горы, МГУ, Механико-математический факультет, аудитория 14-08.

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

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

Общая характеристика работы

Актуальность темы . '

Широко известна бернсайдова проблематика, охватывающая большой круг вопросов, как в теории групп, так и в смежных областях. Проблемам бернсайдовского типа посвящена обзорная статья Е.И.Зельманова.1 В Р/-случае вопросы локальной конечности алгебраических алгебр решаются положительно. В ассоциативном случае соответствующий результат был получен И.Капланским и Д.Левицким. Чисто комбинаторное доказательство для ассоциативного случая получается из теоремы Ширшова о высоте.2 Для PI-алгебр Ли соответствующий результат был получен Е.И.Зельмановым и А.И.КоСтрикиным. Подробная библиография по этому вопросу изложена в монографии А.И.Кострикина?

Первый контрпример к "неограниченной" проблеме был найден ; Е. С. Голодом в 1964 году на основе универсальной конструкции Е. С. Голода- И. Р. Шафаревича. Вопрос о локальной конечности групп с тождеством хп = 1 был решен отрицательно в знаменитых работах П. С. Новикова и С. И. Адяна [1968]: было доказано существование для любого нечетного п ^ 4381 бесконечной группы с т > 1 образующими, удовлетворяющей тождеству хп — 1. Эта оценка была улучшена до п > 665 С. И. Адяном [1975]. Позднее А. Ю. Ольшанский предложил геометрически наглядный вариант доказательства для нечетных п > Ю10. В конечно-определенном случае все подобные вопросы сильно усложняются. В этом направлении работают многие исследователи, и определенного прогресса достигли М. Сапир и И. Рипс.

Построения в группах, как правило, более сложны, чем в полугруппах. Например, вопрос о существовании конечно-порожденной ниль-полугруппы, то есть полугруппы, каждый элемент которой в некоторой степени обращается в нуль, имеет тривиальный положи-

1 Zelmanov Е. On the nilpotency of nilalgebras // Lect. Notes Math., 1988, 1352, 227-240.

2 Ширшов А. И. О некоторых неассоциативных ниль-кольцах и алгебраических алгебрах // Мат. сб., 1957, 41, 3, 381-394. // О кольцах с тождественными соотношениями // Мат. сб., 1957, 43, 2, 277-283.

3 Кострикин А. И. Вокруг Бернсаида. // М.: Наука, 198G, 232.

тельный ответ: уже в алфавите из двух букв имеются слова сколь угодно большой длины, не содержащие трех подряд одинаковых под-слов (кубов). Первая конструкция такого рода принадлежит Туэ [1912]. Однако, если потребовать от полугруппы возможность ее задания конечным числом определяющих соотношений, ситуация сильно усложняется - вопрос о существовании такой полугруппы открыт (см. [Свердловская Тетрадь]).

На проблематику, связанную с построением разного рода экзотических объектов с помощью конечного числа определяющих соотношений обратил внимание В. Н. Латышев. Им же была поставлена проблема существования конечно-определенного ниль-кольца.4

В качестве продвижения в решении этого вопроса можно рассматривать результаты Хигмана, Г. П. Кукина5, В. Я. Беляева6 о вложениях рекурсивно-определенных объектов в конечно-определенные, в частности, известна теорема Хигмана о вложении рекурсивно-определенных групп в конечно-определенные. В этом контексте можно рассматривать результат о существовании конечно-определенной полугруппы, содержащей ненильпотентный ниль-идеал, рассматриваемый в настоящей диссертации.

Хотя до сих пор и не удается построить контрпримеры к проблемам бернсайдовского типа с помощью конечного набора определяющих соотношений, были построены конечно определенные объекты с разного рода "экзотическими" свойствами. В. А. Уфнаровским7 был построен пример конечно-определеной алгебры с промежуточным ростом. Этот пример представляет собой универсальную обертывающую алгебру алгебры Ли со степенным ростом. В данной диссертации приведена конструкция конечно-определенной полугруппы с нецелой размерностью Гельфанда-Кириллова.

Для построения конечно-определенных полугрупп с подобными "экзотическими" свойствами чрезвычайно эффективным оказывает-

4 Днестровская тетрадь: оперативно-информац. сборник — 4-е изд. // Новосибирск: изд. ин-та матем. СО АН СССР, 1993, 73.

5 Ivukin G. P. The variety of all rings has Higman's property // Algebra and Analysis. Irkutsk. 19S9 91-101

6 Belyaev V. Ya. Imbeddability of recursively defined inverse semigroups in finitely presented semigroups // Sibirsk. Math. Journal 25 no. 2., 1984. 50-54.

7 Уфнаровский В. А. О росте алгебр // Вестник МГУ. вып 1, 1978, 4, 59-65.

ся подход, связанный с использованием машины Минского. Машина Минского эквивалентна Машине Тьюринга, но в ее конструкции используется только два регистра. Этим объясняется ее удобство при использовании в алгебраических конечно-определенных системах.

В настоящей диссертации данный подход используется для постороения конечно-определенной полугруппы с размерностью Гельфанда- Кириллова, равной N + а, где а - некоторое рекурсивное число, N — натуральное число, зависящее от а. В процессе построения в полугруппе реализуется машина Минского, вычисляющая соответствующее рекурсивное а. Кроме того, система соотношений определяет канонический вид слова для реализации требуемой размерности Гельфанда- Кириллова.

Построение разного рода конечно определенных экзотических объектов тесно связано с алгоритмической проблематикой. Известно, что проблема равенства в конечно-определенной полугруппе, а следовательно, и алгебре, алгоритмически неразрешима. С другой стороны, эта проблема разрешима, если идеал соотношений задай конечным базисом Грёбнера, замкнутым относительно композиции.8 В этой связи В. Н. Латышев в 1980 году поставил опрос о существовании алгоритма определения, является ли данный элемент делителем нуля или нильпотентом в случае, когда идеал соотношений задан конечным базисом Грёбнера.

Кроме этого, В. Н. Латышевым был поставлен также аналогичный вопрос для мономиальных автоматных алгебр. Для этого случая существование алгоритма проверки, является ли данный элемент нильпотентом, было установлено В. В. Ворисенко, а существование алгоритма для делителей нуля - А. Я. Беловым и В. В. Ворисенко.9 Аналогичный результат для некоторого класса квадратичных алгебр был получен Н. К. Иыуду,10 а также Д. И. Пионтковским.11

8 Bergman G. The diamond lemma for ring theory // Adv. Math., 1978, 29, 2, 178-218.

9 Belov A. J., Borisenko V. V., Latysev V. N. Monomial Algebras // NY. Plenum, 1997.

10 Иыуду H. К. Алгоритмическая разрешимость проблемы распознавания делителей нуля в одном классе алгебр // Фунд. и прикл. матем., 1995, 2, 1, 541-544.

11 Пионтковский Д. И. Базис Грёбнера и когерентность мономиальной ассоциативной алгебры // Фунд. и прикл. матем., 1996, 2, 2, 501-509.

Все эти результаты вытекают из разрешимости системы линейных рекурентов на дереве.12 Из результата работу А. Я. Белова вытекает также существование алгоритма для установления делителей нуля для целого класса алгебр с ограниченой переработкой (аналогичной условию малых сокращений в теории групп.

Пусть на мономах алгебры А с фиксированной системой образующих есть порядок, для которого существует нормальный базис, т.е. базис из мономов, не представимых в виде линейной комбинации меньших. Алгебра А называется алгеброй с ограниченной переработкой справа, если при некотором с? € N для любого нормального слова V/_в алгебре А и любой образующей а* выполняется равенство V/V/ • АуИ^), где А^- € Р для всех э, кроме того, Wj суть

нормальные слова алгебры А, \\Vjl ^ 2(1, а слово IV есть начальный кусок слова IV длины \\У\ — <1.

Если множество слов нормального базиса образует регулярный язык, каждому слову отвечает вершина автомата и все коэффициенты А^- зависят только от типа вершины графа, отвечающего слову IV, то А есть автоматная алгебра с ограниченной переработкой справа

Аналогичным образом определяется (автоматная) алгебра с ограниченной переработкой слева.

Один из основных результатов данной диссертации показывает, что условие ограниченной переработки является необходимым. Мы строим алгебру с алгоритмически неразрешимой проблемой делителей нуля, и идеалом соотношений, заданным конечным базисом Грёбнера. Тем самым дается отрицательный ответ на вопрос, поставленный В. Н. Латышевым.

Построение основано на подходе, связанным с использованием машины Минского. Для этого в полугруппе конструируется машина Минского, реализующая универсальную машину Тьюринга, одна элементарная операция работы которой соответствует умножению слева на выделенную букву. Остановка машины соответствует обнулению слова.

12 Белов А. Я. Линейные рекуррентные уравнения на дереве // Математические заметки, 78, N5, 643-651.

Цель Работы

Данная диссертация посвящена построению примеров конечно-определенных полугрупп и алгебр с особенными свойствами. Большое внимание уделено реализации машины Минского в конечно-определенных системах.

Научная новизна

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

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

[2] Построен пример конечно-определенной полугруппы с рекурсивной размерностью Гельфанда- Кириллова.

[3] Построен пример бесконечной конечно-определенной полугруппы, содержащей ненильпотентный нильидеал.

Основные методы исследования

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

Практическая и теоретическая ценность

Работа носит теоретический характер. Результаты диссертации могут быть полезны при изучении конечно-определенных полугрупп и алгебр.

Апробация результатов

Основные результаты диссертации многократно докладывались на семинаре "Кольца и модули"кафедры высшей алгебры МГУ в 20002006 гг. , а также на следующих конференциях:

Основные результаты диссертации многократно (май 2000 г., май 2001 г., октябрь 2002 г., март, май 2004 г., апрель 2005 г., апрель, сентябрь 2006 г.) докладывались на семинаре "Кольца и модули "кафедры высшей алгебры МГУ, а также на следующих конференциях:

[1] Международная алгебраическая конференция в честь Е. С. Ля-пина, Санкт-Петербург, 1999.

[2] 65-th International Workshop in Algebra (AAA65) and Conference of Young Algebraists (CYA), Potsdam University, 2003.

Публикации

Основные результаты опубликованы в 3 работах, список которых приведен в конце автореферата [1-3].

Структура диссертации

Диссертация состоит из оглавления, введения, пяти глав и списка литературы, который включает 25 наименований.

Краткое содержание работы

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

Пусть А - алгебра над полем К. Фиксируем конечный алфавит образующих {aj,... , а^}. Словоль в ал,гебре называется слово в алфавите образующих. Порядку на образующих отвечает лексикографический порядок на множестве слов.

Слова в алфавите образуют полугруппу. Основной идеей построения является реализация универсальной машины Тьюринга в этой

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

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

Во второй главе рассматривается машина Минского и ее применения для вычислений. Последовательно строятся машины для сложения, умножения, возведения в степень, извлечения корня. В конце строится машина для вычисления рекурсивной степени натурального числа, с округлением в сторону меньшего целого. Данная машина используется в четвертой главе.

В третьей главе строится конечно-определенная полугруппа с нецелой размерностью Гельфанда-Кириллова.

Определение. Пусть S - полугруппа порожденная конечным множеством букв {si,..., sm}.

Пусть Un - множество всевозможных слов т^.-.г^, где ij = 1,... ,m. п = 0,1,2,.... Тогда Un € S и Un состоит из слов длины п. Пусть ди(п) это число неэквивалентных слов в U1 |J U2 U... (J Un.

ди(п) называется функцией роста полугруппы S

Определение. Размерность Гельфанда-Кириллова полугруппы S определяется как

GKdimfg) = limsupflog-<7y(n)) = lim sup —i-^li^l.

n^oo n-*oo logn

Доказывается следующая теорема:

Теорема. Существует конечно-определенная полугруппа с нецелой размерностью Гельфанда- Кириллова.

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

слова и находятся несколько канонических форм. Вводится система комбинаторных инвариантов. После этого подсчитываются функции роста всех возможных форм и находится размерность Гедьфанда-. Кириллова полугруппы. '

В четвертой главе изученная машина Минского, а также приемы построения, рассмотренные в третьей главе, используются для конструирования более сложного объекта: конечно-определенной полугруппы, размерность Гельфанда-Кириллова которой является рекурсивным числом. Таким образом, построение обобщается на вычисляемые с помощью алгоритмов числа.

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

В пятой главе проводится построение конечно-определенной полугруппы, содержащей ненильпотентный ниль-идеал.

Теорема. Существует конечно-определенная полугруппа Я, удовлетворяющая следующим свойствам:

(I) Существует ненильпотентный идеал I = ЬН} где Ь - буква в Я;

(II) Если слово А 6 (7 представляется в виде А — XYYZ1 где X, У, г в С, тогда ЬА = 0.

Благодарности

Автор глубоко благодарен своем научным руководителям — доктору физико-математических наук профессору Алексею Яковлевичу Белову и доктору физико-математических наук Александру Васильевичу Михалеву за постановку задач, обсуждение результатов и постоянное внимание к работе.

Также автор хотел бы поблагодарить за внимание и обсуждения работы доктора физико-математических наук, профессора Виктора Николаевича Латышева, и доктора физико-математических наук, профессора Вячеслава Александровича Артамонова.

Автор выражает свою отдельную благодарность кандидату физико-математических наук Илье Игоревичу Богданову за детальное обсуждение работы.

Работы автора по теме диссертации

[1] Belov A. Ya. Ivanov I. A Construction of Semigroups with Some Exotic Properties, Comm. in Algebra, Том 31, 2, 2003, стр. 673696. В этой работе автору принадлежит часть, посвященная конструкции определяющих соотношений и теорема 1.

[2] И. А. Иванов-Погодаев, "Алгебра с конечным базисом Грёбнера, и неразрешимой проблемой делителей нуля", Фундаментальная и прикладная математика, том 12(4), 2006.

[3] Belov A. Ya. Ivanov I. A Construction of Semigroups with Some Exotic Properties, Acta Appl. Math 85 (2005), no 1-3, 49-56. В этой работе автору принадлежит часть, посвященная механизму передачи сигналов и теорема 1.

Издательство международного института менеджмента ЛИНК 140181, г. Жуковский Московской области, ул. Московская, д. 8/1 http://www.ou-link.ru Подписано в печать 16.10.2006 Формат 60x90 1/16. Тираж 100 экз. Отпечатано в МИМ ЛИНК

Введение

1. Алгебра с конечным базисом Грёбнера, и неразрешимой проблемой делителей нуля.

1.1 План построения алгебры с идеалом соотношений, заданным конечным базисом Грёбнера, в которой вопрос, является ли элемент делителем нуля, алгоритмически неразрешим

1.2 Универсальная машина Тьюринга и определяющие соотношения

1.3 Делители нуля и остановка машины.

2. Вспомогательные сведения о машине Минского.

3. Реализация Машины Минского в конечно-определенной полугруппе

3.1 План построения полугруппы с полуцелой размерностью Гельфанда- Кириллова.

3.2 Определяющие соотношения.

3.3 Приведение к каноническому виду.

3.4 Работа основного механизма.

3.5 Система инвариантов.

3.6 Преобразование для увеличения количества нормальных слов.

4. Построение полугруппы с рекурсивной размерностью Гельфанда

Кириллова

4.1 План построения полугруппы с рекурсивной размерностью Гельфандаг Кириллова.

4.2 Определяющие соотношения.

4.3 Приведение к каноническому виду.

4.4 Система инвариантов.

4.5 Присоединение.

4.6 Создание машины Минского в полугруппе

5. Конструкция конечно-определенной полугруппы, содержащей пенильпотентный ниль-идеал.

Широко известна бернсайдова проблематика, охватывающая большой круг вопросов, как в теории групп, так и в смежных областях. Проблемам бернсайдовского типа посвящена обзорная статья Е.И.Зельманова [20]. В PI-случае вопросы локальной конечности алгебраических алгебр решаются положительно. В ассоциативном случае соответствующий результат был получен И.Капланским и Д.Левицким. Чисто комбинаторное доказательство для ассоциативного случая получается из теоремы Ширшова о высоте [21], [22]. Для PI-алгебр Ли соответствующий результат был получен Е.И.Зельмановым и А.И.Кострикиным. Подробная библиография по этому вопросу изложена в монографии [24].

Первый контрпример к "неограниченной" проблеме был найден Е. С. Голодом в 1964 году на основе универсальной конструкции Е. С. Голода- И. Р. Шафаревича. Вопрос о локальной конечности групп с тождеством хп = 1 был решен отрицательно в знаменитых работах П. С. Новикова и С. И. Адяна [1968]: было доказано существование для любого нечетного п ^ 4381 бесконечной группы с т > 1 образующими, удовлетворяющей тождеству хп — 1. Эта оценка была улучшена до п ^ 665 С. И. Адяном [1975]. Позднее А. Ю. Ольшанский предложил геометрически наглядный вариант доказательства для нечетных п > Ю10. В конечно-определенном случае все подобные вопросы сильно усложняются. В этом направлении работают многие исследователи, и определенного прогресса достигли М. Сапир и И. Рипс.

Построения в группах, как правило, более сложны, чем в полугруппах. Например, вопрос о существовании конечно-порожденной ниль-полугруппы, то есть полугруппы, каждый элемент которой в некоторой степени обращается в нуль, имеет тривиальный положительный ответ: уже в алфавите из двух букв имеются слова сколь угодно большой длины, не содержащие трех подряд одинаковых подслов (кубов). Первая конструкция такого рода принадлежит Туэ [1912]. Однако, если потребовать от полугруппы возможность ее задания конечным числом определяющих соотношений, ситуация сильно усложняется - вопрос о существовании такой полугруппы открыт (см. [Свердловская Тетрадь]).

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

В качестве продвижения в решении этого вопроса можно рассматривать результаты Хигмана, Г. П. Кукина, В. Я. Беляева о вложениях рекурсивно-определенных объектов в конечно-определенные. [7], [9], в частности, теорема Хигмана о вложении рекурсивно-определенных групп в конечно-определенные. В этом контексте можно рассматривать результат о существовании конечно-определенной полугруппы, содержащей ненильпотентный ниль-идеал, рассматриваемый в настоящей диссертации.

Хотя до сих пор и не удается построить контрпримеры к проблемам Бернсайдовского типа с помощью конечного набора определяющих соотношений, были построены конечно определенные объекты с разного рода "экзотическими" свойствами. В. А. Уфнаровским был построен пример конечно-определеной алгебры с промежуточным ростом [3]. Этот пример представляет собой универсальную обертывающую алгебру алгебры Ли со степенным ростом. В данной диссертации приведена конструкция конечно определенной полугруппы с нецелой размерностью Гельфанда-Кириллова.

Для построения конечно-определенных полугрупп с подобными "экзотическими" свойствами чрезвычайно эффективным оказывается подход, связанный с использованием машины Минского. Машина Минского эквивалентна Машине Тыоринга, но в ее конструкции используется только два регистра. Этим объясняется ее удобство при использовании в алгебраических конечно-определенных системах.

В настоящей диссертации данный подход используется для посторое-ния конечно-определенной полугруппы с размерностью Гельфанда- Кириллова, равной N + а, где а - некоторое рекурсивное число, N - натуральное число, зависящее от а. В процессе построения в полугруппе реализуется машина Минского, вычисляющая соответствующее рекурсивное а. Кроме того, система соотношений определяет канонический вид слова для реализации требуемой размерности Гельфанда- Кириллова.

Построение разного рода конечно определенных экзотических объектов тесно связано с алгоритмической проблематикой. Известно, что проблема равенства в конечно-определенной полугруппе, а следовательно, и алгебре, алгоритмически неразрешима. С другой стороны, эта проблема разрешима, если идеал соотношений задан конечным базисом Грёбнера, замкнутым относительно композиции [12]. В этой связи В. Н. Латышев в 1980 году поставил опрос о существовании алгоритма определения, является ли данный элемент делителем нуля или нильпотентом в случае, когда идеал соотношений задан конечным базисом Грёбнера.

Кроме этого, В. Н. Латышевым был поставлен также аналогичный вопрос для мономиальных автоматных алгебр. Для этого случая существование алгоритма проверки, является ли данный элемент нильпотентом, было установлено В. В. Борисенко, а существование алгоритма для делителей нуля - А. Я. Беловым и В. В. Борисенко [2]. Аналогичный результат для некоторого класса квадратичных алгебр был получен Н. К. Иы-уду [13], [14] а также Д. И. Пиоитковским [15]. Все эти результаты вытекают из разрешимости системы линейных рекурентов на дереве [17]. Из результата работы [17] вытекает также существование алгоритма для установления делителей нуля для целого класса алгебр с ограпичепой переработкой (аналогичной условию малых сокращений в теории групп.

Определение 0.0.1. Пусть на мономах алгебры А с фиксированной системой образующих есть порядок, для которого существует нормальный базис, т.е. базис из мономов, не представимых в виде линейной комбинации меньших. Алгебра А называется алгеброй с ограниченной переработкой справа, если при некотором d Е N для любого нормального слова W в алгебре А и любой образующей щ выполняется равенство

Wat = W- (£ (0.1) 3 где Aj Е F для всех j, кроме того, WWj суть нормальные слова алгебры A, \Wj\ ^ 2d, а слово W есть начальный кусок слова W длины \W\ — d.

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

Аналогичным образом определяется (автоматная) алгебра с ограниченной переработкой слева.

Один из основных результатов данной диссертации показывает, что условие ограниченной переработки является необходимым. Мы строим алгебру с алгоритмически неразрешимой проблемой делителей нуля, и идеалом соотношений, заданным конечным базисом Грёбнера. Тем самым дается отрицательный ответ на вопрос, поставленный В. Н .Латышевым.

Построение основано на подходе, связанным с использованием машины Минского. Для этого в полугруппе конструируется машина Минского, реализующая универсальную машину Тыоринга, одна элементарная операция работы которой соответствует умножению слева на выделенную букву. Остановка машины соответствует обнулению слова.

Таким образом, основные результаты диссертации таковы:

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

2. Построен пример конечно-определенной полугруппы с рекурсивной размерностью Гельфанда- Кириллова.

3. Построен пример бесконечной конечно-определенной полугруппы, содержащей ненильпотентный нильидеал.

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

Практическая и теоретическая ценность. Работа носит теоретический характер.

Апробация работы. Основные результаты диссертации многократно докладывались на семинаре "Кольца и модули"кафедры высшей алгебры МГУ в 2000-2006 гг. , а также на следующих конференциях:

1. Международная алгебраическая конференция в честь Е. С. Ляпина, Санкт-Петербург, 1999.

2. 65-th International Workshop in Algebra (AAA65) and Conference of Young Algebraists (CYA), Potsdam University, 2003.

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

Отдельная часть результатов опубликована в статье [11], автору принадлежит часть, относящаяся к введению определяющих соотношений.

Основные результаты также опубликованы в сборниках тезисов докладов на международных конференциях (см. [??]).

Структура диссертации. Диссертация состоит из оглавления, введения, пяти глав и списка литературы, который включает 25 наименований.

Благодарности. Автор глубоко благодарен своем научным руководителям — доктору физико-математических наук профессору Алексею Яковлевичу Белову и доктору физико-математических наук Александру Васильевичу Михалеву за постановку задач, обсуждение результатов и постоянное внимание к работе.

Также автор хотел бы поблагодарить за внимание и обсуждения работы доктора физико-математических наук, профессора Латышева Виктора Николаевича, и доктора физико-математических наук, профессора Артамонова Вячеслава Александровича.

Автор выражает свою отдельную благодарность кандидату физико-математических наук Богданову Илье Игоревичу за детальное обсуждение работы.

1. Krause G. R., Lenagan Т. H. Growth of algebras and Gelfand-Kirillov dimension. London; Pitman Adv. Publ. Program, 1985, 182.

2. Belov A. J., Borisenko V. V., Latysev V. N. Monomial Algebras. NY. Plenum, 1997.

3. Уфнаровский В. А. О росте алгебр. Вестник МГУ. вып 1, 1978, 4, 59-65.

4. Gelfand I. М., Kirillov A. A. Sur les corps lies aux algebras enveloppantes des algebras de Lie. Pubis, math. Inst, hautes etud. sci., 1966, 31, 509523.

5. Sapir M. V. Algorithmic Problems for Amalgams of Finite Semigroups.

6. Latyshev V. On the recognizable properties of associative algebras. Special vol. J.S.C.: On computational aspects of commutative algebras. London: Acad. Press, 1988, 237-254.

7. Kukin G. P. The variety of all rings has Higman's property. Algebra and Analysis. Irkutsk. 1989 91-101

8. Bokut L. A., Kukin G. P. Algoritmic and combinatorial aldebra. Math, and its appl. 233.

9. Belyaev V. Ya. Imbeddability of recursively defined inverse semigroups in finitely presented semigroups. Sibirsk. Math. Journal 25 no. 2., 1984. 50-54.

10. Belov A. Ya. Ivanov I. A Construction of Semigroups with Some Exotic Properties, Comm. in Algebra, Volume 31, Number 2, 2003. 673-696.

11. Belov A. Ya. Ivanov I. A Construction of Semigroups with Some Exotic Properties, Acta Appl. Math 85 (2005), no 1-3, 49-56.

12. Bergman G. The diamond lemma for ring theory. Adv. Math., 1978, 29, 2, 178-218.

13. Иыуду Н. К. Алгоритмическая разрешимость проблемы распознавания делителей нуля в одном классе алгебр. Фунд. и прикл. матем., 1995, 2, 1, 541-544.

14. Иыуду Н. К. Стандартные базисы и распознаваемость свойств алгебр, заданных копредставлением. Дисс. на соиск. уч. ст. канд. физ. мат. наук — Москва, 1996, 73.

15. Пионтковский Д. И. Базис Грёбнера и когерентность мономиальной ассоциативной алгебры. Фунд. и прикл. матем., 1996, 2, 2, 501-509.

16. Пионтковский Д. И. Некоммутативные базисы Гребнера, когерентность ассоциативных алгебр и делимость в полугруппах. Фунд. и прикл. матем.,2001, 7, 2, 495-513.

17. Белов А. Я. Линейные рекуррентные уравнения на дереве. Математические заметки, 78, N5, 643-651.

18. Уфнаровский В. А. Комбинаторные и асимптотические методы в алгебре. Итоги науки и техн. Сер. Соврем, пробл. мат. Фундам. направления. М.: ВИНИТИ, 1990, 57, 5-177.

19. И. А. Иванов-Погодаев, "Алгебра с конечным базисом Грёбнера, и неразрешимой проблемой делителей нуля", Фундаментальная и прикладная математика, том 12(4), 2006.С.55-65

20. Zelmanov Е. On the nilpotency of nilalgebras. Lect. Notes Math., 1988, 1352, 227-240. РЖМат, 1989, 7A188)

21. Ширшов А. И. О некоторых неассоциативных ниль-кольцах и алгебраических алгебрах. Мат. сб., 1957, 41, 3, 381-394. (РЖМат, 1958, 164)

22. Ширшов А. И. О кольцах с тождественными соотношениями. Мат. сб., 1957, 43, 2, 277-283. РЖМат, 1958, 7544)

23. Днестровская тетрадь: оперативио-информац. сборник — 4-е изд. — Новосибирск: изд. ин-та матем. СО АН СССР, 1993, 73.

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