0
$\begingroup$

Hey guys in a turing machine can a state go to itself by reading a letter. For example,

enter image description here

q2 reading a 'c' to go to itself. Is that possible?

Or does it need to read a tape alphabet, such as $ to read that c and then go back to q2?

$\endgroup$
1
$\begingroup$

Yes, a state can go to itself when seeing any symbol. (As Steven's answer says, the analogous question for head movement - whether the head of the Turing machine has to move at each stage, or whether it can stay put at a given moment - varies from definition to definition, but I've never seen a definition which prohibits a state from looping to itself.)

  • Note that this is a particularly natural thing to allow: it's basically a "while" command.

However, as with many aspects of Turing machines, tweaking the definition to rule it out isn't significant: Turing machines which prohibit states from looping to themselves are no weaker than Turing machines which allow states to loop to themselves. This is a good exercise.

$\endgroup$
1
  • $\begingroup$ Thanks as Steven said, I can have a new intermediate state, but I wanted to know can a state loop itself. Your answer seems to imply that it can $\endgroup$ – Calculus Cold May 14 '20 at 19:11
0
$\begingroup$

That depends on the exact definition of Turing Machine that you are using.

I am used to a definition where the transition function $\delta$ is a function from $(Q \setminus F)$ to $Q \times \Sigma \times M$, where $Q$ is the set of all states, $F$ is the set of final states, $\Sigma$ is the tape alphabet, and $M=\{\text{left, right, stay}\}$ specifies the movement of the head.

In this case a Turing machine can definitely have a transition of the type $\delta(q, c) = (q, \alpha, \text{stay})$ (for any $\alpha \in \Sigma$).

However, according to Wikipedia the set of allowed movements in the transition function used by the definition from Hopcroft & Ullman does not contain $\text{stay}$.

Anyway, since this can be simulated by going to a new intermediate state while moving the head (left or right), and then going back to the intended state while repositioning the head on the previous position, there is no difference in the computing power or time complexity (up to multiplicative constants) among the two definitions.

$\endgroup$
2
  • 1
    $\begingroup$ This is addressing whether "stay" is a valid movement command, but the question seems to be whether a state can loop back to itself on a given input. The latter is always allowed. $\endgroup$ – Noah Schweber May 14 '20 at 18:29
  • $\begingroup$ Thanks. I am using the definition that has a stay movement. But I wanted to know if a state can loop itself in a turing machine. I can obviously create a new state and loop. But I wanted to know if I can do the same state looping as a FSA can $\endgroup$ – Calculus Cold May 14 '20 at 19:12

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.