An undecidable problem is a problem that cannot have any algorithm to solve it.

Post correspondence problem can be solved using a brute force approach. Then how can it be an undecidable problem?

  • 2
    $\begingroup$ Can you explain your algorithm by brute force? I am confident that you have not demonstrated that your algorithm will alway terminate within finite many steps with the correct result. $\endgroup$ – Apass.Jack Apr 26 at 4:55

Post correspondence problem can be solved using a brute force approach.

No. Brute force can be applied only if the number of dominoes we are going to use, is finite. For example, if we restrict each domino to be used at most once, then the number of possibilities will be finite and we can use a brute force algorithm.

But the PCP allows us to use each domino as many time as we want, which makes the number of possible configurations infinite.

Proof of undecidability:
We will prove this by reducing "Acceptance problem of Turing Machine" to an instance of PCP. We already know that, acceptance problem of Turing Machine: $$ L^A = \{ <M,w> | M \:is \:a \:TM \:and \:M \:accepts \:w \} $$ is undecidable. Hence, if our instance of PCP is decidable, acceptance problem of Turing Machine will also be decidable, A contradiction.
The reduction involves making dominoes for all possible configurations of a TM when run on the input string. A full reduction can be found here. Let me know in the comments, if you need any clarifications on the reduction.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.