 Post correspondence problem

The Post Correspondence Problem (PCP) is a decision problem in the field of computability theory and formal languages. It was introduced by Emil Post in 1946. The problem can be described as follows: You are given two lists of strings (or sequences of symbols) over some finite alphabet.