# Turing machine loop and reject example

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

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.

• what if there is no reject state ? Like, what would be the default reject? If it doesn't go into accept state but halts ? – Tree Garen Jun 13 '19 at 2:53
• @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. – Draconis Jun 13 '19 at 3:01
• @TreeGaren (Some people call the two "accept" and "halt", confusingly, in which case just "halt" means "halt-and-reject".) – Draconis Jun 13 '19 at 3:01