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?


1 Answer 1


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, 2015 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, 2015 at 6:09
  • $\begingroup$ okay.It is necessary for a Turing Machine to write a symbol? $\endgroup$
    – techno
    Nov 27, 2015 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, 2015 at 6:13
  • $\begingroup$ okay....Thanks. $\endgroup$
    – techno
    Nov 27, 2015 at 6:14

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .