Isomorphism problem

The problem of describing an algorithm that enables one to establish whether or not any pair of recursively-presented algebraic systems (cf. Algebraic system) in a given class are isomorphic. The partial isomorphism problem for a fixed algebraic system $ A $ consists of describing an algorithm that recognizes whether or not a recursively-presented algebraic system in the class under discussion is isomorphic to $ A $. A positive solution of the (partial) isomorphism problem consists of a description of the desired algorithm (the respective problem is solvable); a negative solution consists of proving that no algorithm exists (the respective problem is unsolvable). Usually, this isomorphism problem is formulated for algebras given by generators and defining relations.

The isomorphism problem is unsolvable for many important classes of algebraic systems. The unsolvability of the partial isomorphism problem for a finitely-presented semi-group in the class of all finitely-presented semi-groups was established in [2], and that for finitely-presented groups in the class of all finitely-presented groups in [1]. The isomorphism problem for groups in the variety of solvable groups of solvability length $ n $, given in the variety by a finite number of generators and relations, is also unsolvable for $ n \geq 7 $[3].

The isomorphism problem is solvable in the class of all finite finitely-presented algebras of fixed signature, and in the class of Abelian groups.

The isomorphism problem for nilpotent groups of class 2 and for groups with one defining relation is still open (1988). The isomorphism problem for groups is connected with algorithmic problems in topology.

References

[1]	S.I. Adyan, "Unsolvability of some algorithmic problems in group theory" Trudy Moskov. Mat. Obshch. , 6 (1957) pp. 231–298 (In Russian)
[2]	A.A. Markov, "Theory of algorithms" , Israel Program Sci. Transl. (1961) (Translated from Russian) (Also: Trudy Mat. Inst. Steklov. 42 (1954))
[3]	A.S. Kirkinskii, V.N. Remeslennikov, "The isomorphism problem for solvable groups" Math. Notes , 18 : 3 (1975) pp. 849–853 Mat. Zametki , 18 : 3 (1975) pp. 437–443