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?
$\begingroup$
$\endgroup$
1
-
1$\begingroup$ Cross-posted: cs.stackexchange.com/q/93768/755, stackoverflow.com/q/51129854/781723. Please do not post the same question on multiple sites. Each community should have an honest shot at answering without anybody's time being wasted. $\endgroup$– D.W. ♦Jul 6, 2018 at 20:57
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
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.
$\begingroup$
$\endgroup$
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.
answered Aug 1, 2018 at 17:32