- Problem Statement<\/a><\/li>
- Representation of the Problem<\/a><\/li>
- Domino Form<\/a><\/li>
- Table Form<\/a><\/li><\/ul>
- Proof of Undecidability<\/a><\/li>
- FAQs<\/a><\/li>
- Q.1 What are some other well-known undecidable problems related to a Turing Machine?<\/a><\/li>
- Q.2: What is the Halting Problem?<\/a><\/li><\/ul><\/ul><\/div><\/div><\/div><\/div>\n\n\n\n
Problem Statement<\/h2>\n\n\n\n
The Post Correspondence Problem is a popular undecidable decision problem, <\/strong>introduced by Emil Post<\/strong> in 1946. Being a problem, simpler than the Halting Problem<\/strong>, it is often used in proofs of undecidability. <\/p>\n\n\n\n
The problem is stated formally as follows,<\/p>\n\n\n\n
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.<\/p>\n\n\n\n
For example, <\/p>\n\n\n\n
Consider the lists, <\/p>\n\n\n\n
a = [b, a, aba, bb]<\/strong>
b = [ba, ba, ab, b]<\/strong><\/p>\n\n\n\nFor these 2 lists, the sequence [1, 2, 1, 3, 3, 4]<\/strong> will give the solution for the Post Correspondence Problem. The String that will be formed in both cases will be \u201cbababaababb\u201d<\/strong> by following the above sequence.<\/p>\n\n\n\n
<\/figure>\n\n\n\n
Representation of the Problem<\/h2>\n\n\n\n
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:<\/p>\n\n\n\n
Domino Form<\/h3>\n\n\n\n
Table Form<\/h3>\n\n\n\n
Proof of Undecidability<\/h2>\n\n\n\n
Undecidability<\/strong> of a problem means that there is no specific algorithm, which can accurately determine, whether the given problem has a solution or not.<\/p>\n\n\n\n
A well-known problem that is undecidable is the Turing Problem<\/strong>. So, if we can remodel\/reduce the Turing Problem<\/strong>, into the Postman Correspondence Problem, <\/strong>we can prove its undecidability as well.<\/p>\n\n\n\n
A brief sketch of the proof is as follows,<\/p>\n\n\n\n
Consider an instance of the Postman Correspondence Problem<\/strong>, 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<\/strong> 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.<\/p>\n\n\n\n
FAQs<\/h2>\n\n\n\n
- Q.2: What is the Halting Problem?<\/a><\/li><\/ul><\/ul><\/div><\/div><\/div><\/div>\n\n\n\n
- Table Form<\/a><\/li><\/ul>
- Representation of the Problem<\/a><\/li>
![\"\"](\"https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/11\/image1-4-1024x241.png\")
<\/figure>\n\n\n\n![\"\"](\"https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/11\/image3-1.png\")
<\/figure>\n\n\n\n![\"\"](\"https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/11\/image2-1-1024x254.png\")
<\/figure>\n\n\n\n