The Post Correspondence Problem is an undecidable problem that turns out to be a very helpful tool for proving problems in logic or in formal language theory to be undecidable

Let Σ be an alphabet with at least two letters. An instance of the Post Correspondence problem (for short, PCP) …