VideoGist - The Post Correspondence Problem

The Post Correspondence Problem

Neso Academy

14 min, 29 sec

The video is a lecture on the Post Correspondence Problem (PCP), an undecidable problem introduced by Emil Post in 1946.

Summary

The lecturer introduces the Post Correspondence Problem and its undecidable nature, following the discussion of the halting problem in a previous lecture.
Examples of PCP are provided, showing how to arrange dominos (tiles with a top and bottom part) to make the strings on top and bottom match.
The first example is solved by selecting dominos in a sequence that matches the top and bottom strings, demonstrating a solution to the PCP.
A second example is presented using a different representation (a table format) and is also solved by arranging a sequence of dominos.
A third example shows a PCP that cannot be solved, illustrating the undecidable nature of the problem and leading to the conclusion that no general algorithm can solve all instances of PCP.

Chapter 1

0:00 - 47 sec

The introductory part of the lecture explains the concept of undecidable problems and introduces the Post Correspondence Problem (PCP).

The lecture starts by referencing the halting problem as an example of an undecidable problem.
The Post Correspondence Problem (PCP) is introduced as another undecidable problem, first presented by Emil Post in 1946.
The problem involves arranging dominos or tiles in a way that the top and bottom strings formed by the sequence are identical.

Chapter 2

0:47 - 4 min, 35 sec

The lecture proceeds with a detailed explanation of how to solve an example of the Post Correspondence Problem.

A set of four dominos is presented as an example to solve the PCP.
The lecturer explains that a sequence must be found where the concatenated top strings match the concatenated bottom strings.
Dominos can be used any number of times to achieve a matching sequence, and the sequence must be finite.
A solution to the example is demonstrated step by step, starting with a domino that has matching symbols on the top and bottom.

Chapter 3

5:22 - 3 min, 36 sec

A second example using a tabular representation of PCP is solved to demonstrate another approach to solving the problem.

The lecturer presents a different representation of PCP using a table format where dominos correspond to rows in the table.
The task is to match the top and bottom strings by selecting dominos in a sequence.
A solution is found by carefully choosing dominos that complement the extra elements on the top or bottom strings.

Chapter 4

8:59 - 5 min, 26 sec

An unsolvable PCP example is used to explain why the problem is considered undecidable and why no general algorithm can solve all instances of PCP.

A third example of PCP is provided where no solution is possible, showcasing the undecidable nature of the problem.
Different possibilities are explored to solve the PCP, but each attempt leads to an infinite loop without a matching sequence.
The example illustrates why a generalized algorithm for solving all PCP instances cannot exist, as some instances may lead to infinite loops without a solution.