Post correspondence problem(pcp) undecidable problem of Turing Machine

Post Correspondance Problem

Post Correspondance Problem is a combinatorial problem formulated by Emil Post in 1946. A correspondance system P is a finite set of ordered pairs of nonempty strings over some alphabet.

The selected pairs (u1,v1),(u2,v2)--------(un,vn) are not necessarily distinct. Let strings u1,u2,----um are in set U and strings v1,v2----vm are in set V

U={u1,u2-------um} and V={v1,v2-------vm} for some m>0.

PCP is to determine whether there is any match or not for a given correspondance system.

Example

Does a PCP with two list x=b,bab³   and  y=(b³,ba,a) have a solution?

Solution:  

first choose  second tile because match first two alphabet ba.

Second choose  first tile because in upper part has extra b^3.

Third choose first tile because extra b in upper part

Last choose third tile extra b in lower part.

upper part and lower part has same pattern bab³bbba.

So That PCP has solution. 

Post correspondance problem is a undecidable problem.There are n number of tiles. The motive is to arrange tile in some order that string made by denominators.PCP is undecidable so that there is no particular algorithm that determine whether any post correspondence system has solution or not.