# Can a finite state machine represent every possible discrete deterministic system?

Consider the two following definitions:
Discrete Deterministic System: a system where inputs and outputs can have only a finite number of values, and is deterministic;
Finite State Machine: an abstract machine that can be in exactly one of a finite number of states at any given time.

My understanding is that the states in a discrete deterministic system will be a combination of the actual inputs (and possibly previous ones, if it is a system with memory), and therefore the number of states should be finite.

Provided that complexity is not a problem, is it be possible to build a finite state machine that models every possible discrete deterministic system?

If not, can you provide an example of a discrete deterministic system that cannot be represented as a finite state machine?

• I would think that you must also require the discrete system to be deterministic to make it representable with an FSM. Apr 1, 2019 at 12:35
• @ElliotAlderson That's a very good point that I have missed. Apr 2, 2019 at 8:11
• @ElliotAlderson Maybe a nondeterministic state machine could be used to model stochastic systems. Anyway, when I asked the question I was indeed thinking about deterministic systems, so I edited it. Thank you. Apr 2, 2019 at 14:19
• @Isacco No. Non-deterministic FSMs are equivalent to deterministic FSMs. The non-determinism of these is meaning something else. Apr 2, 2019 at 14:20

## 1 Answer

Any real discrete system will have a finite number of memory cells (and a finite number of states as a consequence), so it can be theoretically represented by a finite state machine.

If we also consider abstractions, then a PDA or a Turing machine are examples of discrete systems with infinite number of states.

I mention abstractions because they can represent some real systems for which FSMs are useless, even if strictly speaking such abstractions cannot be implemented in silicon. For example, a theoretical FSM representing a micro-controller with 128 bytes of RAM will have more states than there are atoms in the known universe. Representing such an MCU with a state machine is practically impossible, and if stack overflows are avoided in the implementation, I'd call it a PDA rather than an FSM.