Other Undecidable Problems

The Post Correspondence Problem

This is arguably the most famous of the undecidable problems. It has been widely studied and can be used to prove the undecidability of a number of other problems. A correspondence system is a finite set of pairs of strings over an alphabet Σ
{ (u1,v1), (u2,v2), ..., (uK,vK) }
The problems is this:
Is there a selection of indices (i1,i2,...,iN) such that
ui1ui2...uiN = vi1vi2...viN ?
The result we are suggesting is that this problem is undecidable. The textbook relegates this proof to problem 5.5.2. The reduction is from the problem of deciding whether a string belongs to the language of an unrestricted grammar. However, one does not reduce directly to the Post Correspondence problem; instead, the reduction is to a modified version of the Post Correspondence problem.

Empty intersection of context-free languages

The Post Correspondence problem can be used to show that the following problem is undecidable:
Given two context-free languages L1 and L2, is L1∩L2 = ∅?
In the last section we showed that the problem of deciding whether L = Σ* for a context-free language L is undecidable; however, this result cannot be used to establish the undecidability of the context-free language intersection problem.

Proof of undecidability

Assuming that the Post Correspondence problem is undecidable, the idea is to reduce it to the above context-free language empty intersection problem. Let Σ be the alphabet used for the correspondence system
{ (u1,v1), (u2,v2), ..., (uK,vK) }
and take a symbol $ ∉ Σ. The languages we construct are over Σ∪{$}. Let L1 be the context-free language
L1 = { w$wR : w ∈ Σ* }
Let L2 be the context-free language defined by this grammar:
S → uiSviR | $   for i = 1..K
The strings of L2 are of the form:
ui1ui2...uiN$viNR...vi2Rvi1R
Then L1∩L2 ≠ ∅ if and only if there is a string w such that
w$wR  =  ui1ui2...uiN$viNR...vi2Rvi1R  =  ui1ui2...uiN$(vi1vi2...viN)R
if and only if there is a string w such that
w = ui1ui2...uiN = vi1vi2...viN
Thus, the context-free language empty intersection problem could decide the Post Correspondence problem. We conclude that the context-free language empty intersection problem is undecidable.

The Tiling Problem

The notion of tiling means that we have an infinite set of square tiles of the same size, but only finitely many are different from each other. The idea is to attempt to fill the upper right quadrant of a coordinate plane with these tiles.

A single start tile is placed in the corner. Tiles can only be placed adjacent to each other if they match in some sense. The matching must occur on both the horizontal and vertical adjacent edges. Although the matching can be more abstract, it is most useful to think that there are a finite number of markings
a, b, c, d
Assume that every edge on each tile has one of these markings:
Edge markings are the only feature that distinguishes tiles. Tiles match simply by having the same markings on adjacent edges like this:

Formal tiling system

Mathematically, a tiling system is a quadruple (D,d0,H,V) where D is a finite set set of "tiles", d0 ∈ D, and H, V are binary relations on D. The set D should be thought of a "tile types" since we use an infinite number of tiles. A tiling function is this:
f: N×N → D
which assigns a tile (i.e., a tile type) to each coordinate pair (0,0), (0,1), (1,0), ... in such a way that d0 is the starter tile and that adjacent tiles match, which means this:
f(0,0) = d0
(f(n,n),f(n,n+1)) ∈ H
(f(n,n),f(n+1,n)) ∈ V
What we're suggesting about the matching relations H and V is this:
(d,d′) ∈ H  if and only if  right-edge-marker(d) = left-edge-marker(d′)
(d,d′) ∈ V  if and only if  top-edge-marker(d)  = bottom-edge-marker(d′)
Finally, the tiling problem is this:
Given a tiling system D, does there exist a tiling function, f?

The tiling problem is undecidable

At first glance this seems pretty far from what we've done, but you will see that it is relatively simple to reduce an undecidable TM problem to the tiling problem. The undecidable TM problem is this:
This problem is Given a TM, M, does M↑ε?
This is effectively the complement of the problem of part (b) in Theorem 5.4.2, and so it must as well be undecidable.

Assume we start our machine M with this tape configuration:
>
We want to map the progress of the tape by the tiles, and so think of the upper coordinate plane quadrant as this: Here are the tile types:
  1. For each a ∈ Σ (including blank and left end):
    Think of an empty edge as having the empty string as the marker, and so empty edges must match other empty edges.
  2. If δ(q,a) = (p,b) for b ∈ Σ
    The state on a top or bottom edge means that this tile corresponds to the selected position.
  3. If δ(q,a) = (p,R), for all b other than the left end marker:
           
    The state on the right means that the tape head is moving right.
  4. If δ(q,a) = (p,L), for all b:
           
  5. The starter tile and initial blank fill tile:
    d0 =        

Example

Suppose M writes the input string "ab" and performs some computation. Specifically, suppose the computation proceeds through these configurations:
( s, > )          
( t, ># )      δ(s,>) = (t,R)
( u, >a )      δ(t,#) = (u,a)
( v, >a# )     δ(u,a) = (v,R)
( w, >ab )     δ(v,#) = (w,b)
( x, >ab# )    δ(w,b) = (x,R)
After which in state x, it begins whatever "computation" it plans to do to the input string. The corresponding tiling up to this point is this:
...
> ...
...
...
> ...
...
If x were a halting state, then the tiling of the column with the marked tile cannot proceed further because there are no tiles whose bottom edge will match the top edge (x,#). Therefore, it is clear that the tiling will only complete if M runs forever.


© Robert M. Kline