[Solved]: Can a Turing Machine have infinite accept states?

Problem Detail: 

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.

Asked By : Max

Answered By : Ran G.

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).

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/49822

 Ask a Question

 Download Related Notes/Documents