311 views
0 votes
0 votes
In the proof of Theorem $5.15$, we modified the Turing machine $M$ so that it never tries to move its head off the left-hand end of the tape. Suppose that we did not make this modification to $M$. Modify the $PCP$ construction to handle this case.

Please log in or register to answer this question.

Related questions

0 votes
0 votes
0 answers
1
0 votes
0 votes
0 answers
3
admin asked Oct 19, 2019
303 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.
0 votes
0 votes
0 answers
4