Post Correspondence problem

In this section I show that the p-parsing problem for $\cal {R}$($\cal {L}$)-grammars is generally not solvable. A yes-no problem is undecidable (cf. [33, pp.178-179]) if there is no algorithm that takes as its input an instance of the problem and determines whether the answer to that instance is `yes' or `no'. An instance of a problem consists of a particular choice of the parameters of that problem.

In the case at hand I show that in general the p-parsing problem is not solvable for any fixed path p. I show that this result holds both for the p-parsing problem, and goals in general. I encode an undecidable problem in a $\cal {R}$($\cal {L}$)-grammar in such a way that deciding whether there is at least one solution of the p-parsing problem will be equivalent to solving this undecidable problem.

I use Post's Correspondence Problem (PCP) as the undecidable problem. The following definition and example of a PCP are taken from [33][chapter 8.5].

An instance of PCP consists of two lists, A = v₁...v_k and B = w₁...w_k of strings over some alphabet $\Sigma$. This instance has a solution if there is any sequence of integers i₁...i_m, with m $\geq$ 1, such that

$$v_{i_1}, v_{i_2}, \dots, v_{i_m} = w_{i_1}, w_{i_2}, \dots, w_{i_m}.$$
The sequence i₁,..., i_m is a solution to this instance of PCP. As an example, assume that $\Sigma$ = {0, 1}. Furthermore, let A = $\langle$1, 10111, 10$\rangle$ and B = $\langle$111, 10, 0$\rangle$. A solution to this instance of PCP is the sequence 2,1,1,3 (obtaining the sequence 101111110). For an illustration, cf. figure 2.11.

Figure 2.11: Illustration of a solution of a PCP problem.

Clearly there are PCP's that do not have a solution. Assume again that $\Sigma$ = {0, 1}. Furthermore let A = $\langle$1$\rangle$ and B = $\langle$0$\rangle$. Clearly this PCP does not have a solution. In general, however, the problem whether some PCP has a solution or not is not decidable. This result is proved by [33] by showing that the halting problem for Turing Machines can be encoded as an instance of Post's Correspondence Problem.

First I give a simple algorithm to encode any instance of a PCP as a grammar of $\cal {R}$($\cal {L}$), in such a way that the question whether there is a solution to this PCP can be phrased as a goal. Then I extend the encoding in such a way that the question whether there is a solution is equivalent to the p-parsing problem.

Note that I use the notation lⁱ to stand for i repetitive occurrences of label l. Hence the expression X₀ a in r⁴ f will stand for the path X₀ a in r r r r f. Furthermore I assume that C and L are defined appropriately.

Encoding of PCP.

1.

For each 1 $\leq$ i $\leq$ k (k the length of lists A and B) define a unit rule sign(X₀):-$\phi$, where $\phi$ is defined as follows (the i - th member of A is a₁...a_m, and the i-th member of B is b₁...b_n).

(a)

For each j, 1 $\leq$ j $\leq$ m there is an equation: X₀ a in r^{j - 1} f $\doteq$ a_j

(b)

Moreover, there is an equation: X₀ a in r^m $\doteq$ X₀ a out.

(c)

For each j, 1 $\leq$ j $\leq$ n there is an equation: X₀ b in r^{j - 1} f $\doteq$ b_j

(d)

Moreover, there is an equation: X₀ b in rⁿ $\doteq$ X₀ b out.

2.

There is one non unit rule, defined as follows:

The underlying idea of the algorithm is really very simple. For each pair of strings from the lists A and B there will be one unit rule where these strings are represented by a difference-list encoding. Furthermore there is a general combination rule that simply concatenates A-strings and concatenates B-strings.

Figure 2.12: The grammar of $\cal {R}$($\cal {L}$) corresponding to example PCP

Figure 2.13: Parse tree of the proof that there is a solution, according to the $\cal {R}$($\cal {L}$) encoding of the example PCP.

The following goal then is equivalent to determining whether there is a solution to the PCP:

In matrix representation the resulting $\cal {R}$($\cal {L}$) grammar for the first example PCP above, look as in figure 2.12. Furthermore, one of the parse trees for the solution given above is presented in figure 2.13.

To show that the same result applies to the p-parsing problem I change the encoding slightly. Firstly, each unit rule built by the foregoing algorithm will have an extra constraint X₀ solution $\doteq$ no. Similarly, in the combination rule I add for each of the three variables X₀,X₁,X₂ the constraints X_i solution $\doteq$ no. Finally, the query above is then encoded as an extra rule as follows:

Now, the question whether there is a solution to an instance of PCP can be answered ``yes'' in case the enumeration of the solution-parsing problem of the following formula at least yields one answer:

Proposition

The p-parsing problem for $\cal {R}$($\cal {L}$)-grammars is unsolvable.

Proof.

Suppose the problem was solvable. In that case we could use it to solve the PCP, because a PCP $\pi$ has a solution if and only if for its encoding, $\cal {R}$($\cal {L}$)($\pi$), the query

has at least one solution. By construction, there is a direct relation to a solution to $\pi$ (a list of integers) and a derivation of $\cal {R}$($\cal {L}$)($\pi$). A derivation encodes the concatenations of the a and b strings. If and only if such a concatenation yields the same list this derivation can be the daughter of the final rule. The last problem however is known to be undecidable, hence the p-parsing problem is unsolvable.