0
$\begingroup$

I want to design a Turing machine that accepts at most 3 0s. Now, I have designed one, which goes to accept state overtime it sees 1, 2 and 3 0s and rejects any further 0s. I wanted to know if it is okay for TM to go to accepting state from 3 different states?

$\endgroup$
1

2 Answers 2

1
$\begingroup$

Of course, a Turing machine can transition to a given state from as many other states as you like. Machines used in halting problem reductions usually have an "infinite loop" state that only transitions back to itself, and many other states that transition into that one.

$\endgroup$
1
$\begingroup$

As Draconis says, you can go to the accept (or reject) state from as many states as you want.

However, it would make no difference if you could only go to the accept state from one state. Suppose you wanted to go to the accept states from states $S_1, \dots, S_k$. Then just make a new state $X$ such that you go from each of $S_1, \dots, S_k$ to $X$ and then from $X$ to the accepting state.

The definition of Turing machines is, in general, very flexible. You can add all kinds of restrictions to the definition without changing the power of the machines.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.