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 a^{n}b^{n}c^{n}. Take away the write capability, it reduces to a FSA, capable of only recognizing a^{n}. Strip away the random access, languages recognized reduce to a^{n}b^{n}.

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.

### Like this:

Like Loading...

*Related*

## Leave a Reply