Show that the Post Correspondence Problem is decidable over

Show that the Post Correspondence Problem is decidable over the unary alphabet sigma = {1}. Explain how your algorithm works on the instance {[1/1111], [1/111111], [11111/111]}.

Solution

Let P = {( _i , _i ), 1 i k } be a Post System over = {1}. In this case the members of the pairs can be looked upon as nonnegative numbers in unary encoding.

The concatenation of two strings _i and _j is only addition of the respective numbers.

Hence, if there is a solution, then any of its permutations is also a solution. Secondly, the pairs which have members having identical length are not important because even if one such pair is there, we have a solution comprising a single integer corresponding to that pair. When there is no equal pair, what is important is the difference between the lengths (i.e., the magnitudes, in unary encoding) of the members in a pair;

for two distinct pairs, ( _i , _i ) and ( _j , _j ), let _{i i} = m, m > 0 and _{j j} = n, n > 0; then it is possible to find a solution (an integer sequence) by finding the LCM(m, n). Let l = LCM(m, n)/m and p = LCM(m, n)/n. Obviously, l.m = p.n which means that the integer sequence ( i ^l , j^p ) (i.e i repeated l times followed by j repeated p times) will be a solution. Since any combination of negative and positive numbers will result in some LCM, the solution exists as long as both classes of pairs exist, one having shorter first members and the other having larger members. So the algorithm checks if there is a pair having equal length strings; if so it accepts. Else, it ensures that if there is a pair belonging to one class, there should be a pair belonging to the second class. If so, it accepts the input Post System, else if there are some pairs in one class but no pair in the other class, then it rejects.