Fix a finitely-presented group $G$ with distinguished non-identity element $g$. For any finitely-presented group $H$ with element $h$, is it decidable whether there is a homomorphism $h: G \rightarrow H$ such that $h(g) = h\ ?$
If we know $G$ is cyclic, the question is undecidable by reduction from the Word Problem. But what if we don't know anything about $G$? What if we know $g$ has finite order in $G$?
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 .
As people have already observed, if G is infinite cyclic and g is a generator, then the answer is always "yes". Steven Sam's comment shows that there can't be a uniform algorithm that works for all cyclic groups Z/n. In fact, the problem is undecidable for any given n. For instance:-
For finite cyclic G of order n with generator g, the question can be rephrased as "Is it decidable whether the element h is of finite order dividing n?". Suppose H is torsion-free. If this problem is decidable for some n then the word problem is solvable in H.
But the word problem is not solvable in torsion-free groups. For instance, Collins and Miller constructed a sequence of presentations for torsion-free groups H_1, H_2,... with the property that each H_i is torsion-free and it is undecidable which of the H_i are trivial. (More precisely, the set of all i such that H_i is trivial is recursively enumerable but not recursive.)
If G is infinite cyclic and g generates G, then the answer is: "yes, there is such a map" (so in particular, it's not undecidable at all).
So I'm not quite sure what the original poster meant by saying that if G is cyclic, the problem is redicible to the word problem. Maybe, if someone sees how that argument would go (and what the right hypothesis is), they could explain it.
Then it might be more clear whether this same argument can be applied if G is not cyclic.
Charles is right, of course, to say that a map from G to H restricts to a map from the cyclic group generated by g, to H, but if you could determine that there was no appropriate map from G to H, that wouldn't necessarily tell you that there was no appropriate map from < g> to H, so, on the face of it, it's possible that it could be decidable that there were no appropriate maps from G to H, but not decidable whether or not there were appropriate maps from < g> to H. (Here, "appropriate" means "taking g to h".)
(Edited to correct html issue.)
I'm with Reid. If G,H are finitely presented, and g,h elements, and we want to know if there's a morphism f:G->H with f(g)=h, wouldn't that restrict to a morphism on the cyclic group generated by g, and thus be immediately undecidable?
