What is the Post correspondence problem?

What is the Post correspondence problem?

The Post correspondence problem is a decision problem in computer science and mathematics that involves determining whether a given set of string pairs can be concatenated in a specific order to form identical strings.

Formally, the problem is defined as follows: Given a finite set of string pairs, each consisting of a top string and a bottom string, the task is to determine whether there exists a sequence of indices that can be chosen from the set of string pairs, such that concatenating the corresponding top strings in the chosen sequence results in the same string as concatenating the corresponding bottom strings in the same sequence.

In other words, the problem asks whether there is a way to match the top and bottom strings in such a way that the resulting concatenated strings are equal. This problem is known to be undecidable, meaning that there is no algorithm that can solve it for all possible inputs. However, it is semi-decidable, which means that if a solution exists, it can be found algorithmically.