In: Computer Science
(10) Show that the Post Correspondence Problem is undecidable over the binary alphabet S = {0, 1}.
Solution 10:
Proof method 1:
We can encode every string in a finite alphabet into a binary string (like a computer using binary to encode text). As PCP for a random alphabet is undecidable, a random encoding in binary is also undecidable.
Proof method 2:
Please give thumbsup, or do comment in case of any query. Thanks.