7.25 (1980)

We associate with words in the alphabet $x, x^{-1}, y, y^{-1}, z, z^{-1}, \dots$ operations which are understood as functions in variables $x, y, z, \dots$. We say that a word $A$ is expressible in words $B_1, \dots, B_n$ on the group $G$ if $A$ can be constructed from the words $B_1, \dots, B_n$ and variables by means of finitely many substitutions of words one into another and replacements of a word by another word which is identically equal to it on $G$. A list of words is said to be functionally complete on $G$ if every word can be expressed on $G$ in words from this list. A word $B$ is called a Schaeffer word on $G$ if every word can be expressed on $G$ in $B$ (compare with A. V. Kuznetsov, Matem. Issledovaniya, Kishinëv, 6, no. 4 (1971), 75–122 (Russian)). Does there exist an algorithm which decides
$\qquad$ a) by a word $B$, whether it is a Schaeffer word on every group? Compare with the problem of describing all such words in (A. G. Kurosh, Theory of Groups, Moscow, Nauka, 1967, p. 435 (Russian)); here are examples of such words: $xy^{-1}$, $x^{-1}y^2 z$, $x^{-1}y^{-1}zx$.
$\qquad$ b) by a list of words, whether it is functionally complete on every group?
$\qquad$ c) by words $A, B_1, \dots, B_n$, whether $A$ is expressible in $B_1, \dots, B_n$ on every group? (This is a problem from A. V. Kuznetsov, ibid., p. 112.)
$\qquad$ d) the same for every finite group? (For finite groups, for example, $x^{-1}$ is expressible in $xy$.) For a fixed finite group an algorithm exists (compare with A. V. Kuznetsov, ibid., § 8).