The Post Correspondence Problem for free groups is undecidable

We prove that the Post Correspondence Problem for finitely generated free groups is undecidable, even when one of the two homomorphisms is injective. This resolves a longstanding open problem in algorithmic group theory. The result exhibits a sharp contrast with the theory of fixed subgroups: although the equalizer of two free-group homomorphisms is finitely generated whenever one of the maps is injective, there is no algorithm that decides whether this equalizer is trivial.
The proof proceeds through a connection with finite-state transducers. Given a cyclic tag system $\mathcal C$, we effectively construct a finite partial deterministic inverse transducer $\mathcal{T}_{\mathcal C}$ whose fixed-point set is nontrivial if and only if $\mathcal C$ halts. We then associate to any such transducer two homomorphisms \(g,h\colon F_Y\longrightarrow F_A,\) with $h$ injective, such that their equalizer is nontrivial precisely when the transducer has a nontrivial fixed loop. Consequently, the rank of these equalizers cannot be computed in general, answering a question posed by Stallings in 1984.
As a further consequence, we prove that no algorithm computes a basis for the fixed subgroup of a virtual endomorphism of a finitely generated free group, nor constructs a finite automaton recognizing the reduced fixed-point language of a finite complete inverse transducer.