Question

Show that the Post Correspondence Problem is decidable over the unary alphabet$\sum _{}=\left\{1\right\}$.

Short answer

It’s proved that Post Correspondence Problem is undecidable over$\sum _{}=\left\{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 ∑=1

Now we will create a Turning Machine M that decides unary PCP such that:

M = on input$\left(P\right)$.

• Check if a_i= b_i for some value of ‘i’.

If$True\to Aceept$

• Check if there exist some values of i and j such that a_i > b_i and a_j< b_j .

If$True\to Accept$

Else Reject.

If both condition are false, that means upper parts have more or less 1s than lower part, hence no match will exist and M got rejected.

Thus this makes M decidable which means Post Correspondence Problem is decidable over the unary alphabet.