ИЗОМОРФИЗМА ПРОБЛЕМА

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

Для многих важных классов алгебр И. п. неразрешима. Доказана неразрешимость частной И. п. для произвольной конечно определенной полугруппы в классе всех конечно определенных полугрупп [2] и частной И. п. для произвольной конечно определенной группы в классе всех конечно определенных групп [1]. В классе всех групп из многообразия n-ступенно разрешимых групп, задаваемых в этом многообразии конечным числом образующих и определяющих соотношений, при И. п. также неразрешима [3].

И. п. разрешима в классе всех конечных конечно определенных алгебр фиксированной сигнатуры, в классе абелевых групп.

Открытыми остаются пока (к 1978) И. п. для нильпотентных групп ступени 2, групп с одним определяющим соотношением. И. п. для групп связана с алгоритмич. проблемами топологии.

Лит.:[1] Адян С. И., "Тр. Моск. матем. об-ва", 1957, т. 6, с. 231-98; [2] Марков А. А., Теория алгорифмов, М.-Л., 1954 (Тр. матем. ин-та АН СССР, т. 42); [3] Киркинский А. С, Ремесленников В. Н., "Матем. заметки", 1975, т. 18, № 3, с. 437 - 43.

А. Л. Семенов.