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

• Автор: Иванов-Погодаев, Илья Анатольевич
• Шифр специальности: 01.01.06
• Научная степень: Кандидатская
• Год защиты: 2006
• Место защиты: Москва
• Количество страниц: 77 с. : ил.

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]. В Р1-случае вопросы локальной конечности алгебраических алгебр решаются положительно. В ассоциативном случае соответствующий результат был получен И.Капланским и Д.Левицким. Чисто комбинаторное доказательство для ассоциативного случая получается из теоремы Ширшова о высоте [21], [22]. Для Р1-алгебр Ли соответствующий результат был получен Е.И.Зельмановым и А.И.Кострикиным. Подробная библиография по этому вопросу изложена в монографии [24].
Первый контрпример к “неограниченной” проблеме был найден Е. С. Голодом в 1964 году на основе универсальной конструкции Е. С. Голода- И. Р. Шафаревича. Вопрос о локальной конечности групп с тождеством хп = 1 был решен отрицательно в знаменитых работах П. С. Новикова и С. И. Адяна [1968]: было доказано существование для любого нечетного п ^ 4381 бесконечной группы с т > 1 образующими, удовлетворяющей тождеству хп = 1. Эта оценка была улучшена до п ^ 665 С. И. Адяном [1975]. Позднее А. Ю. Ольшанский предложил геометрически наглядный вариант доказательства для нечетных п > Ю10. В конечно-определенном случае все подобные вопросы сильно усложняются. В этом направлении работают многие исследователи, и определенного прогресса достигли М. Сапир и И. Рипс.
Построения в группах, как правило, более сложны, чем в полугруппах. Например, вопрос о существовании конечно-порожденной ниль-полугруппы, то есть полугруппы, каждый элемент которой в некоторой степени обращается в нуль, имеет тривиальный положительный ответ: уже в алфавите из двух букв имеются слова сколь угодно большой длины, не содержащие трех подряд одинаковых подслов (кубов). Первая конструкция такого рода принадлежит Туэ [1912]. Однако, если потребовать от полугруппы возможность ее задания конечным числом определяющих соотношений, ситуация сильно усложняется - вопрос о суще3. Реализация Машины Минского в конечно-определенной полугруппе

ношения (3.27), (3.29). В обоих случаях, согласно определению Т(х,у), число букв t изменяется аналогично Т(х,у).
Пусть теперь сумма количества букв а и b (п + к) изменилась.
Докажем утверждение при помощи индукции по сумме п + к. Для п + к = 0 имеем Т(0,0) = то.
Допустим, n + к нечетно, тогда у нас в слове - Q2 и единственным соотношением, увеличивающим п + к является Q2th = aQh - соотношение (3.28). Оно может быть применено, в случае если в слове нет Ь. Значит у нас в слове п + к букв а, нет букв b и Т{п + к, 0) букв t. После применения соотношения в слове п + к+1 букв а и Т(п + к, 0) — 1 букв t. Но Т(п + к + 1; 0) = Т(п + к, 0) - 1. Индуктивный переход в этом случае завершен.
Случай четной суммы п+к рассматривается аналогично, только единственным применимым соотношением будет LQit — LQ2b - соотношение (3.26).
Предложение 3.5.2. (г) Пусть Т(0,0) = 2п + Тогда
Т(п, 0) = 0 при нечетном п,
Т(0, п) = 0 при четном п.
(гг) Пусть Т(0,0) = 2п+ ДПД щ Тогда Т(п + 1,0) = 0 при нечетном п,
Т(0,п + 1) = 0 при четном п.
Докажем (i) по индукции. При ?г = 1,2 это очевидно. Если это выполнено для нечетного п, то
Т(п, 0) = 2(п + 1) + -2п+ = п +
Следовательно, по определению Т(0,п + 1) = Т(п + 1,0) — п — 1 = Т(п, 0) - п — 2 = 0.
Для четного п координаты меняются местами.
(ii) Очевидным образом следует из (i) и определения Т(х,у).
Таким образом, из предложений (3.5.1) и (3.5.2) следует, что если W приводится к виду, не содержащему букв t, то либо в слове нет букв а,
либо букв Ь. Таким образом, подслово aQibg встретиться не может.
Теперь допустим, что в слове встретилось Lu. Это означает, что W приведено к виду, не содержащему букв s. Заметим, что путь из состояния (0,0) в состояние (х, у) единственен (мы можем лишь возвращаться по нему назад или идти вперед) и по ходу этого пути количество букв