Finite state machines (FSM) are strictly less powerful than turing machines (TM). But this is not the case with infinite state machines (ISM). For example, every TM can be embedded into some ISM. The opposite (that for every ISM there exists a TM that can be embedded within the ISM), however, is not true. We can construct a counterexample from any FSM by adding an infinite number of states and no transitions.

I have two questions:

1. Are all ISMs equivalent to either a FSM or TM? (For example, does there exist an ISM that can recognize a context-free grammar, but nothing more powerful?)

2. Is there an algorithm for determining how powerful an ISM is?

Finite state machines (FSM) are strictly less powerful than turing machines (TM). But this is not the case with infinite state machines (ISM). For example, every TM can be embedded into some ISM. The opposite (that for every ISM there exists a TM that can be embedded within the ISM), however, is not true. We can construct a counterexample from any FSM by adding an infinite number of states and no transitions.

I have two questions:

1. Are all ISMs equivalent to either a FSM or TM? (For example, does there exist an ISM that can recognize a context-free grammar, but nothing more powerful?)

2. Is there an algorithm for determining how powerful an ISM is?

EDIT: If such an algorithm doesn't exist, are there any reasonable heuristics or rules of thumb?