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 Σ{ (u_{1},v_{1}), (u_{2},v_{2}), ..., (u_{K},v_{K}) }The problems is this:
Is there a selection of indices (i_{1},i_{2},...,i_{N}) such that
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.
u_{i1}u_{i2}...u_{iN} = v_{i1}v_{i2}...v_{iN} ?
Empty intersection of contextfree languages
The Post Correspondence problem can be used to show that the following problem is undecidable:
Given two contextfree languages L_{1} and L_{2},
is L_{1}∩L_{2} = ∅?
In the last section we showed that the problem of deciding whether L = Σ^{*}
for a contextfree language L is undecidable; however, this result cannot be used to
establish the undecidability of the contextfree language intersection problem.
Proof of undecidability
Assuming that the Post Correspondence problem is undecidable, the idea is to reduce it to the above contextfree language empty intersection problem. Let Σ be the alphabet used for the correspondence system{ (u_{1},v_{1}), (u_{2},v_{2}), ..., (u_{K},v_{K}) }and take a symbol $ ∉ Σ. The languages we construct are over Σ∪{$}. Let L_{1} be the contextfree language
L_{1} = { w$w^{R} : w ∈ Σ^{*} }Let L_{2} be the contextfree language defined by this grammar:
S → u_{i}Sv_{i}^{R}  $ for i = 1..K
The strings of L_{2} are of the form:
u_{i1}u_{i2}...u_{iN}$v_{iN}^{R}...v_{i2}^{R}v_{i1}^{R}Then L_{1}∩L_{2} ≠ ∅ if and only if there is a string w such that
w$w^{R} = u_{i1}u_{i2}...u_{iN}$v_{iN}^{R}...v_{i2}^{R}v_{i1}^{R} = u_{i1}u_{i2}...u_{iN}$(v_{i1}v_{i2}...v_{iN})^{R}if and only if there is a string w such that
w = u_{i1}u_{i2}...u_{iN} = v_{i1}v_{i2}...v_{iN}Thus, the contextfree language empty intersection problem could decide the Post Correspondence problem. We conclude that the contextfree 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:
Formal tiling system
Mathematically, a tiling system is a quadruple (D,d_{0},H,V) where D is a finite set set of "tiles", d_{0} ∈ 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 → Dwhich assigns a tile (i.e., a tile type) to each coordinate pair (0,0), (0,1), (1,0), ... in such a way that d_{0} is the starter tile and that adjacent tiles match, which means this:
f(0,0) = d_{0} (f(n,n),f(n,n+1)) ∈ H (f(n,n),f(n+1,n)) ∈ VWhat we're suggesting about the matching relations H and V is this:
(d,d′) ∈ H if and only if rightedgemarker(d) = leftedgemarker(d′) (d,d′) ∈ V if and only if topedgemarker(d) = bottomedgemarker(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:
 horizontal: specifies the tape contents
 vertical: specifies the steps of the TM

For each a ∈ Σ (including blank and left end):

If δ(q,a) = (p,b) for b ∈ Σ

If δ(q,a) = (p,R), for all b other than the left end marker:

If δ(q,a) = (p,L), for all b:

The starter tile and initial blank fill tile:
d_{0} =
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:
...  

>  ...  
...  
...  
>  ...  
... 