# How post correspondence problem is undecidable?

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?

• 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. – Apass.Jack Apr 26 at 4:55

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 \: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.