0 votes 0 votes We showed that $PCP$ was undecidable, but we assumed that the alphabet $\Sigma$ could be arbitrary. Show that $PCP$ is undecidable even if we limit the alphabet to $\Sigma = \left\{0,1\right\}$ by reducing $PCP$ to this special case of $PCP$. Theory of Computation ullman theory-of-computation undecidable post-correspondence-problem descriptive + – admin asked Jul 21, 2019 admin 189 views answer comment Share Follow See all 0 reply Please log in or register to add a comment.
