2
$\begingroup$

Why does the Turing Machine allow for multiple final states when it would be simpler yet equivalent to work with just one? Why allow additional unnecessary states?

Is there some historical reason for this? Is the concept of multiple final states useful in any way? (Perhaps something akin to the ease of use of multi-track Turing machines, even though they're equivalent to standard ones?)

$\endgroup$
2
$\begingroup$

I've never seen a definition of Turing machines that allows multiple final states. All the definitions I've seen either have a single "halt" state or one "halt and accept" state and one "halt and reject" state.

There's no benefit to having multiple final states, though there's no real harm, either. In a finite automaton, it makes sense to have multiple final states because the automaton terminates when it runs out of input and whether or not the last state is final determines whether or not it accepts its input. (I prefer the term "accepting state", for this reason.) But, for Turing machines, the machine halts precisely when it enters a final state, regardless of what's happening on the state. So, if you have a Turing machine with multiple final states, you could just delete all but one of them and rewrite the transition function to jump to the one that remains, instead of the ones that were deleted.

$\endgroup$
1
0
$\begingroup$

The formal definition of a standard Turing machine $M$ is as follows (from An Introduction to Formal Languages and Automata, 6e - Peter Linz): $$M = (Q, \Sigma, \Gamma, \delta, q_0, □, F)$$

Aside from the other elements, $F$ is the symbol that denotes the finite set of accepting (a.k.a. final) states, and $F \subseteq Q$.

There is no restriction that states how many accepting states a particular Turing machine must have. The machines will differ from problem to problem. Nor is there any statement that states having a single accepting state is the best, and that other accepting states are "unnecessary."

I'm not sure if this is comparable to multi-track Turing machines vs. standard Turing machines, though. As you said, multi-track Turing machines are usually for the sake of simplicity and are equivalent to their standard counterparts, whereas the number of final states is usually a necessity depending on the language. The two seem to be fundamentally different issues to me.

$\endgroup$
4
  • $\begingroup$ You say "the number of final states is usually a necessity depending on the language". I don't see how that could possibly be, as the machine halts when it enters ANY final state, thus, in my view, rendering all final states equivalent. Could you provide an example? $\endgroup$
    – Tin Man
    Jun 7 '18 at 15:29
  • $\begingroup$ I agree the statement is also ambiguous and I should have made it a bit clearer. When I wrote it, I had in mind cases or examples where we would design a Turing machine for a function that receives two arguments ( $f(x, y)$) and takes on a different form depending on the values of $x$ and $y$. $\endgroup$
    – Sean
    Jun 7 '18 at 15:46
  • $\begingroup$ I can only think of one specific example right now, and I'll edit it into my answer. Please feel free to correct me or point out any inaccuracies if any. $\endgroup$
    – Sean
    Jun 7 '18 at 15:46
  • 2
    $\begingroup$ There is probably more than one formal definition of Turing machines. $\endgroup$ Jun 7 '18 at 17:45

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.