As promised (threatened?) Tech Tuesday is embarking on a look at the theoretical side of computer science. We also call this the theory of computation and it deals with two big questions: first, what are the limits to computation (known as computability) and second, how efficiently can we compute things (known as computational complexity). Now in order to be able to make formal arguments in trying to answer these questions it helps a lot to have models of computation that are simpler and more tractable than the computers that we are actually using.
Today we will start by getting to know so-called finite state machines (FSM) which are a specific type of what is called automata (by which we mean abstract machines). An FSM consists of a finite set of states and transitions between those states. Let’s consider a simple example to make that clearer. Before starting to write this blog post I made a coffee on our Nespresso machine. We can model that machine as an FSM by enumerating the states the machine can be in.
Our simplest model might be that the machine is either on or off. The transition between the two states is the caused by the operating the on / off switch on the machine:
This has all the basics of a FSM. There are two states (off and on) and transitions between them. At any one moment that machine is guaranteed to be in exactly one of these states. And for a given state and input we know precisely what the new state is.
Now that is not yet a satisfying model because, well, it doesn’t make any coffee. Our “on” state is really two states which we might call “rest” and “brew” which gives us the following slightly more complicated model:
While this may still seem extraordinarily simplistic, we can already see the utility of FSMs emerging here. We can ask questions of the model, such as: what sequence of inputs leads from the brew state to the off state?
This is non-trivial, because we are seeing that in the current model to get from brew to off we have to pass through rest. That is not the reality of our Nespresso machine where you can in fact press the on/off switch even when the machine is brewing as captured in the following FSM:
But that may not be desirable. For instance, it might be damaging to the internals of the coffee maker to be turned off while it is brewing. In that case maybe the on/off switch should be disabled while brewing. By modeling the Nespresso machine as a FSM, we can use formal methods to analyze its operations.
We can specify algorithms that operate on the FSM and let us answer such questions as is there any sequence of steps that gets us from a state A to a state B? Or asked differently, is state B reachable at all? We can also ask and answer the question as to what all the possible paths through the FSM are. And we can ask questions about how many states are required to model a particular problem and how it might take to get from state A to state B.
FSMs are a particularly useful model of computation exactly because we can come up with definitive answers to all of these questions. That’s very powerful but as we will see also comes at a big price.
