Алгоритмические проблемы в теории групп

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

---

Если вы ищете компанию, которая выполняет диссертации на заказ , переходите на Work5 и заполняйте форму заказа.

---

. При таком положении полностью закрывалась возможность устанавливать несуществование алгоритма для той или другой серии задач. Поэтому в тех случаях, когда алгоритма для какого-нибудь круга задач не существует, математика оказывалась беспомощной. Развитие математической логики позволило дать точное определение понятию алгоритма, или закона; это и было осуществлено в 30-х годах этого столетия в ряде работ (Черча, Тюринга, Клина). Впоследствии были даны другие формы определения понятия алгоритма (Марков, Колмогоров). Это обстоятельство позволило обнаружить наличие алгоритмически неразрешимых задач сначала в математической логике, а затем и в самой математике. Так, Марков и Пост доказали неразрешимость проблемы тождеств слов в ассоциативных системах. Марков сделал это для проблемы делимости в ассоциативных системах и решил соответствующие вопросы для матриц. Тюринг показал алгоритмическую неразрешимость проблемы слов для полугрупп с сокращениями. В настоящей работе доказывается неразрешимость проблемы тождеств, слов для групп. Как известно, словом в группе (или в другой системе) называется произведение образующих этой группы.

Проблема тождеств слов для групп, заданных конечным числом образующих, связанных конечным числом определяющих соотношений ставится следующим образом: требуется построить алгоритм, позволяющий для любых двух слов установить, равны они между собой или нет. В некоторых частных случаях эту проблему удается. Разработка точного понятия алгоритма, данная в последнее время рядом авторов, позволила доказать неразрешимость некоторых алгоритмических проблем. Алгоритмическая проблема всегда имеет массовый характер. Она соответствует целому классу отдельных вопросов, требующих ответа «да» или «нет» и состоит в разыскании алгоритма, позволяющего решить любой из этих вопросов. Неразрешимость алгоритмической проблемы означает только невозможность решить все эти вопросы с помощью единого общего метода. Но это ни в коем случае не означает неразрешимости какой-нибудь из объединяемых ею единичных проблем. Теоремы о невозможности алгоритмов имеют существенное значение для развития математики, хотя бы потому уже, что они предостерегают математиков от безнадежных поисков несуществующих алгоритмов.

1. Новиков П. С , Об алгоритмической неразрешимости проблемы тождества слов в теории групп. Труды Матем. ин-та им. Стеклова 44 (1955). 2. Новиков П. С, Неразрешимость проблемы сопряженности в теории групп, Изв. АН, сер. матем. 18 (1954), 485—524. 3. Курош А. Г., Теория групп, М.—Л., Гостехиздат, 1953. 4. Ад ян С И . , Алгоритмическая неразрешимость проблем распознавания некоторых свойств групп, ДАН 103, № 4 (1955), 533—535.