Return to Answer

The problem is decidable if and only if there exists a homomorphism from $G$ to the infinite cyclic group $\mathbb Z$ taking $g$ to 1 (the generator of $\mathbb Z$. Clearly, if such a homomorphism exists, the answer to your question is "yes" for every $H,h$. Suppose that there is no such homomorphism. Consider the signature (group operations, nullary operation) of pairs $(H,h)$ where $H$ is a group, $h\in H$. Let $X$ be the set of generators and $R$ be the set of defining relations of $G$, suppose $g$ is represented by a word $w$ in $X$. Then you are asking, whether a formula $\theta=\exists X (\& R \& (w=h))$ is true for the pair $(H,h)$. But the negation $\neg\theta$ is a Markov property. Indeed, there exists a pair, say, $({\mathbb Z},1)$ which satisfies $\neg\theta$ because there is no homomorphism $G\to \mathbb Z$ that takes $g$ to $1$, and there exists a pair, say, $(G,g)$ which cannot be embedded into any pair $(G',g)$ which satisfies $\neg\theta$. The proof that Markov properties for pairs $(H,h)$ are undecidable is the same as the proof of the Adian-Rabin theorem for groups .

The problem is decidable if and only if there exists a homomorphism from $G$ to the infinite cyclic group $\mathbb Z$ taking $g$ to 1 (the generator of $\mathbb Z$). Clearly, if such a homomorphism exists, the answer to your question is "yes" for every $H,h$. Suppose that there is no such homomorphism. Consider the signature (group operations, nullary operation) of pairs $(H,h)$ where $H$ is a group, $h\in H$. Let $X$ be the set of generators and $R$ be the set of defining relations of $G$, suppose $g$ is represented by a word $w$ in $X$. Then you are asking, whether a formula $\theta=\exists X (\& R \& (w=h))$ is true for the pair $(H,h)$. But the negation $\neg\theta$ is a Markov property. Indeed, there exists a pair, say, $({\mathbb Z},1)$ which satisfies $\neg\theta$ because there is no homomorphism $G\to \mathbb Z$ that takes $g$ to $1$, and there exists a pair, say, $(G,g)$ which cannot be embedded into any pair $(G',g)$ which satisfies $\neg\theta$. The proof that Markov properties for pairs $(H,h)$ are undecidable is the same as the proof of the Adian-Rabin theorem for groups .

The problem is decidable if and only if there exists a homomorphism from $G$ to the infinite cyclic group $\mathbb Z$ taking $g$ to 1 (the generator of $\mathbb Z$. Clearly, if such a homomorphism exists, the answer to your question is "yes" for every $H,h$. Suppose that there is no such homomorphism. Consider the signature (group operations, nullary operation) of pairs $(H,h)$ where $H$ is a group, $h\in H$. Let $X$ be the set of generators and $R$ be the set of defining relations of $G$, suppose $g$ is represented by a word $w$ in $X$. Then you are asking, whether a formula $\theta=\exists X (\& R \& (w=h))$ is true for the pair $(H,h)$. But the negation $\neg\theta$ is a Markov property. Indeed, there exists a pair, say, $({\mathbb Z},1)$ which satisfies $\neg\theta$ because there is no homomorphism $G\to \mathbb Z$ that takes $g$ to $1$, and there exists a pair, say, $(G,g)$ which cannot be embedded into any pair $(G',g)$ which satisfies that property. The proof that Markov properties for pairs $(H,h)$ are undecidable is the same as the proof of the Adian-Rabin theorem for groups .

The problem is decidable if and only if there exists a homomorphism from $G$ to the infinite cyclic group $\mathbb Z$ taking $g$ to 1 (the generator of $\mathbb Z$. Clearly, if such a homomorphism exists, the answer to your question is "yes" for every $H,h$. Suppose that there is no such homomorphism. Consider the signature (group operations, nullary operation) of pairs $(H,h)$ where $H$ is a group, $h\in H$. Let $X$ be the set of generators and $R$ be the set of defining relations of $G$, suppose $g$ is represented by a word $w$ in $X$. Then you are asking, whether a formula $\theta=\exists X (\& R \& (w=h))$ is true for the pair $(H,h)$. But the negation $\neg\theta$ is a Markov property. Indeed, there exists a pair, say, $({\mathbb Z},1)$ which satisfies $\neg\theta$ because there is no homomorphism $G\to \mathbb Z$ that takes $g$ to $1$, and there exists a pair, say, $(G,g)$ which cannot be embedded into any pair $(G',g)$ which satisfies $\neg\theta$. The proof that Markov properties for pairs $(H,h)$ are undecidable is the same as the proof of the Adian-Rabin theorem for groups .

The problem is decidable if and only if there exists a homomorphism from $G$ to the infinite cyclic group $\mathbb Z$ taking $g$ to 1. Clearly, if such a homomorphism exists, the answer to your question is "yes" for every $H,h$. Suppose that there is no such homomorphism. Consider the signature (group operations, nullary operation) of pairs $(H,h)$ where $H$ is a group, $h\in H$. Let $X$ be the set of generators and $R$ be the set of defining relations of $G$, suppose $g$ is represented by a word $w$ in $X$. Then you are asking, whether a formula $\theta=\exists X, \& R \& (w=h)$ is true for the pair $(H,h)$. But the negation $\neg\theta$ is a Markov property. Indeed, there exists a pair, say, $({\mathbb Z},1)$ which satisfies $\neg\theta$, and there exists a pair, say, $(G,g)$ which cannot be embedded into any pair $(G',g)$ which satisfies that property. The proof that Markov properties for pairs $(H,h)$ are undecidable is the same as the proof of the Adian-Rabin theorem for groups.

The problem is decidable if and only if there exists a homomorphism from $G$ to the infinite cyclic group $\mathbb Z$ taking $g$ to 1 (the generator of $\mathbb Z$. Clearly, if such a homomorphism exists, the answer to your question is "yes" for every $H,h$. Suppose that there is no such homomorphism. Consider the signature (group operations, nullary operation) of pairs $(H,h)$ where $H$ is a group, $h\in H$. Let $X$ be the set of generators and $R$ be the set of defining relations of $G$, suppose $g$ is represented by a word $w$ in $X$. Then you are asking, whether a formula $\theta=\exists X (\& R \& (w=h))$ is true for the pair $(H,h)$. But the negation $\neg\theta$ is a Markov property. Indeed, there exists a pair, say, $({\mathbb Z},1)$ which satisfies $\neg\theta$ because there is no homomorphism $G\to \mathbb Z$ that takes $g$ to $1$, and there exists a pair, say, $(G,g)$ which cannot be embedded into any pair $(G',g)$ which satisfies that property. The proof that Markov properties for pairs $(H,h)$ are undecidable is the same as the proof of the Adian-Rabin theorem for groups  .