retagged by
273 views
5 votes
5 votes

Consider the following instance of Post's Correspondence Problem:
$$\begin{array}{c|c|c} 
\text{Index} & \text{A} & \text{B} \\
\hline 1 & 10 & 101 \\
2 & 101 & 011 \\
3 & 110 & 100
\end{array}$$
The above instance of Post's Correspondence Problem has :

  1. Exactly one solution
  2. At least one solution
  3. Infinite solutions
  4. No solution
retagged by

1 Answer

6 votes
6 votes
The solution must start with index $1,$ because choices $2$ and $3$ result in an immediate mismatch. But then, the $\text{A-string}$ is shorter than the $\text{B-string}$, and there is no pair that allows the length of the $\text{A-string}$ to grow faster than that of the $\text{B-string}$. Hence, we cannot create any solution to this problem.
Answer:

Related questions

0 votes
0 votes
0 answers
4
admin asked Oct 19, 2019
316 views
In the silly Post Correspondence Problem, $SPCP$, the top string in each pair has the same length as the bottom string. Show that the $SPCP$ is decidable.