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 …
Continue reading