Associative calculus

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

Any associative calculus $ \mathfrak A $ is defined by specifying some alphabet $ A $ and a finite list $ \sigma $ of relations in $ A $— pairs of words (cf. Word) in this alphabet. The words constituting a relation are often called its parts — left and right. A $ \sigma $- permissible operation on words in $ A $ is any substitution of one part of any relation belonging to $ \sigma $, where it occurs imbedded in a word in $ \mathfrak A $( cf. Imbedded word), by the other part of the same relation. An associative calculus $ \mathfrak A $ is the performance of a sequence of $ \sigma $- permissible operations, starting from any word $ P $ in $ A $. One says that all words $ Q $ obtained in this way (including the initial word $ P $ itself) are equivalent to $ P $ in the associative calculus $ \mathfrak A $( in symbolic notation, $ \mathfrak A : P \amalg Q $). The relation $ \amalg $ for any associative calculus $ \mathfrak A $ is reflexive, symmetric and transitive. In addition, it follows from $ \mathfrak A : P \amalg Q $ and $ \mathfrak A : R \amalg S $ that $ \mathfrak A : PR \amalg QS $. This makes it possible, in a natural manner, to assign to each associative calculus $ \mathfrak A $ a finitely-presented associative system $ K _ {\mathfrak A} $, whose elements are equivalence classes of words in $ A $ and whose multiplication operation is induced by the operation of concatenation of words in $ A $. The associative system $ K _ {\mathfrak A} $ thus constructed will have a unit (the element represented by the empty word); the elements of $ K _ {\mathfrak A} $ represented by the letters of the alphabet $ A $ will constitute a system of generating elements for $ K _ {\mathfrak A} $, while the list of relations $ \sigma $ represents a complete system of relations between these generating elements of $ K _ {\mathfrak A} $ in the sense that the elements of $ K _ {\mathfrak A} $ represented by two words $ P $ and $ Q $ are identical in $ K _ {\mathfrak A} $ if and only if $ P $ and $ Q $ are equivalent in $ \mathfrak A $. Thus, the recognition of the identity of elements in $ K _ {\mathfrak A} $ is reduced to the recognition of equivalence of words in $ \mathfrak A $. Hence the importance of the study of the solvability of the 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 $ \mathfrak A $, 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 $ \mathfrak A $. In the algebraic interpretation, this problem is the identity problem for the associative system $ K _ {\mathfrak A} $. 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, a Turing machine or a 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 [3] and E.L. Post [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 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 [5], and one with only three such relations [6]. Thue's problem has been almost fully solved for the case of an associative calculus with one relation [7].

In a natural way one defines an isomorphism of one associative calculus into another and onto another [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 [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 $ I $ is an isomorphism-invariant property of an associative calculus, if there is a unique associative calculus with the property $ I $ and if there exists also an associative calculus not included in any associative calculus with the property $ I $, then the algorithmic problem of recognition of an associative calculus with the property $ I $ 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 [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

[1a]	A. Thue, "Probleme über Veränderungen von Zeichenreihen nach gegebener Regeln" Kra. Vidensk. Selsk. Skrifter. 1. Mat. Nat. Kl. : 10 (1914)
[1b]	A. Thue, "Probleme über Veränderungen von Zeichenreihen nach gegebener Regeln" , Selected Math. Papers , Univ. Forlaget , Oslo (1977) pp. 493–524
[2]	A.A. Markov, "Theory of algorithms" , Israel Program Sci. Transl. (1961) (Translated from Russian) (Also: Trudy Mat. Inst. Steklov. 42 (1954))
[3]	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
[4]	E.L. Post, "Recursive unsolvability of a problem of Thue" J. Symbolic Logic , 12 : 1 (1947) pp. 1–11
[5]	G.S. Tseitin, "Associative calculi with undecidable equivalence problems" Dokl. Akad. Nauk SSSR , 107 : 3 (1956) pp. 370–371 (In Russian)
[6]	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
[7]	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)
[8]	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)

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 [a1], Chapt. 6, or [a2].

References

[a1]	M. Davis, "Computability and unsolvability" , McGraw-Hill (1958)
[a2]	M. Davis, "Unsolvable problems" J. Barwise (ed.) , Handbook of mathematical logic , North-Holland (1977) pp. 567–594