Question

Question: 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.

Short answer

The modified PCP is: $\left[\frac{\#}{\#\#{\text{q}}_0,{\text{w}}_1,{\text{w}}_2\dots {\text{w}}_{\text{n}}}\right]$.

Step-by-step solution

State Theorem 5.15

Theorem 5.15 state that PCP is undecidable problem.

A problem is undecidable if no Turing Machine exist which will halt in finite amount of time.

To modify PCP construction

Referring to Theorem 5.15, a Turing Machine M is modified in such a way that the head never move in left direction of the tape. To solve the above question, let’s assume that no change is made to the Turing Machine M.

Since no change is made in M, so let user make modification in Post Correspondence Problem (PCP).

Post Corresponding Problem: Post Corresponding Problem is undecidable problem where we have more than one tile which contains multiple strings. The goal of this problem is to arrange the order of strings such that the numerator and denominator are identical.

So, use carried out modification in such way: Let’s assume a situation where the head of Turing Machine is at the extreme leftmost block (cell) and wants to move further in left direction, to make it possible, add dominos to left: $\left[\frac{\#\text{qa}}{\#\text{rb}}\right]$

Here, for every q and r belongs to Q, i.e., role="math" localid="1663233453684" $q,r\subset Q$ also a and b belongs to r , i.e., .$a,b\subset r$.

Now, replace the first dominos as follows:

$\left[\frac{\#}{\#\#{\text{q}}_0,{\text{w}}_1,{\text{w}}_2\dots {\text{w}}_{\text{n}}}\right]$

So, using above method to handle the case when head tries to move in left direction.