Post Correspondence Problem Explained — The Puzzle That Broke Computation

We explore the Post Correspondence Problem (PCP), a simple-looking string-matching puzzle that turns out to be one of the most important undecidable problems in computer science. We will learn how PCP works, why it’s more than a game with tiles, and how it reveals fundamental limits of what algorithms can do. We break down the idea of matching top and bottom strings, walk through clear examples, and explain why no algorithm can always decide whether an instance has a solution. PCP is deeply connected to the Halting Problem, Turing machines, formal languages, and the foundations of computability. If you’re studying theory of computation or just curious about the boundaries of algorithmic reasoning, this video will give you a crisp and intuitive understanding of why PCP is both fascinating and impossible to fully solve.