Post Correspondance Problem(PCP)

To prove a program or normal thing(strings or languages) undecidable or decidable there are some technology. The technology is based on a very simple model of a computer called the Turing Machine. The Post Correspondence Problem is an undecidable problem that turns out to be a very helpful tool for proving problems in logic or in formal language theory to be undecidable.

What is undecidable?

The, specific, problem that cannot be solved using a computer are called undecidable. In computing there always exist some. That is a program and an input, whether the program will finish running or continue to run forever.

Suppose, we have step by step procedure(Algorithm) to solve a particular problem. We give the input(problem) and if that procedure can solve it, it gives the result true and if it not it give the result false. what if we give that procedure input(problem)which run forever that it take very long  time(years) to get the result(TRUE or FALSE), then we can't make the decision out of it. This situation is undecidable.

PCP

can be defined as, an instance of PCP consist of two lists of strings over some alphabet Σ; the two list must be of equal length. Refer it as A and B lists, and write as:

A=w₁,w₂,w₃,...,w_k and B=v₁,v₂,v₃,...,v_k for some integer k. for each i , the pair(w_i, v_i) is said to be a corresponding pair.

The instance of PCP has a solution, if there is sequence of one or more integers i₁,i₂,i₃...,i_m ,that, when interpreted as indexes for strings in the A and B lists, yield the same string. That is, w₁ w₂ w₃ ...w_k =v₁ v₂ v₃...v_k. the sequence i₁ ,i₂,i₃...,i_m is a solutionto this instance of PCP.

(Introduction to Automata Theory,languages and Computation- John E.Hopercroft, Rajeev Motwani, Jeffrey D. Ullman)
 

Example

1)Consider the following two lists:

	List A	List B
i	wi	vi
1	110	110110
2	0011	00
3	0110	110

 

A solution to this problem would be the sequence (2,3,1)

To solve this in convenient way is as a collection of blocks so the above list can be viewed as

wi	110	0011	0110
vi	110110	00	110

now we have the supply of each of the block. We just need to view the string in the top cells corresponds to the string in the bottom cells. Select any string from top cells find the any corresponding string in the bottom cells, atleast a starting symbol,

ie when
              i₁=2         i₂=3            i₃=1

0011	0110	110
00	110	110110

Thus we have the solution to above is

w₁w₂w₃...w_k =00110110110=v₁v₂v₃...v_k

0011	0110	110
00	110	110110

            <sub>i1=2       i2=3           i3=1


2)</sub>Consider the following two lists:

	List A	List B
i	wi	vi
1	1	111
2	1011	10
3	10	0

 A solution to this problem would be the sequence (2,1,1,3)

10111	1	1	10
10	111	111	0

            _{i1=2         i2=1        i3=1}     i₄=3