0
$\begingroup$

I'm getting confused on these both. Reject the string does a stop while loop the machine goes on and on.

My textbook has one example on a reject state and no physical one for loop:

Assume that no reject state was given. And I input a string

$1^{q_{1}}011$

After all the transitions the turing machine is now on the empty string $1011 \epsilon^{q_{8}}$ with no where else to go and its not on a accept state, so it rejects.

Now consider if its on q2 at string $0$ so $$10^{q2}11$$

And it cant go anywhere. Would that also reject? Or only if its on the empty string?

Now what is a loop? My idea is

$$1^{q_{1}}011$$

$$1^{q_{2}}011$$

$$1^{q_{1}}011$$

$\dots$

forever

$\endgroup$
0
$\begingroup$

Here's a different way to think about it. Every step, the Turing machine looks at the current cell of the tape, then does the following:

  • Optionally, move the head left or right
  • Select a new state, or accept, or reject

If it accepts or rejects, it halts and doesn't do anything further. But this won't necessarily happen: it's also possible for it to get stuck in a loop it can never get out of. Imagine the following machine:

State 0: if you see a 0, don't move, go to state 0
State 0: if you see a 1, don't move, go to state 0

It's never going to get out of state zero, it'll just stay in it forever.

It's possible for a single machine to do all three, depending on its input:

State 0: if you see a 0, don't move, go to state 0
State 0: if you see a 1, move right, go to state 1
State 1: if you see a 0, don't move, reject
State 1: if you see a 1, don't move, accept

Given the input 0 it'll loop, given the input 10 it'll reject, given the input 11 it'll accept.

$\endgroup$
  • $\begingroup$ what if there is no reject state ? Like, what would be the default reject? If it doesn't go into accept state but halts ? $\endgroup$ – Tree Garen Jun 13 at 2:53
  • $\begingroup$ @TreeGaren There's no such thing. It can halt-and-accept, or halt-and-reject, but can't just halt: it has to do one or the other. $\endgroup$ – Draconis Jun 13 at 3:01
  • $\begingroup$ @TreeGaren (Some people call the two "accept" and "halt", confusingly, in which case just "halt" means "halt-and-reject".) $\endgroup$ – Draconis Jun 13 at 3:01

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.