In many ways finite state machines are more important than Turing machines - because in real life there are no infinite state machines.

A Programmers Guide To Theory

Now available as a paperback and ebook from Amazon.

Contents

1. What Is Computer Science?
   Part I What Is Computable?
2. What Is Computation?
3. The Halting Problem
4. Finite State Machines
   Extract 1: Finite State Machines
5. Practical Grammar
6. Numbers, Infinity and Computation
   Extract 1: Numbers 
   Extract 2: Aleph Zero The First Transfinite
   Extract 3: In Search Of Aleph-One
   Extract 4: Transcendental Numbers
   
7. Kolmogorov Complexity and Randomness
   Extract 1:Kolmogorov Complexity 
8. The Algorithm of Choice 
9. Gödel’s Incompleteness Theorem
10. Lambda Calculus ***NEW!
    Part II Bits, Codes and Logic
11. Information Theory 
12. Coding Theory – Splitting the Bit
13. Error Correction 
14. Boolean Logic
    Part III Computational Complexity
15. How Hard Can It Be?
    Extract 1: Where Do The Big Os Come From
16. Recursion
    Extract 1: What Is Recursion
    Extract 2: Why Recursion
17. NP Versus P Algorithms
    Extract 1: NP & Co-NP
    Extract 2: NP Complete

<ASIN:1871962439>

<ASIN:1871962587>

We have already met the finite state machine as part of the Turing machine (in an eariler chapter), but now we need to consider it in its own right. There is a sense in which every real machine is a finite state machine of one sort or another while Turing machines, although theoretically interesting, are just theoretical.

We know that if the Church-Turing thesis is correct, Turing machines can perform any computation that can be performed. This isn’t the end of the story, however, because we can learn a lot about the nature of computation by seeing what even simpler machines can do. We can gain an understanding of how hard a computation is by asking what is the least that is needed to perform the computation.

As already stated the simplest type of computing machine is called a ‘finite state machine’ and as such it occupies an important position in the hierarchy of computation.

A Finite History

A finite state machine consists of a fixed number of states. When a symbol, a character from some alphabet say, is input to the machine it changes state in such a way that the next state depends only on the current state and the input symbol.

Notice that this is more sophisticated than you might think because inputting the same symbol doesn’t always produce the same behavior or result because of the change of state.

• The the new state depends only on the current state and the input

You can also have the machine output a character as a result of changing state or you can consider each state to have some sort of action associated with it.

What this means is that the entire history of the machine is summarized in its current state. All of the inputs since the machine was started determine its current state and thus the current state depends on the entire history of the machine. However, all that matters for its future behavior is the state that it is in and not how it reached this state. This means that a finite state machine can "forget" aspects of its history that it deems irrelevant to its future.

Before you write off the finite state machine as so feeble as to be not worth considering as a model of computation, it is worth pointing out that in addition to being able to "forget" irrelevant aspects of its history it can record as many as it needs. As you can have as many states as you care to invent, the machine can record arbitrarily long histories. Suppose some complex machine has a long and perhaps complex set of histories which determine what it will do next. It is still a finite state machine because all you need is a state for each of the possible past histories and the finite state machine can respond just like the seemingly complex machine. In this case the state that you find the machine in is an indication of its complete past history and hence can determine what happens next.

Because a finite state machine can represent any history and, by regarding the change of state as a response to the history, a reaction, it has been argued that it is a sufficient model of human behavior. Unless you know of some way that a human can have an unbounded history or equivalently an unbounded memory then this seems to be an inescapable conclusion - humans are finite state machines.

Representing Finite State Machines

You can represent a finite state machine in a form that makes it easier to understand and think about. All you have to do is draw a circle for every state and arrows that show which state follows for each input symbol. For example, the finite state machine in the diagram below has three states. If the machine is in state 1 then an A moves it to state 2 and a B moves it to state 3.

This really does make the finite state machine look very simple and you can imagine how as symbols are applied to it how it jumps around between states.

This really is a simple machine but its simplicity can be practically useful. There are some applications which are best modeled as a finite state machine. For example, many communications protocols, such as USB, can be defined by a finite state machine diagram showing what happens as different pieces of information are input. You can even write, or obtain, a compiler that will take a finite state machine’s specification and produce code that behaves correctly.

Many programming problems are most easily solved by actually implementing a finite state machine. You set up an array, or other data structure, which stores the possible states and you implement a pointer to the location that is the current state. Each state contains a lookup table that shows what the next state is, given an input symbol. When a symbol is read in, your program simply has to look it up in the table and move the pointer to the new state. This a very common approach to organizing games.