Theorem A 1. There is no algorithm which, given homomorphisms \[g,h\colon F_Y\longrightarrow F_A\] between finitely generated free groups, with \(h\) injective, decides whether \[\operatorname{Eq}(g,h)\neq\{1\}.\]
The Post Correspondence Problem for free groups is undecidable
July 15, 2026
Abstract
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 \(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.
1 Introduction↩︎
The Post Correspondence Problem is one of the classical sources of undecidability in theoretical computer science. Given two homomorphisms \(\phi,\psi\colon X^*\longrightarrow Y^*\) between finitely generated free monoids, it asks whether there exists a nonempty word \(w\in X^*\) such that \(w\phi=w\psi.\) Equivalently, the problem asks whether the equalizer \[\operatorname{Eq}(\phi,\psi) = \{w\in X^*\mid w\phi=w\psi\}\] is nontrivial. Post proved in 1946 that no algorithm decides this problem .
The analogous problem for free groups has remained open. Given finite alphabets \(A\) and \(B\) and homomorphisms \(\phi,\psi\colon F_A\longrightarrow F_B,\) the Post Correspondence Problem for free groups asks whether \[\operatorname{Eq}(\phi,\psi) = \{x\in F_A\mid x\phi=x\psi\}\] contains a nontrivial element. Although progress has been made for other classes of groups , the problem for free groups has been regarded as an important open question in algorithmic group theory (see , , and the survey ).
The main result of this paper settles the problem.
Goldstein and Turner proved that if at least one of two homomorphisms between finitely generated free groups is injective, then their equalizer is finitely generated . Thus, the equalizers occurring in Theorem A are not pathological infinitely generated subgroups. They are finitely generated free groups, but there is no algorithm that determines whether their rank is zero.
Several consequences follow immediately.
In particular, the second assertion gives a negative answer to the Rank Problem posed by Stallings in 1984 concerning the computability of the rank of equalizers .
1.0.0.1 Fixed subgroups and equalizers.
The result contrasts sharply with the theory of fixed subgroups. If \(\alpha\colon F_A\longrightarrow F_A\) is an endomorphism, then \[\text{Fix}(\alpha) = \{x\in F_A\mid x\alpha=x\} = \operatorname{Eq}(\alpha,\operatorname{id})\] is a special case of an equalizer.
The study of fixed subgroups has a long history. Gersten and Cooper independently proved that the fixed subgroup of an automorphism of a finitely generated free group is finitely generated . Bestvina and Handel subsequently developed the theory of train tracks and proved Scott’s conjecture: if \(\alpha\) is an automorphism of a free group of rank \(n\), then \[\operatorname{rank}\text{Fix}(\alpha)\leq n\] . Imrich and Turner introduced stable images and extended these finite-generation and rank results to arbitrary endomorphisms .
The corresponding algorithmic problem is more complicated. Bogopolski and Maslakova constructed an algorithm computing a basis of the fixed subgroup of an automorphism . More recently, Mutanguha proved that stable images of free-group endomorphisms are computable , allowing the Bogopolski–Maslakova algorithm to be applied to arbitrary endomorphisms. Consequently, fixed subgroups of free-group endomorphisms are effectively computable and, in particular, their triviality is decidable. We refer to for a survey.
General equalizers are much more complicated. When neither of the two maps is injective, the equalizer may fail to be finitely generated. If one map is injective, finite generation is given by the theorem of Goldstein and Turner , but the corresponding rank and basis problems have remained open in general.
Stallings asked whether the rank of the equalizer of two injective endomorphisms of a free group of rank \(n\) is bounded above by \(n\). This was recently disproved by Lei and Zhang . He also asked whether the rank of an equalizer of two homomorphisms between finitely generated free groups is computable ; we refer to this as the Rank Problem. The problem of computing a free basis of the equalizer, the Basis Problem, was shown in to be equivalent to the Rank Problem.
Positive results are known for several restricted classes of homomorphisms . In rank two, Logan proved that finitely generated equalizers have rank at most two . Related questions concerning uniformly continuous extensions of endomorphisms to the boundary have also been studied in . Theorem A shows that these positive results cannot extend to arbitrary finitely generated free groups.
1.0.0.2 Virtual endomorphisms and complete transducers.
Non-computability persists when the domain is required to have finite index. We prove that there is no algorithm which, given a finite-index subgroup \(H \leq F\) and a homomorphism \[\theta \colon H \longrightarrow F,\] computes a basis for \(\operatorname{Fix}(\theta)\). Using a transducer associated with \(H\), we further show that the rationality theorem for fixed points of complete inverse transducers obtained by Silva is necessarily non-effective: no algorithm constructs a finite automaton recognizing their reduced fixed-point language. We conclude by relating the corresponding triviality problem to the existence of nontrivial fixed loops in complete inverse transducers.
1.0.0.3 Outline of the proof.
The proof reduces the halting problem of cyclic tag systems to the deciding triviality of the fixed-point set for finite inverse transducers and that to an instance of PCP for free groups. \[\begin{align} &\text{halting of cyclic tag systems}\\ \;\leq\; &\text{existence of nontrivial fixed points of finite inverse transducers}\\ \;\leq\; &\text{nontriviality of equalizers of free-group homomorphisms}. \end{align}\]
The first reduction is the main construction of the paper. A finite partial deterministic inverse transducer is a finite-state device which reads words over an alphabet with formal inverses and produces output words, with every transition accompanied by the corresponding inverse transition. After free reduction of the output, such a transducer \(\mathcal{T}\) defines a partial map \(\widetilde{\mathcal{T}}\) on a finitely generated free group. Inverse transducers have previously been used in the study of fixed points of free-group maps .
Given a cyclic tag system \(\mathcal{C}\), we effectively construct a finite partial deterministic inverse transducer \(\mathcal{T}_{\mathcal{C}}\). The construction uses the discrepancy \[\Delta(w) = w^{-1}\bigl(w\widetilde{\mathcal{T}}_{\mathcal{C}}\bigr)\] between the input read so far and its output. Along a distinguished path in the transducer, the freely reduced discrepancy acts as the queue of the tag system. Reading its first binary letter simulates one step of the cyclic tag system, while auxiliary marker letters record the number of simulated steps and prevent the discrepancy from collapsing to the identity.
If the tag system halts, its queue eventually contains only marker letters. These letters can then be cyclically read without changing the discrepancy, producing a nontrivial fixed loop in the transducer. We also prove that every nontrivial fixed point must be represented by a closed path. We can show that the existence of such a loop forces a repetition in the computation. The marker recording the number of steps excludes such a repetition when the tag system does not halt.
Since cyclic tag systems are Turing-complete , this gives the following intermediate result.
Theorem B 1. It is undecidable whether a finite partial deterministic inverse transducer has a nontrivial fixed point.
More precisely, from a cyclic tag system \(\mathcal{C}\), we effectively construct a finite partial deterministic inverse transducer \(\mathcal{T}_{\mathcal{C}}\) such that the following conditions are equivalent:
\(\mathcal{C}\) halts;
\(\mathcal{T}_{\mathcal{C}}\) has a nontrivial fixed loop at its distinguished state \(s\);
\(\text{Fix}\bigl(\widetilde{\mathcal{T}}_{\mathcal{C}}\bigr) \neq \{1\}.\)
Moreover, every fixed point of \(\widetilde{\mathcal{T}}_{\mathcal{C}}\) is represented by a closed path at \(s\). This last assertion is essential: it excludes fixed points arising from unintended paths and allows the second reduction to use the subgroup of closed input paths.
The second reduction is algebraic. Let \(\mathcal{T}=(Q,q_0,\delta,\lambda)\) be a finite partial inverse transducer, and let \[K = \{w\in F_A \mid w\text{ labels a closed input path at }q_0\}.\] The input automaton of \(\mathcal{T}\) is a finite inverse automaton, and hence \(K\) is a finitely generated subgroup of \(F_A\). A free basis \(B=\{b_1,\ldots,b_r\}\) of \(K\) can be computed from the corresponding Stallings automaton.
Let \(Y=\{y_1,\ldots,y_r\}.\) We define homomorphisms \[g,h\colon F_Y\longrightarrow F_A\] by letting \(y_i h=b_i\) and letting \(y_i g\) be the output produced by the transducer while reading the closed path labelled by \(b_i\). Since \(B\) is a free basis of \(K\), the homomorphism \(h\) is injective. Moreover, \[xg=xh\] holds for a nontrivial \(x\in F_Y\) precisely when \(xh\) labels a nontrivial fixed loop of \(\mathcal{T}\). Consequently, \[\operatorname{Eq}(g,h)\neq\{1\} \quad\Longleftrightarrow\quad \mathcal{T} \text{ has a nontrivial fixed loop at }q_0.\]
Combining this construction with Theorem B proves Theorem A. The construction is effective at every stage and preserves the injectivity of one of the two homomorphisms.
Since every finitely generated free group embeds in \(F_2\), undecidability persists for homomorphisms \[g,h\colon F_Y\longrightarrow F_2.\] By composing with suitable embeddings, the result can also be formulated for pairs of endomorphisms of a single finitely generated free group. The construction ensures that one of the maps is injective.
The paper is organized as follows. In Section 2 we introduce some basic notions on cyclic tag systems, partial inverse transducers, and the basic properties of discrepancies. In Section 3 we construct the transducer \(\mathcal{T}_{\mathcal{C}}\) associated with a cyclic tag system and prove Theorem B. In Section 4 we encode fixed loops of inverse transducers as equalizers of free-group homomorphisms and derive Theorem A. In Section 5, we derive several corollaries of the main result. In Section 6, we apply the main theorem to virtual endomorphisms and complete inverse transducers, proving two non-effectivity results and discussing the corresponding triviality problems.
2 Preliminaries and notation↩︎
We start by introducing preliminary results about cyclic tag systems and transducers. For further details, the reader is referred to .
2.1 Cyclic tag systems↩︎
A cyclic tag system \(\mathcal{C}\) is a tuple of words \((u_0,\ldots, u_{m-1})\) over \(\{0,1\}\), together with a starting word \(w_0\in\{0,1\}^*\) and a queue. The queue starts with \(w_0\) and evolves according to the following rule: if, at an instant \(i\), the queue has value \(u=au'\), with \(a\in \{0,1\}\), we update it to \(u'\alpha_i(a)\), where \(\alpha_i(a)=\varepsilon\) if \(a=0\) and \(\alpha_i(a)=u_{i \text{ mod m}}\) if \(a=1\).
We say that the system halts when the queue is empty. We will usually denote by \(W_n\) the value of the queue after \(n\) steps.
Cook showed that cyclic tag systems can emulate any tag system, which are Turing-complete. Hence, the halting problem for cyclic tag systems is undecidable.
2.2 Transducers↩︎
For a finite alphabet \(A\), put \(\widetilde{A}=A\cup A^{-1}.\) A word over \(\widetilde{A}\) represents an element of \(F_A\). For a word \(w\in \widetilde{A}^*\), let \(\overline{w}\) denote its freely reduced form, and let \(|w|\) denote the length of \(\overline{w}\). If \(w\neq1\), let \(\operatorname{first}(w)\) be the first letter of \(\overline{w}\). When there is no risk of confusion, we use the same notation for a word and the element of the free group that it represents.
A finite partial deterministic \(A\)-transducer is a quadruple \(\mathcal{T}=(Q,q_0,\delta,\lambda)\) where \(Q\) is a finite set of states, \(q_0\in Q\) is the initial state, and \(\delta:Q\times A\to Q\) and \(\lambda:Q\times A\to A^*\) are partial functions with the same domain. Both \(\delta\) and \(\lambda\) can be naturally extended to partial mappings \(Q\times A^*\to Q\) and \(Q\times A^*\to A^*\), respectively.
A finite partial deterministic \(\widetilde{A}\)-transducer is said to be inverse if \[p\xrightarrow{a|w} q \quad\text{ is an edge of \mathcal{T} if and only if } q\xrightarrow{a^{-1}|w^{-1}} p \quad\text{ is an edge of \mathcal{T}}.\]
A label can be seen as \(\mathrm{input}|\mathrm{output}\). A reduced path is one where the input label is a reduced word, that is, one without backtracking. Naturally, every nontrivial reduced closed path at the basepoint is labelled (on the input side) by a nontrivial reduced word. The following is an analogue of for partial transducers.
Lemma 1. Let \(\mathcal{T}=(Q,q_0,\delta,\lambda)\) be a finite partial deterministic inverse \(\widetilde{A}\)-transducer, and let \(\theta:\widetilde{A}^*\longrightarrow F_A\) be the natural projection. The partial mappings \(\delta\) and \(\lambda\) induce partial mappings \(\widetilde{\delta}\) and \(\widetilde{\lambda}\) on \(Q\times F_A\) with domain
\[\left\{ (q,g)\in Q\times F_A \;\middle|\; \overline{g} \text{ is readable from }q \right\}.\] Hence \[g\widetilde{\mathcal{T}} = (q_0,g)\widetilde{\lambda}\] defines a partial mapping \(\widetilde{\mathcal{T}}:F_A\rightharpoonup F_A\).
Proof. It is enough to prove that deleting a single freely reducible factor does not affect readability, the terminal state, or the output as an element of \(F_A\).
Suppose that \[u=xaa^{-1}y, \qquad x,y\in\widetilde{A}^*, \qquad a\in\widetilde{A},\] and that \(u\) is readable from \(q\). Put \(p=(q,x)\delta.\) Suppose that the edge read after \(x\) is \(p\xrightarrow{a\mid U}r.\) Since \(\mathcal{T}\) is inverse, the edge \(r\xrightarrow{a^{-1}\mid U^{-1}}p\) also belongs to \(\mathcal{T}\). Moreover, since \(\mathcal{T}\) is deterministic, this is the unique edge leaving \(r\) with input label \(a^{-1}\). It must therefore be the edge traversed by the factor \(a^{-1}\) in the readable word \(u\).
Thus the subpath labelled \(aa^{-1}\) returns from \(p\) to \(p\). Consequently, \(xy\) is readable from \(q\) and \((q,u)\delta=(q,xy)\delta.\) If \(X=(q,x)\lambda\) and \(Y=(p,y)\lambda,\) then \[(q,u)\lambda=XUU^{-1}Y, \qquad (q,xy)\lambda=XY.\] It follows that \[\bigl((q,u)\lambda\bigr)\theta = \bigl((q,xy)\lambda\bigr)\theta.\]
Iterating this argument over a sequence of free cancellations taking \(u\) to \(\overline{u}\) gives \((q,u)\delta=(q,\overline{u})\delta\) and \(\bigl((q,u)\lambda\bigr)\theta = \bigl((q,\overline{u})\lambda\bigr)\theta.\)
Hence the induced partial mappings are therefore well-defined. ◻
2.2.1 Fixed loops and discrepancies↩︎
Let \(\mathcal{T}\) be a finite inverse \(\widetilde{A}\)-transducer. Define \[\text{Fix}(\widetilde{\mathcal{T}})=\{w\in F_A\mid w\widetilde{\mathcal{T}}=w\}.\]
We say that \(w\in F_A\) is a fixed loop (at the basepoint) if \(w\in \text{Fix}(\widetilde{\mathcal{T}})\) and \((q_0,w)\delta=q_0\).
We define the discrepancy of a word \(w\in F_A\) that represents a readable path from the basepoint as \(w^{-1}w\widetilde{\mathcal{T}}\).
Throughout the paper, when reading a word, we will keep track of the discrepancy of the input as well as the state we are currently at and denote that by a pair \((d,q)\in F_A\times Q\), which we will call a discrepancy pair.
If, when reading a word, the current discrepancy is \(d\in F_A\) and an edge labelled \(a\mid U\) is crossed, the new discrepancy is \[\begin{align} d'&=\overline{a^{-1}dU}. \label{eq:update} \end{align}\tag{1}\] More generally, if we read a path \(\gamma\), the discrepancy is \[\begin{align} d'&=\overline{\operatorname{in}(\gamma)^{-1}d\,\operatorname{out}(\gamma)}, \label{eq:path-update} \end{align}\tag{2}\] where \(\operatorname{in}(\gamma)\) is the input label of \(\gamma\) and \(\operatorname{out}(\gamma)\) is the output label.
Starting with discrepancy \(1\), a closed path \(\gamma\) is a fixed loop if and only \((q_0,\gamma)\delta=q_0\) and its final discrepancy is \(1\)
3 Construction of a partial transducer from a cyclic tag system↩︎
The purpose of this section is to describe a construction of a finite partial deterministic inverse transducer associated to a cyclic tag system so that the system halts if and only if the transducer has a nontrivial fixed point. Moreover, the transducer will have the property that all fixed points will be, in fact, fixed loops at the initial state.
Fix a cyclic tag system \(\mathcal{C}=(u_0,\ldots,u_{m-1})\) with initial word \(w_0\). Let \[A=\{0,1,\#,H,p\}, \qquad Q=\{s,0,1,\ldots,m-1\}.\]
When we write \(i\) to refer to an element of \(Q\) we always mean \(i\) mod \(m\). Let \(\delta:Q\times A\rightharpoonup Q\) be defined as:
\((s,\#)\delta=0\);
for \(i\in \{0,\ldots, m-1\}\) \((i,0)\delta=(i,1)\delta=i+1\) and \((i,H)\delta=(i,p)\delta=i\);
and with the remaining transitions undefined.
Also, let \(\lambda:Q\times A\rightharpoonup A^*\) be defined as:
\((s,\#)\lambda=\#w_0p\);
for \(i\in \{0,\ldots, m-1\}\) \((i,0)\lambda=H\), \((i,1)\lambda=u_iH\), \((i,H)\lambda=H\) and \((i,p)\lambda=p\);
and with the remaining transitions undefined. We now add all inverse-letter transitions to obtain a partial finite inverse transducer \(\mathcal{T}_{\mathcal{C}}\).
It is easy to check that \(\mathcal{T}_{\mathcal{C}}\) is indeed a finite partial inverse transducer.
Let \(e_{\#}\) denote the edge \(s\xrightarrow{\#\mid\#w_0p}0.\) Starting from the discrepancy pair \((1,s)\) and reading \(e_{\#}\) gives \[\left(\overline{\#^{-1}(\#w_0p)},0\right) =(w_0p,0).\] Put \(d_0=w_0p\). Suppose that the current discrepancy pair is \((aR,i)\), where \(a\) is the first letter of the word \(aR\), and suppose that the edge leaving \(i\) with input label \(a\) has output \(U\). Formula 1 gives \[(aR,i)\longmapsto(RU,r),\] where \(r\) is the terminal state of the edge. Thus the first letter is removed and the output is appended.
Define a homomorphism \[\beta:\{0,1,H,p\}^*\longrightarrow\{0,1\}^*\] by \[\beta(0)=0, \qquad \beta(1)=1, \qquad \beta(H)=\beta(p)=\varepsilon.\] For a positive word \(V\), let \(|V|_H\) and \(|V|_p\) denote the numbers of occurrences of \(H\) and \(p\) in \(V\).
Starting from \((d_0,0)\), repeatedly read the first letter of the word in the current pair. Every pair obtained in this way has the form \((d,i)\) with \[d\in\{0,1,H,p\}^+, \qquad i\in\{0,\ldots,m-1\}.\] Indeed, all outputs (and the starting word) are positive, and the word always contains exactly one occurrence of \(p\). Put \((D_0,i_0)=(d_0,0).\) If \((D_n,i_n)\) is defined, whenever we read a letter from \(\{0,1\}\), we define \((D_{n+1},i_{n+1})\) to be the new pair carrying the discrepancy and the current state. Whenever we read \(\#\), \(H\), or \(p\) we don’t define a successor in this new sequence.
Lemma 2. For every \(n\) for which \((D_n,i_n)\) is defined, we have that \[i_n=n\bmod m, \qquad \beta(D_n)=W_n, \qquad |D_n|_H=n, \qquad \text{ and } \qquad |D_n|_p=1,\] where \(W_n\) is the queue of the cyclic tag system after \(n\) steps. Moreover, \((D_{n+1},i_{n+1})\) is defined if and only if \(W_n\neq\varepsilon\).
Proof. For \(n=0\), we have \(D_0=w_0p\) and \(i_0=0\), so all assertions are immediate.
Assume that the assertions hold for some \(n\). If \(W_n=\varepsilon\), then \(\beta(D_n)=\varepsilon\), so \(D_n\) has no binary letter. Therefore, we never read another binary letter and the successor is not defined.
Suppose that \(W_n\neq\varepsilon\). There is a unique factorization \[\label{eq:Dn-factorization} D_n=ZaR,\tag{3}\] where \(Z\in\{H,p\}^*,\) and \(a\in\{0,1\}.\)
Read the letters of \(Z\) in order. The edges on \(H\) and \(p\) leave the state unchanged and output the letter that they read. The resulting pair after reading \(Z\) is thus \((aRZ,i_n).\)
If \(a=0\), the next edge has label \(0\mid H\) and gives \((RZH,i_n+1).\)
If \(a=1\), the next edge has label \(1\mid u_{i_n}H\) and gives \((RZu_{i_n}H,i_n+1).\)
Applying \(\beta\) gives exactly the two cases of the cyclic tag rule. In both cases the state increases by one, one new \(H\) is added, and the unique occurrence of \(p\) is preserved. ◻
Proposition 1. Consider the sequence of discrepancy pairs obtained from \((d_0,0)\) by repeatedly reading the first letter of the word in the current pair.
If \(\mathcal{C}\) does not halt, the sequence is infinite and no pair occurs twice.
If \(\mathcal{C}\) halts, the sequence reaches a pair \((D,i)\) with \(D\in\{H,p\}^+.\) Reading the letters of \(D\) in order returns to the same pair \((D,i)\).
Proof. Suppose first that \(\mathcal{C}\) does not halt. Then \(W_n\neq\varepsilon\) for every \(n\), so \((D_n,i_n)\) is defined for every \(n\).
After the \(n\)-th binary letter has been read and before the next binary letter is read, every word in the sequence contains exactly \(n\) occurrences of \(H\). Indeed, after the \(n\)-the binary letter is read, the sequence has value \((D_n,i_n)\) and reading \(H\) or \(p\) does not change the number of \(H\)’s in the discrepancy component. Therefore, if a pair appears twice in the sequence, both occurrences must be between the reading of the \(n\)-th and the \(n+1\)-th binary letters, for some \(i\). Now, write \(D_n=ZaR\) as in 3 . Before \(a\) is read, the sequence moves the letters of \(Z\) from the beginning to the end, one at a time. At each step, the number of letters from \(\{H,p\}\) before the first binary letter decreases by one. Hence no word, and therefore no pair, occurs twice in this part of the sequence.
Suppose now that \(\mathcal{C}\) halts after \(n\) steps. Then \(W_n=\varepsilon\), so \(D_n\in\{H,p\}^+\). It is nonempty because it contains the unique occurrence of \(p\). Put \(D=D_n\) and \(i=i_n\). Reading an initial \(H\) or \(p\) moves that letter to the end and leaves the state unchanged. Reading all letters of \(D\) therefore returns to \((D,i)\). ◻
Remark 2. The letters \(H\) and \(p\) have different roles. Every binary transition appends one \(H\) to the discrepancy, and the number of occurrences of \(H\) records the number of binary steps. The letter \(p\) occurs once in the initial word and is preserved by every transition used in the simulation. It keeps the current discrepancy nontrivial.
12 Define a homomorphism \(\chi:F_A\longrightarrow\mathbb{Z}\) by \[\chi(p)=1, \qquad \chi(a)=0 \quad(a\in A\setminus\{p\}).\] So \(\chi\) denotes the exponent-sum of \(p\). For every edge \(q\xrightarrow{a\mid U}r\) whose endpoints are numbered states, one has \[\label{eq:chi-preserved} \chi(a)=\chi(U).\tag{4}\] Consequently, if this edge changes \((d,q)\) to \((e,r)\), then \[\chi(e)=-\chi(a)+\chi(d)+\chi(U)=\chi(d).\] Since \(\chi(d_0)=1\), every pair reached from \((d_0,0)\) by a path among the numbered states has a nontrivial discrepancy.
Before proving the main theorem of this section, we present two technical lemmas.
Lemma 3. Let \(i\xrightarrow{a\mid U}j\) be an edge between numbered states, and suppose it changes \((d,i)\) to \((e,j)\), where \(\chi(d)=1\). If \[a\neq\operatorname{first}(d),\] then \[\operatorname{first}(e)=a^{-1}.\]
Proof. The word \(a^{-1}d\) is freely reduced and begins with \(a^{-1}\). It is easy to see that multiplication by \(U\) on the right cannot cancel this first letter. Indeed, \(a^{-1}d\) contains a \(p\) and if \(a\not\in\{p,p^{-1}\}\), then \(U\) contains no \(p^{-1}\) to cancel that \(p\) and the initial \(a^{-1}\) survives cancellation. If \(a\in\{p,p^{-1}\}\), then \(U=a\) and so \(U\) has length one and it cannot cancel the initial \(a^{-1}\) as \(d\) is nontrivial. ◻
The next lemma concerns an arbitrary closed path, not necessarily the path obtained by repeatedly reading the first letter.
Lemma 4. Let \(\rho\) be a nonempty reduced closed path at state \(0\) that uses only the numbered states. If reading \(\rho\) from \((d_0,0)\) returns to \((d_0,0)\), then the sequence obtained from \((d_0,0)\) by repeatedly reading the first letter contains the same pair at two different times.
Proof. Write \(\rho=e_1\cdots e_k,\) and let \[(d_0,0),(d_1,i_1),\ldots,(d_{k-1},i_{k-1}), (d_0,0)\] be the successive pairs obtained while reading \(\rho\) from \((d_0,0)\). By 4 , \[\chi(d_j)=1 \qquad(0\leq j\leq k).\] In particular, every \(d_j\) is nontrivial.
For \(1\leq j\leq k\), let \(a_j\) be the input label of \(e_j\). We say that the edge \(e_j\) is positive if \[a_j=\operatorname{first}(d_{j-1}),\] and negative otherwise. If \(e_j\) negative, Lemma 3 gives \[\operatorname{first}(d_j)=a_j^{-1}.\] Thus the reverse edge \(e_j^{-1}\) reads the first letter from \((d_j,i_j)\).
A negative edge cannot be followed by a positive one. Indeed, if \(e_j\) is negative and \(e_{j+1}\) is positive,then both \(e_j^{-1}\) and \(e_{j+1}\) have as input \(\operatorname{first}(d_j)\). Determinism would give \(e_{j+1}=e_j^{-1},\) which contradicts the fact that \(\rho\) is reduced.
It follows that, for some \(r\in\{0,\ldots,k\}\), the first \(r\) edges are positive and the remaining are negative.
If \(r=k\), then \(\rho\) is an initial part of the sequence obtained by repeatedly reading the first letter and returns to \((d_0,0)\). If \(r=0\), then \(\rho^{-1}\) has this property. In either case, the sequence repeats \((d_0,0)\).
Assume that \(0<r<k\). The path \(e_1\cdots e_r\) is an initial part of the sequence obtained by repeatedly reading the first letter from \((d_0,0)\) to \((d_r,i_r)\). The path \(e_k^{-1}\cdots e_{r+1}^{-1}\) is another initial part of the same sequence with the same endpoints. If these paths have different lengths, the sequence reaches \((d_r,i_r)\) at two different times. If they have the same length, determinism implies that they are equal edge by edge. Their last edges are then equal, so \(e_r=e_{r+1}^{-1},\) again contradicting the reducedness of \(\rho\). Thus the sequence repeats a pair. ◻
Theorem 3. From a cyclic tag system \(\mathcal{C}\), one can effectively construct a finite partial deterministic inverse transducer \(\mathcal{T}_{\mathcal{C}}\) such that the following conditions are equivalent:
\(\mathcal{C}\) halts;
\(\mathcal{T}_{\mathcal{C}}\) has a nontrivial fixed loop at \(s\);
\(\text{Fix}(\widetilde{\mathcal{T}}_{\mathcal{C}})\neq\{1\}\).
Moreover, if \(g\in\text{Fix}(\widetilde{\mathcal{T}}_{\mathcal{C}})\), then the freely reduced representative of \(g\) labels a closed path at \(s\).
Proof. We first prove the last assertion. Let \(g\) be fixed, and let \(w\) be its freely reduced representative. Since \(w\) is freely reduced, its path is reduced. If \(w\) is empty, it is already a closed path at \(s\). Suppose that \(w\) is nonempty. The only edge leaving \(s\) is \(e_{\#}\), so the path begins with that edge and the discrepancy pair is \((d_0,0)\). If the path ended at a numbered state, its final first coordinate would have \(p\)-exponent sum one by 4 . This is impossible because \(g\) is fixed, so it has trivial discrepancy. Therefore the path returns to \(s\) through \(e_{\#}^{-1}\). It cannot leave \(s\) again, because the only possible next edge would be \(e_{\#}\), giving an immediate reversal. Hence the path ends at \(s\).
It follows immediately that conditions (ii) and (iii) are equivalent: a fixed loop is a fixed point, and every fixed point is represented by a loop at \(s\).
Suppose that \(\mathcal{C}\) halts. By Proposition 1, the sequence obtained by repeatedly reading the first letter starting from \((d_0,0)\) reaches a pair \((D,i)\) with \(D\in\{H,p\}^+\), and reading the letters of \(D\) returns to \((D,i)\). Let \(\tau\) be the path from \((d_0,0)\) to \((D,i)\), and let \(\sigma\) be the closed path at state \(i\) whose input (and output) word is \(D\). Therefore \[\begin{align} (1,s) \xrightarrow{e_{\#}}(d_0,0) \xrightarrow{\tau}(D,i) \xrightarrow{\sigma}(D,i) \xrightarrow{\tau^{-1}}(d_0,0) \xrightarrow{e_{\#}^{-1}}(1,s). \end{align}\] is a closed path at \(s\) which sends \((1,s)\) to itself. It is therefore a fixed loop. Its input label represents a conjugate of the nonempty positive word \(D\), and is nontrivial. This proves (i)\(\Rightarrow\)(ii).
Conversely, suppose that \(\mathcal{C}\) does not halt and that there is a nontrivial fixed reduced loop at \(s\). Since \(s\) is incident with only the geometric edge \(e_{\#}\), the reduced loop has the form \(e_{\#}\rho e_{\#}^{-1},\) where \(\rho\) is a nonempty reduced closed path at state \(0\) using only the numbered states.
Suppose that reading \(\rho\) from \((d_0,0)\) gives \((e,0)\). The inverse entry edge has label \[\#^{-1}\mid d_0^{-1}\#^{-1}.\] Since the full path is fixed, 1 gives \[1=\overline{\# e d_0^{-1}\#^{-1}},\] and therefore \(e=d_0\). Thus \(\rho\) sends \((d_0,0)\) to itself. Lemma 4 implies that the first-letter sequence repeats a pair, and so \(\mathcal{C}\) halts by Proposition 1(i), which is absurd. ◻
Since the halting problem is undecidable for cyclic tag systems, we have the following corollary.
Corollary 1. It is undecidable whether a finite partial deterministic inverse transducer has a nontrivial fixed point.
4 The Post Correspondence Problem for free groups↩︎
The purpose of this section is to show that the problem of deciding the existence of a nontrivial fixed loop in a finite partial deterministic inverse transducer can be reduced to an instance of the PCP for free groups. This, together with the main result from the previous section, leads to the undecidability of the PCP for free groups.
Theorem 4. From a finite partial inverse \(\widetilde{A}\)-transducer \(\mathcal{T}=(Q,q_0,\delta, \lambda)\), one can effectively construct a finite set \(Y\), and homomorphisms \[g,h:F_Y\longrightarrow F_A\] between two free groups such that \(h\) is injective and \[\operatorname{Eq}(g,h)\neq\{1\} \quad\Longleftrightarrow\quad \mathcal{T}\text{ has a nontrivial fixed loop at }q_0.\]
Proof. Forget the output labels of \(\mathcal{T}\) and consider only its input-labelled automaton. Let \[K= \{w\in F_A\mid (q_0,w)\widetilde{\delta}=q_0\}\] be the set of elements of \(F_A\) which label closed paths at \(q_0\).
The set \(K\) is a subgroup of \(F_A\). Indeed, the product of two closed paths is a closed path, and the inverse of a closed path is again a closed path.
Consider the connected component of the input automaton containing \(q_0\). Since it is is finite, deterministic, and inverse, it is a finite Stallings automaton for \(K\), after removing any edges which don’t occur in any reduced closed path at \(q_0\).
Therefore one can effectively compute a finite free basis \(B\) of \(K\). Let \(B=\{b_1,\ldots,b_r\}\) be such a basis, and let \[Y=\{y_1,\ldots,y_r\}\] be a new alphabet.
Define \(\psi=\widetilde{\mathcal{T}}|_K\). That is, \(\psi:K\longrightarrow F_A\) is defined by \(w\psi=w\widetilde{\mathcal{T}}.\) This is a homomorphism. Indeed, if \(u,v\in K\), then reading \(u\) returns the transducer to \(q_0\). Hence \[(uv)\psi = (uv)\widetilde{\mathcal{T}} = (u\widetilde{\mathcal{T}}) (v\widetilde{\mathcal{T}}) = (u\psi)(v\psi).\]
Let \(F_Y\) be the free group with basis \(Y\). Define homomorphisms \(g,h:F_Y\longrightarrow F_A\) by \[y_ih=b_i \qquad\text{and}\qquad y_ig=b_i\psi \qquad (1\leq i\leq r).\]
Since \(B\) is a free basis of \(K\), the homomorphism \(h\) is injective and \(F_Yh=K.\) Moreover, by construction, \[\label{eq:g-psi-h} xg=(xh)\psi\tag{5}\] for every \(x\in F_Y\).
Suppose first that there is some nontrivial \(x\) in \(\operatorname{Eq}(g,h).\) Put \(w=xh.\) Since \(h\) is injective, \(w\neq1\) and, since \(w\in K\), \(w\) labels a closed path at \(q_0\). By 5 , \[w\widetilde{\mathcal{T}} = w\psi = xg = xh = w.\] Thus \(w\) is a nontrivial fixed loop at \(q_0\).
Conversely, suppose that \(w\) is a nontrivial fixed loop at \(q_0\). Then \(w\in K\) and \(w\psi=w.\) Since \(h\) maps \(F_Y\) isomorphically onto \(K\), there exists \(x\in F_Y\) such that \(xh=w.\) The element \(x\) is nontrivial because \(w\neq1\) and \(h\) is injective. Using 5 , we obtain \(xg = (xh)\psi = w\psi = w = xh.\) Hence \[1\neq x\in\operatorname{Eq}(g,h).\]
Finally, the construction is effective. From the finite input automaton one can compute a free basis \(B\) of \(K\). For each \(b_i\in B\), one can read the corresponding closed path from \(q_0\) and compute its output label. These words are precisely the images of the generators under \(h\) and \(g\). ◻
Corollary 2. The PCP is undecidable for free groups.
5 Some consequences of the undecidability of PCP↩︎
In this section, we derive several consequences of the undecidability of the Post Correspondence Problem. The first two are the undecidability of the Rank and Basis Problems, which are immediate as they would solve PCP.
Corollary 3. There is no algorithm which, given homomorphisms \(g,h:F_\Sigma\to F_\Delta\) with at least one of \(g,h\) injective, outputs a basis for \(\operatorname{Eq}(g,h).\)
Corollary 4. There is no algorithm which, given homomorphisms \(g,h:F_\Sigma\to F_\Delta\) with at least one of \(g,h\) injective, outputs the rank of \(\operatorname{Eq}(g,h).\)
Since every free group embeds in \(F_2\) (and in any free group of rank at least 2), we observe that the PCP is still undecidable when we restrict ourselves to homomorphisms with \(F_2\) as the codomain or to endomorphisms.
Corollary 5. The Post Correspondence Problem is undecidable for pairs \[g,h:F_Y\longrightarrow F_2,\] even when \(h\) is injective.
Proof. Let \(g,h:F_Y\to F_A\) be two homomorphisms between free groups, with \(h\) injective. Let \(\iota:F_A\longrightarrow F_2\) be an injective homomorphism. Define \[g'= g\iota, \qquad h'= h\iota.\] Injectivity of \(\iota\) gives \[\operatorname{Eq}(g',h')=\operatorname{Eq}(g,h),\] and \(h'\) is injective. ◻
Corollary 6. There is no algorithm which, given two endomorphisms \[\alpha,\beta:F_Y\longrightarrow F_Y\] of a finitely generated free group, with \(\beta\) injective, decides whether \(\operatorname{Eq}(\alpha,\beta)\) is nontrivial.
Proof. Let \(g,h:F_Y\to F_A\) be two homomorphisms between free groups, with \(h\) injective. Let \(\iota:F_A\longrightarrow F_Y\) be an injective homomorphism. As above, defining \[g'= g\iota, \qquad h'= h\iota,\] we have that \[\operatorname{Eq}(g',h')=\operatorname{Eq}(g,h),\] and \(h'\) is injective. ◻
We now prove that, although the fixed subgroup of an endomorphism of the free group is computable, the same cannot be said about homomorphisms between a subgroup \(H\) of a free group \(F\) and \(F\). In fact, not even triviality can be decided.
Corollary 7. There is no algorithm which, given a finitely generated subgroup \(K\leq F_A\) and a homomorphism \(\theta:K\longrightarrow F_A,\) decides whether \(\text{Fix}(\theta)\) contains a nontrivial element.
Proof. Let \(g,h:F_Y\longrightarrow F_A\) be homomorphisms with \(h\) injective. Put \(K=\text{Im}(h)\leq F_A.\) The subgroup \(K\) is finitely generated.
Since \(h:F_Y\to K\) is an isomorphism, define \(\theta:K\longrightarrow F_A\) by \(x\theta=xh^{-1}g\). This is a well-defined homomorphism. For every \(x\in F_Y\), \[xh\in\text{Fix}(\theta) \quad\Longleftrightarrow\quad xg=xh.\] Therefore \[\text{Fix}(\theta)=\bigl(\operatorname{Eq}(g,h)\bigr)h.\] Since \(h\) is injective, \(\text{Fix}(\theta)\) is nontrivial if and only if \(\operatorname{Eq}(g,h)\) is nontrivial. ◻
The following corollary follows directly from and Corollary 2.
Corollary 8. There is no algorithm that takes as input two free groups \(F_n\) and \(F_m\), and two endomorphisms \(\phi,\psi\in \text{End}(F_n\times F_m)\) that decides whether \(\text{Fix}(\varphi)\cap \text{Fix}(\psi)\) is trivial or not
We then have that there is an algorithm taking as input a monomorphism and an endomorphism of \(F_n\times F_m\) that decides if their intersection is trivial or not , but when we remove the injectivity assumption, the problem becomes undecidable.
6 Complete transducers and virtual endomorphisms↩︎
When the subgroup \(H\) in Corollary 7 is not only finitely generated but also of finite index, we can still deduce from PCP that the fixed subgroup is not computable. We conjecture that triviality cannot be decided as well. A homomorphism \(\phi:H\to G\) where \(H\) is a finite index subgroup of \(G\) is said to be a virtual endomorphism
Theorem 5. There is no algorithm which, given a finitely generated free group \(F\), a finite-index subgroup \(H\leq F\), and a virtual endomorphism \(\theta\colon H\longrightarrow F\) of \(F\), computes \(\text{Fix}(\theta)\).
Proof. We start by considering the construction from the proof of Corollary 7
Let \(g,h\colon F_Y\longrightarrow F_A\) be an instance of the Post Correspondence Problem in which \(h\) is injective. Put \[K=\text{Im}(h)\leq F_A.\] Since \(h\) is injective, it induces an isomorphism \(h\colon F_Y\longrightarrow K.\) Define a homomorphism \(\theta\colon K\longrightarrow F_A\) by \[x\theta=xh^{-1}g.\] We have that, for \(x\in F_Y\), \[xh\in\text{Fix}(\theta) \quad\Longleftrightarrow\quad xg=xh,\] and therefore \[\text{Fix}(\theta)=\operatorname{Eq}(g,h)h.\] In particular, \[\text{Fix}(\theta)\neq\{1\} \quad\Longleftrightarrow\quad \operatorname{Eq}(g,h)\neq\{1\}.\]
By Marshall Hall’s Theorem, we embed \(K\) as a free factor of a finite-index subgroup \(H\) of \(F_A\) and compute a basis \(\mathcal{B}\sqcup\mathcal{C}\) of \(H\), where \(\mathcal{B}\) is a free basis of \(K\).
We extend \(\theta\) to a homomorphism \(\widehat{\theta}\colon H\longrightarrow F_A\) by defining \[b\widehat{\theta}=b\theta \qquad (b\in\mathcal{B}) \qquad \text{ and } \qquad c\widehat{\theta}=1 \qquad (c\in\mathcal{C}).\]
Suppose that we could compute \(\text{Fix}(\widehat{\theta}).\) We could then compute \[\text{Fix}(\widehat{\theta})\cap K = \text{Fix}(\theta)\] and decide whether \(\text{Fix}(\theta)\) is trivial, and so if \(\operatorname{Eq}(g,h)\) is trivial. ◻
We conjecture that triviality is also undecidable.
Conjecture 6. There is no algorithm which, given a finitely generated free group \(F\), a finite-index subgroup \(H\leq F\), and a homomorphism \(\theta\colon H\longrightarrow F,\) decides whether \(\text{Fix}(\theta)=\{1\}.\)
Fixed subgroups of virtual endomorphisms are closely related to fixed loops of complete inverse transducers. Silva proved in that for every finite complete inverse transducer \(\mathcal{T}\), the set \(\text{Fix}(\widetilde{\mathcal{T}})\) was a rational subset of the free group, which, from Benois’s Theorem means only that the language of all reduced words representing elements of \(\text{Fix}(\widetilde{\mathcal{T}})\) is rational . The next result shows that Theorem 5 implies that this regular language cannot be constructed effectively from \(\mathcal{T}\).
Corollary 9. There is no algorithm which, given a finite complete deterministic inverse transducer \(\mathcal{T}\), constructs a finite automaton recognizing the language of reduced words representing elements of \(\text{Fix}(\widetilde{\mathcal{T}})\).
Proof. Let \(F_A\) be a finitely generated free group, let \(H\leq F_A\) be a finite-index subgroup, and let \(\theta:H\longrightarrow F_A\) be a homomorphism. We will effectively construct a finite complete inverse transducer \(\mathcal{T}_\theta\) such that \[H\cap\operatorname{Fix}(\widetilde{\mathcal{T}_\theta}) = \operatorname{Fix}(\theta).\]
This suffices to show the result as \(\text{Fix}(\theta)\) is not computable and we can compute a finite automaton recognizing the reduced words representing elements of \(H\). Consider the finite set of right cosets \(Q=H\backslash F_A,\) and take \(q_0=H\) as the initial state. Compute a right transversal \(\{t_q:q\in Q\}\) such that \(q=Ht_q\) and \(t_{q_0}=1\).
For \(q\in Q\) and \(a\in\widetilde{A}\), put \[q\cdot a=Ht_qa\]
Since \(Ht_qa=Ht_{q\cdot a},\) we have that \[t_qa\,t_{q\cdot a}^{-1}\in H.\]
For every \(q\in Q\) and \(a\in\widetilde{A}\), define the transition \[q \xrightarrow{\;a\mid (t_qa\,t_{q\cdot a}^{-1})\theta \;} q\cdot a.\] It is easy to see that this gives a finite complete deterministic transducer.
We now compute the output of this transducer on an element of \(H\). Let \(w=a_1\cdots a_n\) be a reduced word, and put \(q_j=H a_1\cdots a_j\) for \(0\leq j\leq n\).
Thus \(q_0=H\). We have that \[\begin{align} \prod_{j=1}^{n} t_{q_{j-1}}a_jt_{q_{j-1}\cdot a_j} &= \prod_{j=1}^{n} \bigl(t_{q_{j-1}}a_jt_{q_j}^{-1}\bigr) \\ &= a_1\cdots a_n t_{q_n}^{-1} \\ &= wt_{q_n}^{-1}. \end{align}\] If \(w\in H\), then \(q_n=q_0\) and \(t_{q_n}=1\). Hence the path labelled by \(w\) returns to \(q_0\), and its output represents \(w\theta.\) Therefore, for every \(w\in H\), \(w\widetilde{\mathcal{T}_\theta}=w\theta.\) It follows that \[\begin{align} H\cap\operatorname{Fix}(\widetilde{\mathcal{T}_\theta}) &= \{w\in H:w\widetilde{\mathcal{T}_\theta}=w\} \\ &= \{w\in H:w\theta=w\} \\ &= \operatorname{Fix}(\theta), \end{align}\] ◻
The proof above shows that the fixed subgroup of a virtual endomorphism can be seen as the fixed loops of a finite inverse transducer, so Conjecture 6 can be reduced to deciding if a finite inverse transducer has nontrivial fixed loops. We show that the two are indeed equivalent
Proposition 7. The following decision problems are effectively equivalent.
Given a finite-index subgroup \(H\leq F_A\) and a homomorphism \(\theta:H\longrightarrow F_A,\) decide whether \(\text{Fix}(\theta)=\{1\}.\)
Given a finite complete deterministic inverse transducer \(\mathcal{T}\), with initial state \(q_0\), decide whether \(\mathcal{T}\) has a nontrivial fixed loop.
Proof. It follows from the proof of Corollary 9 that we can reduce 1 to 2.
Suppose now that \(\mathcal{T}=(Q,q_0,\delta,\lambda)\) is a finite complete deterministic inverse transducer over \(\widetilde{A}\).
Since \(\mathcal{T}\) is complete and inverse, every element of \(F_A\) acts on \(Q\). Let \[H_{\mathcal{T}} = \left\{ w\in F_A:(q_0,w)\widetilde{\delta}=q_0 \right\}\] be the stabilizer of \(q_0\). The orbit of \(q_0\) is finite, and therefore \([F_A:H_{\mathcal{T}}]<\infty.\)
For \(w\in H_{\mathcal{T}}\), define \[w\theta_{\mathcal{T}}=w\widetilde{\mathcal{T}}.\] The map \(\theta_{\mathcal{T}}:H_{\mathcal{T}}\longrightarrow F_A\) is a homomorphism. Indeed, if \(u,v\in H_{\mathcal{T}}\), then reading \(u\) returns the transducer to \(q_0\), and hence \[(uv)\widetilde{\mathcal{T}} = (u\widetilde{\mathcal{T}}) (v\widetilde{\mathcal{T}}).\] Consequently, \[\begin{align} \text{Fix}(\theta_{\mathcal{T}}) &= \left\{ w\in H_{\mathcal{T}}:w\theta_{\mathcal{T}}=w \right\} \\ &= \left\{ w\in F_A: (q_0,w)\widetilde{\delta}=q_0 \text{ and } w\widetilde{\mathcal{T}}=w \right\}, \end{align}\] that is \(\text{Fix}(\theta_{\mathcal{T}})\) is the set of fixed loops. Hence 2 is also reducible to 1 and the problems are equivalent. ◻
So, Conjecture 6 is equivalent to showing that it is undecidable whether a finite complete inverse transducer has a nontrivial fixed loop. We also conjecture that it is undecidable whether a finite complete inverse transducer has a nontrivial fixed point
Conjecture 8. There is no algorithm which, given a finite complete deterministic inverse transducer \(\mathcal{T}\) with initial state \(q_0\), decides whether \(\text{Fix}(\widetilde{\mathcal{T}})\) is trivial.
Acknowledgements↩︎
The author was supported by national funds through the Fundação para a Ciência e a Tecnologia, FCT, under the project UID/04674/2025.