View source for Associative calculus

A name given to calculi (cf. [[Calculus|Calculus]]) of a very definite type, especially suitable for specifying finitely-presented associative systems (semi-groups, cf. [[Semi-group|Semi-group]]). The term  "associative calculus"  was introduced by A.A. Markov, who also developed the theory of associative calculi [[#References|[2]]].

Any associative calculus <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a013/a013500/a0135001.png" /> is defined by specifying some [[Alphabet|alphabet]] <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a013/a013500/a0135002.png" /> and a finite list <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a013/a013500/a0135003.png" /> of relations in <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a013/a013500/a0135004.png" /> — pairs of words (cf. [[Word|Word]]) in this alphabet. The words constituting a relation are often called its parts — left and right. A <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a013/a013500/a0135006.png" />-permissible operation on words in <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a013/a013500/a0135007.png" /> is any substitution of one part of any relation belonging to <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a013/a013500/a0135008.png" />, where it occurs imbedded in a word in <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a013/a013500/a0135009.png" /> (cf. [[Imbedded word|Imbedded word]]), by the other part of the same relation. An associative calculus <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a013/a013500/a01350010.png" /> is the performance of a sequence of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a013/a013500/a01350011.png" />-permissible operations, starting from any word <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a013/a013500/a01350012.png" /> in <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a013/a013500/a01350013.png" />. One says that all words <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a013/a013500/a01350014.png" /> obtained in this way (including the initial word <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a013/a013500/a01350015.png" /> itself) are equivalent to <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a013/a013500/a01350016.png" /> in the associative calculus <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a013/a013500/a01350017.png" /> (in symbolic notation, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a013/a013500/a01350018.png" />). The relation <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a013/a013500/a01350019.png" /> for any associative calculus <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a013/a013500/a01350020.png" /> is reflexive, symmetric and transitive. In addition, it follows from <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a013/a013500/a01350021.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a013/a013500/a01350022.png" /> that <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a013/a013500/a01350023.png" />. This makes it possible, in a natural manner, to assign to each associative calculus <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a013/a013500/a01350024.png" /> a finitely-presented associative system <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a013/a013500/a01350025.png" />, whose elements are equivalence classes of words in <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a013/a013500/a01350026.png" /> and whose multiplication operation is induced by the operation of concatenation of words in <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a013/a013500/a01350027.png" />. The associative system <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a013/a013500/a01350028.png" /> thus constructed will have a unit (the element represented by the empty word); the elements of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a013/a013500/a01350029.png" /> represented by the letters of the alphabet <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a013/a013500/a01350030.png" /> will constitute a system of generating elements for <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a013/a013500/a01350031.png" />, while the list of relations <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a013/a013500/a01350032.png" /> represents a complete system of relations between these generating elements of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a013/a013500/a01350033.png" /> in the sense that the elements of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a013/a013500/a01350034.png" /> represented by two words <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a013/a013500/a01350035.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a013/a013500/a01350036.png" /> are identical in <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a013/a013500/a01350037.png" /> if and only if <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a013/a013500/a01350038.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a013/a013500/a01350039.png" /> are equivalent in <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a013/a013500/a01350040.png" />. Thus, the recognition of the identity of elements in <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a013/a013500/a01350041.png" /> is reduced to the recognition of equivalence of words in <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a013/a013500/a01350042.png" />. Hence the importance of the study of the solvability of the [[Algorithmic problem|algorithmic problem]] of recognition of equivalent words in an arbitrary associative calculus. This problem was first formulated by A. Thue : Construct, for an arbitrary associative calculus <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a013/a013500/a01350043.png" />, an algorithm which, for any pair of words in the alphabet of this associative calculus, determines, in a finite number of steps, whether or not the words constituting the pair are equivalent in <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a013/a013500/a01350044.png" />. In the algebraic interpretation, this problem is the identity problem for the associative system <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a013/a013500/a01350045.png" />. Thue succeeded in solving the problem in a few special cases only. In the modern interpretation of the problem (1930's and later) the algorithm of this problem is sought in some exact meaning of the word, such as a [[Partial recursive function|partial recursive function]], a [[Turing machine|Turing machine]] or a [[Normal algorithm|normal algorithm]]. If the problem is thus modernized, the problem of finding a specific associative calculus for which the desired algorithm does not exist becomes meaningful. Markov [[#References|[3]]] and E.L. Post [[#References|[4]]], working independently of each other, constructed unsolvable associative calculi, i.e. associative calculi with an unsolvable algorithmic problem of recognition of word equivalence. These results yield a negative solution of Thue's problem in its modern form. However, if one accepts the [[Church thesis|Church thesis]] or any other equivalent assumption regarding the adequacy of recursive functions for rendering the concept of an algorithm more precise, one comes to the inevitable conclusion that Thue's problem in its original form as well has a negative solution for some concrete associative calculi.

The original examples constructed by Markov and Post were extremely complex. Simpler unsolvable associative calculi were subsequently presented. They include, for example, an associative calculus with seven very simple relations [[#References|[5]]], and one with only three such relations [[#References|[6]]]. Thue's problem has been almost fully solved for the case of an associative calculus with one relation [[#References|[7]]].

In a natural way one defines an isomorphism of one associative calculus into another and onto another [[#References|[2]]]. Of special interest from the algebraic point of view is the study of those properties of associative calculi that are invariant under isomorphisms; they are the properties of abstract associative systems. Markov [[#References|[2]]], who based himself on his own studies on the recognition of word equivalence in an associative calculus, obtained a very general result, which yields a negative solution to practically all algorithmic problems concerning the basic classifications of associative calculi studied at that time. He showed, in particular, that if <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a013/a013500/a01350046.png" /> is an isomorphism-invariant property of an associative calculus, if there is a unique associative calculus with the property <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a013/a013500/a01350047.png" /> and if there exists also an associative calculus not included in any associative calculus with the property <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a013/a013500/a01350048.png" />, then the algorithmic problem of recognition of an associative calculus with the property <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a013/a013500/a01350049.png" /> among other associative calculi is unsolvable for any alphabet with more than three letters. It immediately follows that algorithmic problems of recognition of uniqueness of associative calculi, finiteness of an associative calculus, the semi-group character of an associative calculus, inclusion in group-associative calculi, and isomorphism of pairs of associative calculi, are unsolvable for any alphabet with more than three letters. It was subsequently proved [[#References|[8]]] that the set of pairs of isomorphic associative calculi is recursively enumerable; the method used in this connection also makes it possible to establish the recursive enumerability of the number of invariant properties of associative calculi.

====References====
<table><TR><TD valign="top">[1a]</TD> <TD valign="top">  A. Thue,   "Probleme über Veränderungen von Zeichenreihen nach gegebener Regeln"  ''Kra. Vidensk. Selsk. Skrifter. 1. Mat. Nat. Kl.'' :  10  (1914)</TD></TR><TR><TD valign="top">[1b]</TD> <TD valign="top">  A. Thue,   "Probleme über Veränderungen von Zeichenreihen nach gegebener Regeln" , ''Selected Math. Papers'' , Univ. Forlaget , Oslo  (1977)  pp. 493–524</TD></TR><TR><TD valign="top">[2]</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">[3]</TD> <TD valign="top">  A.A. Markov,   "On the impossibility of certain algorithms in the theory of associative systems"  ''C.R. Acad. Sci. URSS'' , '''55'''  (1948)  pp. 533–586  ''Dokl. Akad. Nauk SSSR'' , '''55''' :  7  (1947)  pp. 587–590</TD></TR><TR><TD valign="top">[4]</TD> <TD valign="top">  E.L. Post,   "Recursive unsolvability of a problem of Thue"  ''J. Symbolic Logic'' , '''12''' :  1  (1947)  pp. 1–11</TD></TR><TR><TD valign="top">[5]</TD> <TD valign="top">  G.S. Tseitin,   "Associative calculi with undecidable equivalence problems"  ''Dokl. Akad. Nauk SSSR'' , '''107''' :  3  (1956)  pp. 370–371  (In Russian)</TD></TR><TR><TD valign="top">[6]</TD> <TD valign="top">  Yu.V. Matiyasevich,   "Simple examples of undecidable associative calculi"  ''Soviet Math. Dokl.'' , '''8''' :  2  (1967)  pp. 555–557  ''Dokl. Akad. Nauk SSSR'' , '''173''' :  6  (1967)  pp. 1264–1266</TD></TR><TR><TD valign="top">[7]</TD> <TD valign="top">  S.I. [S.I. Adyan] Adjan,   "Defining relations and algorithmic problems for groups and semigroups"  ''Proc. Steklov Inst. Math.'' , '''85'''  (1967)  ''Trudy Mat. Inst. Steklov.'' , '''85'''  (1966)</TD></TR><TR><TD valign="top">[8]</TD> <TD valign="top">  N.M. Nagornyi,   "On the search of isomorphisms of associative calculi"  ''Z. Math. Logik Grundl. Math.'' , '''6'''  (1960)  pp. 319–324  (In Russian)  (German abstract)</TD></TR></table>



====Comments====
The term  "associative calculus"  seems to be restricted to the Russian literature; in the West the term  "Thue systemThue system"  is often used. For an account of Thue systems and related combinatorial decision problems, see [[#References|[a1]]], Chapt. 6, or [[#References|[a2]]].

====References====
<table><TR><TD valign="top">[a1]</TD> <TD valign="top">  M. Davis,   "Computability and unsolvability" , McGraw-Hill  (1958)</TD></TR><TR><TD valign="top">[a2]</TD> <TD valign="top">  M. Davis,   "Unsolvable problems"  J. Barwise (ed.) , ''Handbook of mathematical logic'' , North-Holland  (1977)  pp. 567–594</TD></TR></table>