0

Recently I have been studying Post's correspondence problem ($Pcp$), and I have stumbled upon a problem where I need to find a reduction from $Pcp$ to a modified version, $mPcp$. This modified version requires any matching sequence of "dominoes" $p_{i_1}, p_{i_2}, ..., p_{i_m}$ to start with the first "domino", $p_1$.

I am very well aware of the fact that there exists a match for an instance $I=\langle p_1, ..., p_n\rangle$ of $Pcp$ if and only if there exists a match for one of the instances $I_1, I_2, ..., I_n$ of $mPcp$ where $I_j=\langle p_j, p_{j+1}, ..., p_n, p_1, ..., p_{j-1}\rangle$ for $j=1, ..., n$. In other words, if and only if $I$ is a yes-instance for $Pcp$, there is a way to rotate the list of "dominoes" in a cyclic manner such that the starting piece in the found match for $Pcp$ is put in the first position.

However, it is not clear to me how this observation could lead to a mapping from an instance $I$ of $Pcp$ to the "correct" instance $I_j$ of $mPcp$ that can be carried out in a finite amount of steps for any $I$, thus serving as a suitable reduction.

Could anybody point me in the right direction? Thank you very much.

Dyon J Don Kiwi van Vreumingen
  • 101
  • Given a sequence of dominoes $p_1,...,p_n$, you can "rotate" the sequence by removing the first piece and appending it to the end of the sequence. With n pieces, you have n sequences each beginning with $p_i$ for $i = 1,...,n$. You then call mPcp once for each of the n sequences. Pcp will be a "Yes" instance iff mPcp is a "Yes" instance for at least one of the n instances. – user137481 May 09 '16 at 17:42
  • The problem is that calling $mPcp$ for all $i$ could result in an infinite loop if $I$ is a no instance of $Pcp$, thus not satisfying the requirement that the reduction be carried out in a finite number of steps. – Dyon J Don Kiwi van Vreumingen May 10 '16 at 09:12
  • Pcp is undecidable. I'm assuming that you are trying to prove that mPcp is undecidable. To start, we assume that mPcp is decidable and let M be the decider for mPcp. A decider always halts. So, there is no "infinite loop" even for 'No" instances. However, if mPcp is decidable, M could also be used to decide Pcp which gives us a contradiction. Hence, mPcp must also be undecidable. – user137481 May 10 '16 at 15:16

2 Answers2

1

http://infolab.stanford.edu/~ullman/ialc/slides/slides14.pdf

To summarise what is said in the attached pdf:

Let the dominos be (u1,v1), (u2,v2),...(un,vn). (* is some symbol not already in the alphabet) For all the u's, put a * after them, and for all the v's, put a star before them, like such: (u1*,v1), (u2,v2),...(un,*vn)

Now in the MPCP if we wanna start with the first term, we put a * before u1 like such: (u1,v1), (u2,v2),...(un,*vn)

So now you the first domino MUST start, as it is the only one which has the first symbol matching. If there is a solution to this, it must start with the first domino.

Now to make the endings match, we add a domino: (@,*@) where @ is anything not in the alphabet.

Now MPCP is yes iff PCP is yes.

PolkaDot
  • 191
-2

Put the *s before (or after) each symbol, not the words. So for d=(01101,001) add (0*1*1*0*1*,*0*0*1) but no (01101*,*001). If d is a starting domino add (*0*1*1*0*1*,*0*0*1), too.

Parcly Taxel
  • 103,344
tkrisz
  • 1