In a Turing Machine i understand that δ(q,x) is a transition function that results in a Change in ID. What does δ(q, Xj) =(P, y, L) mean.I understand that L stands for move left.Is P the new state and y the symbol at the tape head?Is it right?

The input string to be processed is X1X2 ... Xn, and the present symbol under the R/W head is Xi So the ID before processing Xi is

enter image description here

Before processing i understand that q is the current state and since the TM moves left the current state become p.What is y?


Yep, you're right. $y$ is the symbol that was written when the tape head moved. So the statement

$$\delta(q, x_j) = (p, y, L)$$

should be read as "in state $q$, upon reading symbol $x_j$, write a $y$ on the tape, transition to state $p$, and move left".

  • $\begingroup$ Where is this y written?at xi? I mean the R/W Head Position when the head was in state q? $\endgroup$ – techno Nov 27 '15 at 6:06
  • $\begingroup$ From the picture you posted it looks like that's correct. The $y$ is written where the read-write head of the machine was, at position $x_i$. $\endgroup$ – Eli Rose Nov 27 '15 at 6:09
  • $\begingroup$ okay.It is necessary for a Turing Machine to write a symbol? $\endgroup$ – techno Nov 27 '15 at 6:10
  • $\begingroup$ Looks like in your setup it is necessary. I think it usually is. (But if you write back the original symbol, it's as though you didn't write anything at all). $\endgroup$ – Eli Rose Nov 27 '15 at 6:13
  • $\begingroup$ okay....Thanks. $\endgroup$ – techno Nov 27 '15 at 6:14

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.