With 2 string pairs , PCP was shown to be decidable in 1981 .
He showed that the Post Correspondence Problem ( PCP ) of satisfying their constraints is , in general , undecidable .
With 2 string pairs , Post Correspondence Problem was shown to be decidable in 1981 .
He showed that the Post Correspondence Problem ( PCP ) of satisfying their constraints is , in general , undecidable .