{"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","summary":"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…","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"discussed":0,"published":"2026-07-15","reactions":{}}