Computable invariant

of a binary relation between words of a given type

An algorithm (in some exact sense of the word; e.g. — as used in [1], [2] — a normal algorithm) which is applicable to all the words of this type, and which processes any two related words into the same word.

According to A.A. Markov, two words are inseparable by invariants of the given relation if all computable invariants of this relation process these words to yield the same result. One may note that if some binary relation is decidable (cf. Decidable set), a computable invariant for it assuming different values on any two words not related is readily constructed. If, on the other hand, one is successful in constructing words not related but inseparable by invariants, one has proved that the relation concerned is not decidable.

Many well-known algorithmic problems (cf. Algorithmic problem) in algebra and in topology may be formulated as tasks of investigating the decidability of certain classes of equivalence relations, and negative solutions of such problems are usually obtained as statements to the effect that there exist undecidable relations between equivalence relations of certain types. Markov compiled a program for strengthening (as indicated in the previous paragraph) certain negative solutions of numerous algorithmic problems (word identity problems in group theory, homeomorphism problems, problems on the recognition of invariant properties of associative calculi and group calculi). An example has been constructed of an enumerable (cf. Enumerable set) but undecidable word equivalence relation, in which any two words not related are nevertheless separable by invariants of the binary relation [3]. It is still (1987) an open question whether or not a similar result can be obtained for the classes of relationships studied by Markov.

References

[1]	A.A. Markov, "On indistinguishability by invariants in the theory of associative calculi" Izv. Akad. Nauk SSSR Ser. Mat. , 27 (1963) pp. 907–936 (In Russian)
[2]	A.A. Markov, N.M. [N.M. Nagornyi] Nagorny, "The theory of algorithms" , Kluwer (1988) (Translated from Russian)
[3]	N.M. Nagornyi, "Separability with respect to invariants" , Studies on the theory of algorithms and mathematical logic , 1 , Moscow (1973) pp. 205–210 (In Russian)