On my favourite TCS site cstheory.stackexchange.com I found a simple question about the Post Correspondence Problem:

If the upper and lower words of each domino must have different lengths, is the problem still undecidable? (we call this variant $PCP^{\neq}$).

The answer is yes, it remains undecidable …

A simple reduction from standard $PCP$ to $PCP^{\neq}$ is the following:

Suppose that we have $n$ dominos $[\alpha_1 / \beta_1], [\alpha_2 / \beta_2], …. [\alpha_n / \beta_n]$ with $\alpha_i, \beta_i \in \Sigma^*$

We expand the alphabet $\Sigma$ to a new alphabet $\Sigma’$ in which each symbol $a_i \in \Sigma$ is represented by $m$ distinct new symbols $\{a_{i_1},a_{i_2},….,a_{i_n} \}$, where $m$ is the first odd number greater than or equal to $n+1$ ($m = 3 \lceil (n + 1)/ 3 \rceil $).

We replace each symbol in the words of the original dominos with the sequence of the new $m$ corresponding symbols. For example suppose that $n = 3$ and the dominos are $D_1 = [a/baa]$,$D_2 = [ab/aa]$,$D_3 = [bba/bb]$ we get the new set of dominos:

• $D’_1 = [a_1 a_2 a_3 a_4 a_5/ b_1 b_2 b_3 b_4 b_5 \; a_1 a_2 a_3 a_4 a_5 \; a_1 a_2 a_3 a_4 a_5]$
• $D’_2 = [a_1 a_2 a_3 a_4 a_5 \; b_1 b_2 b_3 b_4 b_5 / a_1 a_2 a_3 a_4 a_5 \; a_1 a_2 a_3 a_4 a_5 ]$
• $D’_3 = [b_1 b_2 b_3 b_4 b_5 \; b_1 b_2 b_3 b_4 b_5 \; a_1 a_2 a_3 a_4 a_5 / b_1 b_2 b_3 b_4 b_5 \; b_1 b_2 b_3 b_4 b_5 ]$

Finally we transform each domino $D’_i$ in which the upper and lower words have the same length, into two equivalent dominos $D^L_i, D^R_i$. We pick the first sequence of length $m$ (that represents the first symbol in the original word) in the upper word of $D’_i$ and we split it at position $i$, we pick the first sequence of length $m$ in the lower word and we split it at position $m-i$. For example, domino $D’_2$ becomes:

• $D^L_2 = [a_1 a_2 / a_1 a_2 a_3 ]$
• $D^R_2 = [ a_3 a_4 a_5 \; b_1 b_2 b_3 b_4 b_5 / a_4 a_5 \; a_1 a_2 a_3 a_4 a_5 ]$

By construction upper and lower words of both dominos have different lengths: if $D’_i = [\alpha / \beta]$ and $|\alpha| = |\beta|$, $D^L_i = [\alpha_1 / \beta_1]$, $D^L_i = [\alpha_2 / \beta_2]$ we have $|\alpha_1| = i, |\beta_1| = m – i$, $|\alpha_2| = |\alpha| – i, |\beta_2| = |\beta| – m + i$; and $m$ is odd so for all $i$, $i \neq m-i$.

Also note that each split point is different for each domino $D’_i$, so there is no way to “reconstruct” the same upper/lower subwords using a combination of other dominos; in other word each domino $D^L_i$ must be followed by $D^R_i$.

So the original $PCP$ problem has a solution if and only if the corresponding $PCP^{\neq}$ has a solution; so $PCP^{\neq}$ is undecidable.

Final stuff: … don’t forget that the PCP variant in which all tiles have equal length is decidable.

Final stuff 2: I also found a nice relation between PCP and Context Free palindromes, but it happens that someone else had the same insight before me; see Post’s Correspondence Problem PCP is about context-free grammars
by Wim H. Hesselink.

Open question: the above reduction is simple but it could probably be further simplified and optimized. Perhaps there is also a simpler reduction … let me know.