View source for Group calculus

<!--
g0452401.png
$#A+1 = 18 n = 0
$#C+1 = 18 : ~/encyclopedia/old_files/data/G045/G.0405240 Group calculus
Automatically converted into TeX, above some diagnostics.
Please remove this comment and the {{TEX|auto}} line below,
if TeX found to be correct.
-->

{{TEX|auto}}
{{TEX|done}}

An [[Associative calculus|associative calculus]] in which the natural group requirement of the existence of an inverse operation is effectively fulfilled. In fact, an associative calculus  $  \mathfrak A $
is said to be a group calculus [[#References|[1]]], [[#References|[15]]] if it is possible to construct for it an inverting algorithm, i.e. an [[Algorithm|algorithm]]  $  \mathfrak C $
such that for any word  $  P $
over the alphabet  $  A $
of  $  \mathfrak A $
the following conditions are satisfied: 1)  $  \mathfrak C ( P) $
is defined and is also a word over  $  A $; 
2) the words  $  P \mathfrak C ( P) $
and  $  \mathfrak C ( P) P $
are equivalent to the empty word in  $  \mathfrak A $(
here, the term  "algorithm"  must be understood in some exact meaning of the word, e.g. as a [[Normal algorithm|normal algorithm]]).

The most useful group calculi are those of a special type (the so-called inversive calculi, cf. [[#References|[2]]]), in which the existence of the inverting algorithm is ensured by a suitable choice of alphabets and lists of relations: The alphabet of an inversive calculus has even length, for each of its letters  $  \xi $
there exists an explicit inverse letter  $  \xi  ^ {-} 1 $, 
and the list of relations includes a complete collection of the so-called trivial relations, i.e. relations with empty words on their right-hand sides, while the form of their left-hand sides is  $  \xi \xi  ^ {-} 1 $.

The importance of group calculi consists in the fact that they are representations of finitely-presented groups (cf. also [[Finitely-presented group|Finitely-presented group]]). A group calculus  $  \mathfrak A $, 
like any other associative calculus, generates in a standard manner (cf. [[Associative calculus|Associative calculus]]) a finitely-presented associative system  $  K _ {\mathfrak A }  $, 
which is a group since  $  \mathfrak A $
has an inverting algorithm. The [[Algorithmic problem|algorithmic problem]] of recognizing word equivalence in a group calculus  $  \mathfrak A $
is the identity problem (word problem) for the finitely-presented group  $  K _ {\mathfrak A} $, 
stated in terms of the group calculus. This is the first one of a list of fundamental decidability problems formulated in 1911 by M. Dehn [[#References|[3]]] for finitely-presented groups. Several authors found a positive solution of this problem for groups definable by special types of group calculi. It was obtained, in particular, for groups defined by inversive calculi with one non-trivial relation [[#References|[4]]]. P.S. Novikov in 1952 ([[#References|[5]]], [[#References|[6]]]) was the first to construct an example of a finitely-presented group with an unsolvable word problem, i.e. a group generated by a group calculus for which no algorithm in an exact sense of the word (e.g. a [[Turing machine|Turing machine]] or a [[Normal algorithm|normal algorithm]]) can be constructed in order to solve the word problem in this calculus. This example gives a negative solution to the word problem for a given finitely-presented group, allowing for the modern precise statement of this problem as given by the theory of algorithms (cf. [[Church thesis|Church thesis]]). Other examples of such group calculi were introduced later (see, for example, , [[#References|[8]]]).

The example of Novikov just mentioned also gives a negative solution for Dehn's second fundamental problem — the problem on recognizing word pairs which are conjugate in a given group calculus. Subsequently, Novikov [[#References|[9]]] gave a simpler negative solution of the conjugacy problem, which is independent of this example.

Of great interest from the algebraic point of view is the study of properties of a group calculus that are invariant under isomorphisms of group calculi; these are then properties of abstract finitely-presented groups. S.I. Adyan [[#References|[10]]], [[#References|[11]]], [[#References|[12]]] in 1955 obtained a very general result, which parallels the result obtained by A.A. Markov for associative calculi, by giving a negative solution to almost-all algorithmic problems connected with fundamental classifications of group calculi then known. In particular, he obtained a negative solution to Dehn's third problem — the problem of isomorphism to some given finitely-presented group. Similar results were subsequently obtained by M. Rabin [[#References|[13]]].

The unsolvability of the above-mentioned algorithmic problems connected with group calculi implied negative solutions of several algorithmic problems in topology. Thus, a group calculus with an unsolvable conjugacy problem can be used to construct a two-dimensional polyhedron for which the problem of path homotopy is unsolvable. Building on the results of Adyan, Markov in 1958 obtained a negative solution of the homeomorphism problem [[#References|[14]]].

====References====
<table><TR><TD valign="top">[1]</TD> <TD valign="top">  A.A. Markov,   "Theory of algorithms" , Israel Program Sci. Transl.  (1961)  (Translated from Russian)  (Also: Trudy Mat. Inst. Steklov. 42 (1954))</TD></TR><TR><TD valign="top">[2]</TD> <TD valign="top">  A.A. Markov,   "Indistinguishability by invariants in the theory of associative calculi"  ''Izv. Akad. Nauk SSSR Ser. Mat.'' , '''27''' :  4  (1963)  pp. 907–936  (In Russian)</TD></TR><TR><TD valign="top">[3]</TD> <TD valign="top">  M. Dehn,   "Ueber unendliche diskontinuierliche Gruppen"  ''Math. Ann.'' , '''71'''  (1911)  pp. 116–144</TD></TR><TR><TD valign="top">[4]</TD> <TD valign="top">  W. Magnus,   "Ueber diskontinuierliche Gruppen mit einer definierenden Relation (der Freiheitssatz)"  ''J. Reine Angew. Math.'' , '''163''' :  2  (1931)  pp. 141–165</TD></TR><TR><TD valign="top">[5]</TD> <TD valign="top">  P.S. Novikov,   "On algorithmic unsolvability of the word problem"  ''Dokl. Akad. Nauk SSSR'' , '''85'''  (1952)  pp. 709–712  (In Russian)</TD></TR><TR><TD valign="top">[6]</TD> <TD valign="top">  P.S. Novikov,   "On algorithmic unsolvable problems of word identity in group theory" , Amer. Math. Soc.  (1958)  (Translated from Russian)</TD></TR><TR><TD valign="top">[7a]</TD> <TD valign="top">  W.W. Boone,   "Certain simple unsolvable problems of group theory I, II"  ''Indag. Math.'' , '''16'''  (1954)  pp. 231–237; 492–497</TD></TR><TR><TD valign="top">[7b]</TD> <TD valign="top">  W.W. Boone,   "Certain simple unsolvable problems of group theory III"  ''Indag. Math.'' , '''17'''  (1955)  pp. 571–577</TD></TR><TR><TD valign="top">[7c]</TD> <TD valign="top">  W.W. Boone,   "Certain simple unsolvable problems of group theory IV, V"  ''Indag. Math.'' , '''19'''  (1957)  pp. 22–27; 227–232</TD></TR><TR><TD valign="top">[8]</TD> <TD valign="top">  J.L. Britton,   "The word problem for groups"  ''Proc. London Math. Soc. (3)'' , '''8''' :  32  (1958)  pp. 493–506</TD></TR><TR><TD valign="top">[9]</TD> <TD valign="top">  P.S. Novikov,   "Unsolvability of the conjugacy problem in group theory"  ''Izv. Akad. Nauk SSSR Ser. Mat.'' , '''18''' :  6  (1954)  pp. 485–524  (In Russian)</TD></TR><TR><TD valign="top">[10]</TD> <TD valign="top">  S.I. Adyan,   "Algorithmic unsolvablity of problems of recognizing certain properties of groups"  ''Dokl. Akad. Nauk SSSR'' , '''103'''  (1955)  pp. 533–535  (In Russian)</TD></TR><TR><TD valign="top">[11]</TD> <TD valign="top">  S.I. Adyan,   "Finitely-presented groups and algorithms"  ''Dokl. Akad. Nauk SSSR'' , '''117''' :  1  (1957)  pp. 9–12  (In Russian)</TD></TR><TR><TD valign="top">[12]</TD> <TD valign="top">  S.I. Adyan,   "Unsolvability of certain algorithmic problems in the theory of groups"  ''Trudy Moskov. Mat. Obshch.'' , '''6'''  (1957)  pp. 231–298  (In Russian)</TD></TR><TR><TD valign="top">[13]</TD> <TD valign="top">  M.O. Rabin,   "Algorithmic unsolvability of group theoretic problems"  ''Ann. of Math.'' , '''67'''  (1958)  pp. 172–194</TD></TR><TR><TD valign="top">[14]</TD> <TD valign="top">  A.A. Markov,   "The unsolvability of the homeomorphism problem"  ''Dokl. Akad. Nauk SSSR'' , '''121''' :  2  (1958)  pp. 218–220  (In Russian)</TD></TR><TR><TD valign="top">[15]</TD> <TD valign="top">  A.A. Markov,   N.M. [N.M. Nagornyi] Nagorny,   "The theory of algorithms" , Kluwer  (1988)  (Translated from Russian)</TD></TR></table>

====Comments====
For a more up-to-date survey of Dehn's problems, especially the conjugacy problem, see [[#References|[a1]]] and the extensive bibliography there.

The volume [[#References|[a2]]] contains a number of survey articles on word problems and related algorithmic problems in group theory.

====References====
<table><TR><TD valign="top">[a1]</TD> <TD valign="top">  R.D. Hurwitz,   "A survey of the conjugacy problem"  ''Contemp. Math.'' , '''33'''  (1984)  pp. 278–298</TD></TR><TR><TD valign="top">[a2]</TD> <TD valign="top">  W.W. Boone (ed.)  F.B. Cannonito (ed.)  R.C. Lyndon (ed.) , ''Word problems'' , North-Holland  (1973)</TD></TR></table>