Is it a state machine when it works with memory?

Question

In the state machines, it is said that it only holds information about the current state and based on the input, a next state is transitioned to.

What about a situation where there are additional conditions, such as:

State A (input X) ---> State B

State B
(input X) AND (SomeValue>=100) ---> State C
(input X) AND (SomeValue < 100) ---> State D

Is this still a state machine?

Answer 1

State machines can have no memory (like finite automata), memory whose access is restricted in some way (such as pushdown automata with stack access), or memory whose access is essentially unlimited (such as a Turing machine or Random Access Machine (RAM)). I think it's fair to call all of these things state machines since they change behavior based upon their internal states.

If the automaton is not writing memory, but only reading memory, and it has no ability to "go back" and read memory it had read before, then no matter what memory it's reading, it's equivalent to having no memory and simply responding to the normal inputs it receives. For instance, a Turing Machine that cannot write and can only read its tape from left to right is equivalent to a finite automaton; a pushdown automaton that cannot push symbols onto the stack is equivalent to a finite automaton; etc.

If the automaton can write the contents of memory and has an ability to eventually read those contents back - and if the amount of memory which can be so manipulated is not fixed - then it remains a state machine but is no longer equivalent to a finite automaton. Note that I say the amount of memory must not be fixed: if the amount of memory is fixed, then any machine using it is equivalent to a finite automaton with repeated states for every possible configuration of all memory. Even the computer you're on right now is no more powerful than a finite automaton: in fact, your computer is infinitely less powerful than a general finite automaton, since there are infinitely many regular languages that cannot possibly be accepted by any physically realizable computer.