1
$\begingroup$

I'm still fairly new to Turing Machines, but I've been doing some research.

I know that a Turing Machine can have an infinite tape and that it requires a finite number of states, but does it necessarily follow that a Turing Machine can have an infinite number of accept states?

I keep seeing different layouts when formally defining Turing Machines, for example:

M = (Q, Σ, Γ, τ, s, F).

1) F ⊆ Q is the set of final or accepting states. (plural)

2) F ⊆ Q is the accept state. (singular)


So I'm just wondering which one is correct?


Any help would be greatly appreciated.

Improve this question
$\endgroup$
2
  • 1
    $\begingroup$ Possible duplicate of Can a Turing machine have infinite states? $\endgroup$
    – advocateofnone
    Commented Nov 23, 2015 at 6:12
  • 1
    $\begingroup$ You are talking about three different cases here: Turing machines with one accepting state, with several (a finite number of them) or infinite ones. Which ones do you mean? $\endgroup$
    – vonbrand
    Commented Nov 23, 2015 at 12:26

3 Answers 3

Reset to default
6
$\begingroup$

In the standard Turing machine, the set of states $Q$ is finite $|Q| < \infty$. Therefore, it cannot have infinite final states. However, it may, or may not have multiple final states. This will not change the power of the machine (i.e., one final state is equivalent to $k$ final states).

Improve this answer
$\endgroup$
2
  • $\begingroup$ Sorry but why are they equivalent? I don't seem to get it. $\endgroup$
    – User Not Found
    Commented Sep 7, 2017 at 3:43
  • $\begingroup$ @UserNotFound Because once you get to any final state, the Turing machine stops and accepts the input. Since it stops, the final states are indistinguishable from each other. You can easily take any two final states F1 and F2, replace F2 with F1, and there would be no difference in how the Turing machines functioned. $\endgroup$
    – Tin Man
    Commented Jun 6, 2018 at 21:17
2
$\begingroup$

Turing machines are defined to have only a finite number of states. Since every accepting state is a state, it's impossible to have infinitely many accepting states. Being allowed to have more than one of something is not the same as being allowed to have infinitely many.

Improve this answer
$\endgroup$
1
$\begingroup$

As for the difference between one and many accepting states, if you have a TM with multiple accepting states, you can add a new single accepting state and make sure that from the accepting states you can get to your new state in one move. Thus one/many doesn't affect the power of the machine, but it might simplify proofs. Thus you'll see varied definitions, all equivalent.

Improve this answer
$\endgroup$

Your Answer

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

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