If the set of Turing machines is countably infinite, how can a Turing machine always have a finite set of states?

Question

I have only begun studying this subject and have only completed the first few chapters of the Elements of the Theory of Computation.

I have seen the answers (on this site and elsewhere) saying that the set of all Turing machines is countably infinite. Intuitively, this makes sense to me, as I can imagine the equinumerosity of this set with the set of the natural numbers.

I have also seen the answers saying that a Turing machine cannot have infinite states by definition (the Elements provides one such definition). Moreover, an infinite state machine would be so powerful that it would not merit study, these answers say.

My question then is, how is it possible that a Turing machine must always have a finite set of states? If this were the case, could one not ask for the maximum number of states a Turing machine can have? And would one not expect this to be some fixed number?

I feel there are points about this theory that I am missing.

Answer 1

You are mentally reversing two logical quantifiers, that are implicit in the statement "Turing machines must always have a finite set of states".

You read this sentence as "there exists a finite set $S$ of states such that all Turing machines $M$ use only states in $S$". Logically, this is a "$\exists S \forall M$" property.

Instead, the sentence is meant to be read as "for each Turing machine $M$, there exists a finite set $S$ of states such that $M$ uses only states in $S$". Logically, this is a "$\forall M\exists S$" property.

This is a matter of natural language being sometimes too easy to be misread.

Answer 2

If the set of integers is infinite, how can any integer be finite?

If the set of words of $\{0,1\}^*$ is infinite, how can any word be finite?

You get the idea.

Answer 3

Maybe consider a simpler example. All Strings over the alphabet $\Sigma = \{0, 1\}$ have finite length, but there are an infinite number of strings over $\Sigma$. The reason for this is simple, suppose the longest String $x \in \Sigma^*$ has length $|x| = m \in \mathbb{N}$. Then we can build a new string $y = x1$ of length $|y| = m + 1$, so $x$ can't have been the longest ↯.

Note that both $x$ and $y$ have finite length, but that doesn't mean that the length of strings must have an upper bound.

The same argument works on Turing machines, if $M$ is the Turing machine with the greatest number of states $m$, then you can always build a new machine that has $m + 1$ states by simply adding a superfluous state.

Answer 4

Each individual Turing machine has a finite fixed number of states. But not every two Turing machines have the same number of states.

There are Turing machines with one state, there are Turing machines with two states, there are Turing machines with three states, and this up to (excluding) infinity.

If we forget about Turing machines, the set of natural numbers is countably infinite, but every number is fixed and not infinite.

Answer 5

Any (Turing Machine, initial tape contents) pair may be transformed into a Turing machine where each tape position is either marked or unmarked (two states), and where the tape is initially blank. The complexity of any such machine may be be expressed using a single parameter: the number of states. For every number of states, some machines will terminate while others won't. Every machine that terminates will execute some finite number of steps and will be in a different state for each of them. Thus, the total number of states visited by machines having any given number of states will the sum of a finite set of finite numbers, i.e. a finite number. This number grows so quickly relative to the number of states that no Turing Machine could compute it for arbitary N, but it's nonetheless finite.