I read this on Eric Lippert’s blog:
“Because the number of states is so large, it is often more helpful to model machines as “Turing machines”, which can have unlimited internal storage”
Immediately, a pain started in my head. I had to write what follows as a comment and on my blog!
A Turing machine is a Turing machine because it can read/write its storage in random order. This makes it recognize languages of type anbncn. Take away the write capability, it reduces to a FSA, capable of only recognizing an. Strip away the random access, languages recognized reduce to anbn.
Turing machines never have infinite states. No model for a computing machine has infinite states. What can be infinite is
1- input set (can be infinite in any case)
2- output set (can be infinite in any case)
3- memory (aka. internal storage, is infinite only starting from push down automata)
Consider the problem of having infinite states in Raymond style: What would happen if a machine could be constructed which had infinite states?
1- There would be no way to encode those states in any base. A simple state machine can be encoded in ceil( log2(states) ) number of bits. This number is always infinite for infinite states.
2- The machine’s control would alone require infinite storage.