Question

Post Correspondence problem is

(a) decidable decision problem

(b) undecidable decision problem

(c) not a decision problem

(d) none of the mentioned

This question was posed to me in unit test.

I'm obligated to ask this question of Rice’s Theorem, Properties and PCP topic in chapter Undecidability of Automata Theory

Answer 1

Correct answer is (b) undecidable decision problem

Explanation: Post Correspondence problem is an undecidable decision problem that was introduced by Emil Post in 1946. Being simpler than halting problem, it can be used in proofs of undecidability.