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: 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?)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?
Difference between infinite state machines and turing machines
automata theory;turing machines
A pushdown automaton is a particular case of ISM, so it is possible to recognize a context-free language with ISM.How would you give your ISM to the algorithm? Anyway a lot of problems are already undecidable for Pushown Automata (particular case of ISM) like equivalence or universality, so I guess the answer would be no for any reasonable question here.