Probabilistic Finite Automaton Emptiness Is Undecidable for a Fixed Automaton

Formally, a PFA is given by a sequence of stochastic transition matrices $M_{\sigma }$, one for each letter $\sigma$ from the input alphabet $\mathrm{\Sigma }$. The states correspond to the rows and columns of the matrices. Thus, the matrices are $d\times d$ matrices for a PFA with $d$ states. The start state is chosen according to a given probability distribution $\pi \in {ℝ}^d$. The set of accepting states is characterized by a 0-1-vector $f\in {\{0,1\}}^d$. In terms of these data, the PFA Emptiness Problem with cutpoint $\lambda$ is as follows:

PFA Emptiness. Given a set of $k$ stochastic matrices $ℳ=\{M_1,\mathrm{\dots },M_k\}\subset {\mathbb{Q}}^{d\times d}$, a probability distribution $\pi \in {\mathbb{Q}}^d$, and a 0-1-vector $f\in {\{0,1\}}^d$, is there a sequence $i_1,i_2,\mathrm{\dots },i_m$ with $1\le i_j\le k$ for $j=1,\mathrm{\dots },m$ such that

$${\pi }^T{M}_{i_1}{M}_{i_2}\mathrm{\dots }{M}_{i_m}f>\lambda \mathrm{?}$$

(1)

The most natural choice is $\lambda =\frac{1}{2}$, but the problem is undecidable for any fixed (rational or irrational) cutpoint $\lambda$ with . We can also ask $\ge \lambda$ instead of $>\lambda$.

There are three different proofs of the basic undecidability theorem in the literature. The first proof is due to Masakazu Nasu and Namio Honda [17] from 1969.¹¹1This proof is commonly misattributed to Paz [20], although Paz gave credit to Nasu and Honda [20, Section IIIB.7, Bibliographical notes, p. 193]. The second proof, by Volker Claus [5], is loosely related to this proof. Both proofs use a reduction from the Post Correspondence Problem (PCP, see Section 1.4). A completely independent proof with a very different approach, namely a reduction from the halting problem for 2-counter machines, was given by Anne Condon and Richard J. Lipton [6] in 1989, based on ideas of Rūsiņš Freivalds [9] from 1981. The somewhat intricate history is described in [21, Section 3] as part of an extensive survey of the various undecidability proofs.

PFA Emptiness remains undecidable under various constraints on the number of transition matrices (size of the alphabet) and their size (number of states). The first result in this direction is due to Claus [5] from 1981. Later improvements were made by Blondel and Canterini [1] and Hirvensalo [13], who were apparently unaware of [5] and concentrated on the case of two matrices (binary input alphabet). An overview of these results is shown in Table 1 below the double line.

We improve these bounds, concentrating on the minimum number of states without restricting the number of matrices, see Theorem 1. (Such results are only implicit in the proofs of [1] and [13].) Undecidability even holds for a PFA where all data except the starting distribution $\pi$ are fixed.

We also get improved bounds for the 2-matrix case. For the variation where the output vector $f$ is not restricted to a 0-1-vector, we can reduce the number of states to 6 (Theorem 2).

Our results are stated in the following theorems and summarized in Table 1.

By combining the different proof techniques, one can extend Theorem 2 to PFAs with two matrices and a fixed start state or starting distribution, analogous to Theorem 1c–d, but we have not worked out these results.

Some weaker results with fixed matrices were previously obtained in a technical report [21, Theorems 2 and 4]. For example, PFA Emptiness was shown to be undecidable for 52 fixed $9\times 9$ matrices, in the setting of Theorem 2 where the final vector $f$ is the only input, with acceptance criterion $\ge 1/2$. For acceptance with strict inequality ($>1/4$), 52 fixed matrices of size $11\times 11$ were needed. In these constructions, the PCP was derived from a universal Turing machine. For the case of 2 fixed matrices with a single accepting state, where the start distribution $\pi$ is the only input, a bound of 572 states was obtained [21, Theorem 3].

The most striking result of the paper is that PFA Emptiness is undecidable already for a fixed PFA, where only the starting distribution $\pi$, or the output vector $f$ is an input. This follows from a combination of known ideas: The main observation, namely that the reduction of Matiyasevich and Sénizergues [16] from undecidable semi-Thue systems leads to instances of the Post Correspondence problem (PCP) where only the starting pair is variable, has been made by Halava, Harju, and Hirvensalo in 2007 [12, Theorem 6]. The idea of merging the first or last matrix into the starting distribution $\pi$ or into the final vector $f$ was used by Hirvensalo in 2007 [13, Step 2 in Section 3].

On the technical side, our major contribution is the reduction of the number of states to six, even for PFAs, and even while keeping the matrices fixed, for the version where the input is the (fractional) output vector $f$.

The PFA Emptiness Problem is a problem about matrix products. There is a great variety of problems about matrix products whose undecidability has been studied; see [7] for a recent survey of this rich area. In fact, the first problem outside the fields of mathematical logic and theory of computing that was shown to be undecidable is a problem about matrix products: Markov proved in 1947 that it is undecidable whether the semigroups generated two finite sets of matrices contain a common element [15]; see Halava and Harju [11] for a presentation of Markov’s proof (as well as an alternative proof). Our basic approach is the same as Markov’s: to model the Post Correspondence Problem (PCP) by matrix products. Our particular technique for doing this has its roots in Paterson’s undecidability proof [19] from 1970 of the matrix mortality problem for $3\times 3$ matrices.

Besides, we have brought to the light some papers that were apparently forgotten, like Nasu and Honda’s original undecidability proof from 1969 [17], and Claus [5]. Also, our technique for converting matrices with row sums 0 to positive matrices with row sums 1 (hence stochastic matrices) in Section 2.6 is more streamlined and elegant than the proofs that we have seen in the literature.

In the Post Correspondence Problem (PCP), we are given a list of pairs of words $(v_1,w_1),(v_2,w_2),\mathrm{\dots },(v_k,w_k)$. The problem is to decide if there is a nonempty sequence $i_1{i}_2\mathrm{\dots }{i}_m$ of indices $i_j\in \{1,2,\mathrm{\dots },k\}$ such that

This is one of the well-known undecidable problems. According to Neary [18], the PCP is already undecidable with as few as five word pairs.

For a string $u=u_1{u}_2\mathrm{\dots }{u}_n$ of decimal digits, we denote its fractional decimal value by $0.u={\sum }_{j=1}^n{u}_j\cdot {10}^{-j}$. For example, if $u=\mathrm{𝟺𝟹𝟸𝟷𝟶𝟶}$, then $0.u=0.4321$. We will take care to avoid trailing zeros, because their disappearance could cause problems.

For two strings $v,w$ of digits in ${\{\mathrm{𝟷𝟷},\mathrm{𝟷𝟸}\}}^{\ast }$, we define the matrix

It is not straightforward to see, but it can be checked by a simple calculation that the matrices $A_0(v,w)$ satisfy a multiplicative law (see [22, Appendix C] for a computer check):

Now we transform these matrices $A_0(v,w)$ by a similarity transformation with the transformation matrix

The resulting matrices $A(v,w)=U^{-1}{A}_0(v,w)U$ differ in some entries of the first column and the fifth row:

Since the matrices were obtained by a similarity, they satisfy the same multiplicative law:

With the vectors ${\pi }_1=(\frac{1}{99},0,-1,0,-\frac{105}{99},2)$ and $f_1={(1,0,0,0,0,0)}^T$, we obtain

The sign of this expression can detect inequality of $v$ and $w$, as we will presently show.

We could have taken the simpler matrix $A_0$ with ${\pi }_0=(0,0,-1,0,-1,2)$, and this would give ${\pi }_0{A}_0(v,w)f_1=-{(0.v-0.w)}^2$. The contortions with the matrix $U$ were necessary to generate a tiny positive term in (5). The reason for the peculiar entries $\frac{99}{105}$ and $\frac{105}{99}$ in (3) and in ${\pi }_1$ will become apparent after the next transformation.

The multiplicative law (4) and the capacity to detect string equality are all that is needed to model the PCP.

In the PCP, it is no loss of generality to assume that the words in the pairs $(v_i,w_i)$ use a binary alphabet, since any alphabet can be coded in binary. We recode them to the binary “alphabet” $\{\mathrm{𝟷𝟷},\mathrm{𝟷𝟸}\}$, i.e., they become words in ${\{\mathrm{𝟷𝟷},\mathrm{𝟷𝟸}\}}^{\ast }$ of doubled length. We form the matrices $A_i=A(v_i,w_i)$. Multiplicativity gives the relation $A_{i_1}{A}_{i_2}\mathrm{\dots }{A}_{i_m}=A(v_{i_1}{v}_{i_2}\mathrm{\dots }{v}_{i_m},w_{i_1}{w}_{i_2}\mathrm{\dots }{w}_{i_m})$, and by Section 2.2, ${\pi }_1{A}_{i_1}{A}_{i_2}\mathrm{\dots }{A}_{i_m}{f}_1>0$ if and only if $v_{i_1}{v}_{i_2}\mathrm{\dots }{v}_{i_m}=w_{i_1}{w}_{i_2}\mathrm{\dots }{w}_{i_m}$, i. e., $i_1{i}_2\mathrm{\dots }{i}_m$ is a solution of the PCP.

Since the value 0 is excluded by Section 2.2, nothing changes if the condition “$>0$” is replaced by “$\ge 0$.” This property will propagate through the proof, with the consequence that in the resulting theorems, it does not matter if we take $>\lambda$ or $\ge \lambda$ as the acceptance criterion for the PFA. We will not mention this issue any more and work only with strict inequality.

There are two problems that we still have to solve:

• $\mathrm{■}$

  The empty sequence ($m=0$) always fulfills the inequality although it does not count as a solution of the PCP.

• $\mathrm{■}$

  The matrices $A_i$ are not stochastic, and ${\pi }_1$ is not a probability distribution. So far, what we have is a generalized probabilistic automaton, or rational-weighted automaton.

Turakainen [23] showed in 1969 that a generalized probabilistic automaton can be converted to a PFA without changing the recognized language (with the possible exception of the empty word), and this can even be done by adding only two more states [24, Theorem 1(i)]. Thus, by the general technique of [24], we can get a PFA with 8 states. We will use some tailored version of this method, involving nontrivial techniques, so that no extra state is needed to make the matrices stochastic and to simultaneously get rid of the empty solution.

We apply another similarity transformation, using the matrix

but this time, we also transform the vectors ${\pi }_1$ and $f_1$, leaving the overall result unchanged:

We analyze the effect of the similarity transform for a matrix of the general form

The transformed matrix is

with $K=1-a_{21}-a_{31}-a_{41}-a_{51}-a_{61}$ and $K_{12}=K-a_{22}-a_{32}-a_{42}-a_{52}-a_{62}$.

By adding an extra column $r_i$, we now make all row sums equal to 1. We also add an extra row, resulting in a $7\times 7$ matrix

The entries of $r_i$ may be negative. They lie in the range $-5\le r\le 1$. All column sums are still 1: Since the row sums are 1, the total sum of the entries is 7. Therefore, since the first six column sums are 1, the sum of the last column must also be 1.

The vectors ${\pi }_2$ and $f_2$ are extended to vectors ${\pi }_3$ and $f_3$ of length 7 by adding a 0, but they are otherwise unchanged. Thus, the extra column and row of $C_i$ plays no role for the value of the product (6), which remains unchanged:

Let $J$ be the doubly-stochastic $7\times 7$ transition matrix of the “completely random transition” with all entries $1/7$. Then, with $\alpha =0.01$, we form the matrices $D_i:=(1-\alpha )J+\alpha C_i$. The constant $\alpha$ is small enough to ensure that $D_i>0$. Hence the matrices $D_i$ are doubly-stochastic.

If expand of the product ${\pi }_3{\prod }_{j=1}^m{D}_{i_j}={\pi }_3{\prod }_{j=1}^m\left((1-\alpha )J+\alpha C_{i_j}\right)$, we get a sum of $2^m$ terms, each containing a product of $m$ of the matrices $J$ or $C_i$. We find that all terms containing the factor $J$ vanish. The reason is that, since $C_i$ has row and column sums 1, $J{C}_i=C_{i}J=J$. Moreover, ${\pi }_{3}J=0$ by (7). It follows that

The factor ${\alpha }^m$ plays no role for the sign, and hence,

if and only if $i_1{i}_2\mathrm{\dots }{i}_m$ is a solution of the PCP.

The start vector ${\pi }_3$ has sum 0 and contains negative entries, which are smaller than $-1$ but not smaller than $-2$. We form ${\pi }_4=((2,2,2,2,2,2,2)+{\pi }_3))/14$. It is positive and has sum 1. The effect of substituting ${\pi }_3$ by ${\pi }_4$ in (9) is that the result is increased by $1/7$. The reason is that $(1,1,1,1,1,1,1)D_{i_1}{D}_{i_2}\mathrm{\dots }{D}_{i_m}=(1,1,1,1,1,1,1)$ , since the matrices $D_i$ are doubly-stochastic, and in particular, column-stochastic, and therefore $(2,2,2,2,2,2,2)/14\cdot D_{i_1}{D}_{i_2}\mathrm{\dots }{D}_{i_m}{f}_3=2/14=1/7$.

In summary, we have now constructed a true PFA with seven states that models the PCP:

if and only if $i_1{i}_2\mathrm{\dots }{i}_m$ is a (possibly empty) solution of the PCP.

We base our proof on the undecidability of the PCP with 5 word pairs, as established by Turlough Neary [18, Theorem 11] in 2015. Neary constructed PCP instances with five pairs $(v_1,w_1),(v_2,w_2),(v_3,w_3),(v_4,w_4),(v_5,w_5)$ that have the following property: Every solution necessarily starts with the pair $(v_1,w_1)$ and ends with $(v_5,w_5)$. We can also assume that the end pair $(v_5,w_5)$ is used nowhere else. (More precisely, in every primitive solution (which is not a concatenation of smaller solutions), the end pair $(v_5,w_5)$ cannot appear anywhere else than in the final position.) However, the start pair $(v_1,w_1)$ is also used in the middle of the solutions. (This multipurpose usage of the start pair is one of the devices to achieve such a remarkably small number of word pairs.)³³3The proof of Theorem 11 in Neary [18] contains an error, but this error can be fixed: His PCP instances encode binary tag systems. When showing that the PCP solution must follow the intended patters of the simulation of the binary tag system, Neary [18, p. 660] needs to show that the end pair $(v_5,w_5)=({10}^{\beta }1111,1111)$ cannot be used except to bring the two strings to a common end. He claims that a block $1111$ cannot appear in the encoded string because in $u$ (the unencoded string of the binary tag system, which is described in Lemma 9) we cannot have two $c$ symbols next to each other. This is not true. The paper contains plenty of examples, and they contradict this claim; for example, the string $u^{\prime }$ in (7) [18, p. 657] contains seven $c$’s in a row. The mistake can be fixed by taking a longer block of 1s: Looking at the appendants in Lemma 9, it is clear that every block of length $|u|+1$ must contain a symbol $b$. Thus, the pair $(v_5,w_5)=({10}^{\beta }{1}^{|u|+99},1^{|u|+99})$ will work as end pair.

We apply the above construction steps to the word pairs $(v_1^R,w_1^R),\mathrm{\dots },(v_5^R,w_5^R)$, leading to five matrices $D_1,D_2,D_3,D_4,D_5$. Since the leftmost matrix must be $D_5$ in any solution, we can combine this matrix $D_5$ with the starting distribution ${\pi }_4$:

leading to a new starting distribution ${\pi }_5:={\pi }_4{D}_5$. The matrix $D_5$ can be removed from the pool $ℳ$ of matrices, leaving only 4 matrices. We have simultaneously eliminated the empty solution with a product of $m=0$ matrices. This concludes the proof of Theorem 1a. ∎

Matiyasevich and Sénizergues [16] constructed PCP instances with seven word pairs $(v_1,w_1),(v_2,w_2),(v_3,w_3),(v_4,w_4),(v_5,w_5),(v_6,w_6),(v_7,w_7)$ that have the following property: Every solution necessarily starts with the pair $(v_1,w_1)$ and ends with $(v_2,w_2)$. Both the start pair $(v_1,w_1)$ and the end pair $(v_2,w_2)$ can be assumed to appear nowhere else, in the sense described in Section 2.8, i. e., apart from the possibility to concatenate solutions to obtain longer solutions. Matiyasevich and Sénizergues [16] used a reduction, due to Claus [4], from the individual accessibility problem (or individual word problem) for semi-Thue systems. They showed that the individual accessibility problem is already undecidable for a particular semi-Thue system with 3 rules [16, Theorem 3]. Halava, Harju, and Hirvensalo [12, Theorem 6] observed an important consequence of this: One can fix all words except $v_1$, and leave only $v_1$ as an input to the problem, and the PCP is still undecidable.

From these word pairs, we form the matrices $A_i=A(v_i,w_i)$ from the words without reversal. Following the same steps as above, we eventually arrive at corresponding matrices $D_1,\mathrm{\dots },D_7$. We merge $D_1$ with ${\pi }_4$ into a new starting distribution ${\pi }_5:={\pi }_4{D}_1$. We are left with a pool $ℳ=\{D_2,\mathrm{\dots },D_7\}$ of six fixed matrices. The only variable input is the starting distribution ${\pi }_5$. This concludes the proof of Theorem 1b. ∎

The following lemma and its proof is extracted from Step 3 in Hirvensalo [13, Section 3]. We denote by $\varphi (u)$ the acceptance probability of a (generalized) PFA for an input $u$, i.e., the value of the product in the expression (1).

The lemma is not specific about the word $u$ or $u^{\prime }$ whose existence is guaranteed. Nevertheless, regardless of how these words are found, the statement is sufficient in the context of the emptiness question.

However, we can be explicit about $u$ and $u^{\prime }$: The construction uses a binary encoding $\tau :{\mathrm{\Sigma }}^{\ast }\to {\{𝚊,𝚋\}}^{\ast }$ with the prefix-free codewords $\{𝚋,\mathrm{𝚊𝚋},\mathrm{𝚊𝚊𝚋},\mathrm{\dots },{𝚊}^{k-2}𝚋,{𝚊}^{k-1}\}$. Then, we can take $u^{\prime }=\tau (u)$, because

For words $u^{\prime }$ that are not of the form $\tau (u)$, (11) holds for the longest word $u$ such that $\tau (u)$ is a prefix of $u^{\prime }$. In other words, $u$ is the decoding of the longest decodable prefix of $u^{\prime }$.

Section 3.1 blows up the number of states by a factor that depends on the number of matrices. Thus, it is advantageous to apply it after merging the start matrix into $\pi$, when the number of matrices is reduced.

So we start with the 5-pair instances of Neary [18] and construct five matrices $A_i=A(v_i^R,w_i^R)$ from the reversed pairs. We then combine $A_5$ with the starting distribution ${\pi }_1$ into ${\pi }_2={\pi }_1{A}_5$, leaving $k=4$ matrices $A_1,A_2,A_3,A_4$ of dimension $d=6$.

We cannot apply the transformations of Step 2, because it changes the first row, and state 1 would no longer be absorbing, which precludes the application of Section 3.1.

Thus, we apply Section 3.1 to the matrices $A_1,A_2,A_3,A_4$, resulting in two matrices $M_{𝚊}^{\prime }$ and $M_{𝚋}^{\prime }$ of dimension $(k-1)(d-1)+1=16$. The new start vector ${\pi }_3$ is ${\pi }_2$ padded with zeros, and the end vector $f$ is still the first unit vector (of dimension 16).