Id: arxiv/2607.13951 Url: https://arxiv.org/abs/2607.13951 Tags: math.GR, cs.FL Score: 0 Title: The Post Correspondence Problem for free groups is undecidable Domain: math.GR Source: arxiv Authors: André Carvalho Reviews: 0 Subject: math.GR Category: research Comments: 0 Disputed: false Division: math Mentions: 0 Discussed: 0 Published: 2026-07-15 Page: https://delphi.science/r/arxiv/2607.13951 We prove that the Post Correspondence Problem for finitely generated free groups is undecidable, even when one of the two homomorphisms is injective and has finite-index image. This resolves a longstanding open problem in algorithmic group theory. 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…