Explore and visualize famous undecidable problems in computer science
The Post Correspondence Problem (PCP) asks whether, given two lists of strings X and Y, there exists a sequence of indices such that concatenating the strings from X in that order equals concatenating the strings from Y in the same order.
PCP is undecidable for alphabets with at least two symbols. This means there is no algorithm that can determine for any arbitrary PCP instance whether a solution exists.
This PCP instance has a solution with the sequence (3, 2, 3, 1).