search
Log In

Recent questions tagged post-correspondence-problem

1 vote
2 answers
1
$\mathbf{Q57}$ Let $\mathrm{A={001,0011,11,101}}$ and $\mathrm{B={01,111,111,010}}$. Similarly , Let $\mathrm{C={00,001,1000}}$ and $\mathrm{B={0,11,011}}$. Which of the following pairs have a post correspondence solution? $\mathrm{1)\; Only \;pair \;(A,B) }$ $\mathrm{ 2) \;Only\; pair \;(C,D) }$ $\mathrm{ 3) \; Both (A,B)\; and (C,D) \; }$ $\mathrm{\; 4) \;Neither \;(A,B) \;nor\; (C,D) }$
asked Dec 20, 2019 in Theory of Computation Sanjay Sharma 664 views
0 votes
0 answers
2
0 votes
0 answers
6
0 votes
0 answers
8
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$.
asked Jul 21, 2019 in Theory of Computation Lakshman Patel RJIT 30 views
0 votes
0 answers
9
Tell whether each of the following instances of $PCP$ has a solution. Each is presented as two lists $A$ and $B$, and the $i^{th}$ strings on the two lists correspond for each $i = 1,2,\cdot\cdot\cdot\cdot$ $A=(01,001,10); \ B = (011,10,00).$ $A=(01,001,10); \ B = (011,01,00).$ $A=(ab,a,bc,c); \ B = (bc,ab,ca,a).$
asked Jul 21, 2019 in Theory of Computation Lakshman Patel RJIT 27 views
To see more, click for the full list of questions or popular tags.
...