Post Correspondence Problem for alphabets of size two The alphabet consists of just two characters, $0$ and $1$. How do I go about proving that it's undecidable? 
I was thinking of reducing the general case to binary form meaning if the alphabet has more than two characters encode them into binary. I don't really know how to go about proving it though.
Any help would be appreciated. Thanks
 A: The standard proof of undecidability of PCP (see e.g. Hopcroft, Motwani, Ullman's "Introduction to Automata Theory, Languages, and Computation" section 9.4 in the third edition, or any other standard text in the area) is to set the pairs up so one of the branches is the starting configuration of a TM followed by some marker, while the other is just the marker. There are pairs which just reproduce the symbols of the first on the second (so they match), with special pairs that then give the effect of the move of the TM (second string gets the "before move" configuration around the state to match the same position on the first, first one gets "after move" configuration). If the TM accepts, another bunch of pairs takes over to level off both strings. The proof isn't hard, just very long-winded (there are many cases to consider, and make sure the construction can't derail).
Doing it for a binary alphabet is certainly possible (can code any alphabet you wish and states of the TM in binary), but doing it directly is just too much hassle.
A: The question seems ambiguous, as there are two alphabets involved in the PCP. That is, we are given two morphisms $g, h: \Sigma^*\rightarrow\Delta^*$, and it is unclear which alphabet, $\Sigma$ or $\Delta$, is meant to be of size two. This is important as the solution depends on which alphabet has size two.
As every finitely generated free monoid embeds into $\{0, 1\}^*$, the problem is trivially undecidable for maps $g, h: \Sigma^*\rightarrow \{0, 1\}^*$. That is, suppose that the PCP is undecidable for maps $g', h': \Sigma^*\rightarrow\Delta^*$, with fixed alphabets $\Sigma$ and $\Delta$, and let $k: \Delta^*\rightarrow\{0, 1\}^*$ be an injective morphism. Then the PCP is undecidable for maps $kg', kh': \Sigma^*\rightarrow\{0, 1\}^*$.
On the other hand, the problem is actually decidable for maps of the form $g, h: \{0, 1\}^*\rightarrow\Delta^*$, as proven in A. Ehrenfeucht, J. Karhumäki, and G. Rozenberg, "The (generalized) Post correspondence problem with lists consisting of two words is decidable." Theoretical Computer Science 21.2 (1982): 119-144 (doi).
