Question

Show that the Post Correspondence Problem is undecidable over the binary alphabet.$\sum _{}=\left\{0,1\right\}$.

Short answer

It’s proved that Post Correspondence Problem is undecidable over $\sum _{}=\left\{0,1\right\}$.

Step-by-step solution

Introduction to Post Correspondence Problem 

Post Corresponding Problem is undecidable problem where we have more than one tile which contains multiple strings. The goal of this problem is to arrange the order of strings such that the numerator and denominator are identical.

In Post Correspondence Problem (PCP), we try to find the pattern in which upper and lower strings are identical.

Proving PCP Undecidability over ∑=0,1

Assume an example of Post Correspondence Problem (PCP), here we have taken size of alphabet as n such that $n\le 2^p$ , where p can be any constant.

So, p-bit code can be created and substituted in the tile.
For example a tile in Post Correspondence Problem:

$\left\{\left[\frac{aba}{acd}\right],\left[\frac{aabd}{acd}\right],\left[\frac{a}{bc}\right],\left[\frac{acd}{bc}\right],\left[\frac{bcd}{abc}\right]\right\}$

Now, let,a=00, b=01, c=10 and d=11 ,so the above tile will becomes:

role="math" localid="1662110076825" $\left\{\left[\frac{000100}{001011}\right],\left[\frac{00000111}{001011}\right],\left[\frac{00}{0110}\right],\left[\frac{011011}{000110}\right]\right\}$

So, the newly formed PCP example has solution for alphabet size ‘2’, if original PCP has solution.

So, if situation arise that new PCP have solution but no solution for original solution. But such situation will not arise as if the tiles are obtained after inserting the values in the original PCP.

Now for unary alphabets, above example will not work, this is because if a, b, c and d are taken as 1, 11, 111 and 1111, and if we trace in backward then it will be very difficult to detect if 1111 belong to ac, ca, d or bb pattern.

Thus, PCP becomes undecidable according to above pattern.