## Problem Statement

The Post Correspondence Problem is a popular **undecidable decision problem, **introduced by **Emil Post** in 1946. Being a problem, simpler than the **Halting Problem**, it is often used in proofs of undecidability.

The problem is stated formally as follows,

Given 2 lists of words, find if there exists a sequence such that the concatenation of the words in this order, gives the same word for both lists.

For example,

Consider the lists,

**a = [b, a, aba, bb]****b = [ba, ba, ab, b]**

For these 2 lists, the sequence **[1, 2, 1, 3, 3, 4]** will give the solution for the Post Correspondence Problem. The String that will be formed in both cases will be **“bababaababb”** by following the above sequence.

## Representation of the Problem

Considering the 1st list to act as the numerator, and the 2nd list to act as the denominator for the problem, the problem can be represented in 2 forms:

### Domino Form

### Table Form

## Proof of Undecidability

**Undecidability** of a problem means that there is no specific algorithm, which can accurately determine, whether the given problem has a solution or not.

A well-known problem that is undecidable is the **Turing Problem**. So, if we can remodel/reduce the **Turing Problem**, into the **Postman Correspondence Problem, **we can prove its undecidability as well.

A brief sketch of the proof is as follows,

Consider an instance of the **Postman Correspondence Problem**, which can, on an arbitrary input, simulate the computation of an arbitrary Turing Machine. We note that a match will occur, if and only if the Turing Machine would accept the input. The problem of deciding **whether a Turing Machine will accept the given input or not** is a well-known undecidable problem. Since the Postman Correspondence Problem reduces into this particular problem, we can say the Postman Correspondence Problem is undecidable as well, which completes our proof.

## FAQs

### Q.1 What are some other well-known undecidable problems related to a Turing Machine?

**Ans:** The** Membership, Finiteness, and Emptiness** of a Turing Machine are all well-known undecidable problems related to a Turing Machine.

### Q.2: What is the Halting Problem?

**Ans**: The **Halting Problem** is the problem of determining from the given description of an arbitrary computer program and an input, whether will the program will terminate or will continue running indefinitely into the future,