Question 5.8: In the proof of Theorem 5.15, we modified the Turing machine...
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.
You need to handle the case where the head is at the leftmost tape cell and attempts to move left. To do so, add dominos
[\frac{\# qa}{\# rb} ]for every q, r ∈ Q and a, b ∈ Γ, where δ(q, a) = (r, b,L). Additionally, replace the first domino with
[\frac{\# }{\# \# q_{0} w_{1} w_{2} . . . w_{n} } ]to handle the case where the head attempts to move left in the very first move.
Related Answered Questions
Question: 5.30
Verified Answer:
(a) INFINITE_{TM} is a language of ...
Question: 5.28
Verified Answer:
Assume for the sake of contradiction that P is a d...
Question: 5.11
Verified Answer:
Let C = { 〈M〉 | M is a two-tape TM that writes a...
Question: 5.7
Verified Answer:
Suppose that A\leq _{m} \overline{A}[/latex...
Question: 5.6
Verified Answer:
Suppose A \leq _{m} B and B ...
Question: 5.10
Verified Answer:
Let B = {〈M,w〉 | M is a two-tape TM that writes ...
Question: 5.5
Verified Answer:
Suppose for a contradiction that A_{TM}\leq...