Let $G, H$ be finitely presented groups with decidable word problems.

Can there be a homomorphism $f:G\to H$ such that there is no algorithm deciding given $w\in H$ whether $f^{-1}(w)$ is empty or not?

MathOverflow is a question and answer site for professional mathematicians. It only takes a minute to sign up.

Sign up to join this community
Anybody can ask a question

Anybody can answer

The best answers are voted up and rise to the top

$\begingroup$
$\endgroup$

6
Let $G, H$ be finitely presented groups with decidable word problems.

Can there be a homomorphism $f:G\to H$ such that there is no algorithm deciding given $w\in H$ whether $f^{-1}(w)$ is empty or not?

1more comment