1
$\begingroup$

I'm reading Sipser's Introduction to the Theory of Computation (2nd ed.), and I am having trouble understanding one of the cases of Turing machine computation. Sipser describes the cases in terms of how one configuration yields another after a step of computation. For example, if the head is not at either end of the configuration and is moving leftward:

Suppose that we have $a$, $b$, and $c$ in $\Gamma$, as well as $u$ and $v$ in $\Gamma^*$ and states $q_i$ and $q_j$. In that case $uaq_ibv$ and $uq_jacv$ are two configurations. ... $uaq_ibv$ yields $uq_jacv$ if the transition function $\delta(q_i,b)=(q_j,c,L)$.

where $\Gamma$ is the tape alphabet and $L$ means the head is moving leftward.

I understand this case, as well as the case where the head moves rightward without being at either end and the cases where the head is at the left-hand end. However, I don't understand the cases where the head is at the right-hand end. Here's how Sipser explains the end cases:

Special cases occur when the head is at one of the ends of the configuration. For the left-hand end, the configuration $q_ibv$ yields $q_jcv$ if the transition is left-moving (because we prevent the machine from going off the left-hand end of the tape), and it yields $cq_jv$ for the right-moving transition. For the right-hand end, the configuration $uaq_i$ is equivalent to $uaq_i⌴$ because we assume that blanks follow the part of the tape represented in the configuration. Thus we can handle this case as before, with the head no longer at the right-hand end.

where ⌴ is the blank symbol.

I'm not sure how to handle this case as I don't know where "as before" refers to. I conceptualize the head like a text cursor stuck in overtype mode, and so my initial guess would be that $uaq_i⌴$ yields something like $uacq_j⌴$ when moving rightward and $uq_iac⌴$ when moving leftward, but I worry that I've missed something. Am I on the right track or am I way off base?

$\endgroup$
1
$\begingroup$

Yes, your understanding is correct.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.