I was working on some questions in the book "Elements Of The Theory Of Computation", by Lewis and Papadimitriou, and I need help with one question - question 4.1.8 (chapter 4):

Give the full details of the turing machines illustrated:


enter image description here

I managed to solve everything but this, and that is because I don't know what the dot is used for. Couldn't find any explanation in the book. There are two more machines in this question (without dots), but I solved them.

  • $\begingroup$ This is all that was written. Earlier in the book, was explained that L means move one step left. So I understood that this machine moves twice to the left. But then what? I don't know whether this dot is a mistake, a part of the alphabet (which isn't described at all), or some action that needs to be performed but was not discussed earlier. $\endgroup$ – eevee25 Aug 15 '16 at 7:42
  • $\begingroup$ Recall that "if $a\in\Sigma$, then the $a$-writing machine will be denoted simply as $a$". What if the dot represents just the TM that writes a dot? $\endgroup$ – Dmitri Chubarov Aug 15 '16 at 7:54
  • $\begingroup$ This is what I am asking. I thought that perhaps someone has an answer from the solution manual, or maybe knows what this means in general. $\endgroup$ – eevee25 Aug 15 '16 at 8:35

Your Answer

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

Browse other questions tagged or ask your own question.