Hi Kranar. See my other post with the reference to linear bounded automata. I think you're right on all points. Also, I agree that "simulates" is probably the

Hi Kranar. See my other post with the reference to linear bounded automata. I think you're right on all points. Also, I agree that "simulates" is probably the wrong word. There would be a one-to-one mapping between FSM states and restricted-TM (or Linear Bounded Automaton) states and it would "simulate" the TM by stepping through mapped states until it reached a terminal state, but the number of states required and the transition table would be ridiculous. I don't think it would exactly be a look-up table, but it's close. (i.e., it would be O(2^N), for a binary alphabet, to construct the transition table, but looking up the terminal state for each input state would also be O(2^N)).