From Finite State Machines to Computers

In this chapter, you will discover the fundamental nature of computers. Our goal is to explain what makes a computer a computer. These concepts are important because you can’t understand how a computer works until you appreciate the implications of its sequential nature.

Once we’ve introduced the concept of digital systems, the next chapter will demonstrate how a computer operates by fetching instructions from memory and executing them. After that, we will introduce Python and demonstrate how you can write a program to simulate a computer and observe its operations. This book is all about learning by doing; by building a computer with software, you will learn how it operates and how to extend and modify it.

The remainder of this book will look at a real computer, a Raspberry Pi, and show you how to write programs for it and observe their execution. In doing so, we will move on from simulating a hypothetical computer to learning about a real computer.

A computer is a deterministic symbol processing machine. But what does that mean? Deterministic tells us that a computer always behaves in the same way when operating under the same conditions (that is, programs and inputs). If you use a computer to evaluate √2, you will always get the same result, no matter how many times you perform the operation. Not all systems are deterministic – if you toss a coin, the sequence of heads and tails is not predictable.

When we say that a computer is a symbol processing machine, we mean that it takes in symbols and operates on them to provide new symbols as an output. These symbols are anything that can be represented in digital form: letters, words, numbers, images, sound, and video. Consider a computer that’s playing chess. The input symbols that are received by the program correspond to the moves made by a player. The program operates on the input symbols according to a set of rules and produces an output symbol – the computer’s move.

Although we’ve just provided a theoretical definition of a computer, it is important to appreciate that programming involves translating information in the real world into symbols that can be manipulated by a computer – writing a set of rules (that is, a program) that tells the computer how to manipulate the symbols, and then converting the output symbols into a form that is meaningful to a human. The symbols that are processed by a computer have no intrinsic meaning to the computer – a certain pattern of bits (that is, the symbol) might represent a number, a name, a move in a game, and so on. The computer processes these bits to produce a new pattern of bits (that is, an output symbol) that has a meaning only to the programmer or user.

We are going to pose a simple problem and then solve it. Our solution will lead us to the concepts of algorithms and computers, and also introduce key concepts such as discrete digital operations, memory and storage, variables, and conditional operations. By doing this, we can determine the types of operations a computer needs to perform to solve a problem. After this, we can ask, “How can we automate this? That is, how can we build a computer?”

It’s a trite statement, but once you understand a problem, you’re well on the way to finding a solution. When you first encounter a problem that requires an algorithmic solution, you have to think about what you want to do, rather than how you are going to do it. The worst approach to problem solving is to start writing an algorithm (or even actual computer code) before you have fully explored the problem. Suppose you were asked to design a cruise control system for an automobile. In principle, this is a very simple problem with an equally simple solution:

IF cruise control on THEN keep speed constant
                     ELSE read the position of the gas pedal

Couldn’t be simpler, could it? Well, what happens if you’ve selected cruise control and someone pulls out in front of you? You could brake, but this algorithm would attempt to keep the speed constant while you are braking by applying full throttle at the same time. Alternatively, you might suggest that the act of braking should disengage the cruise control mechanism. But is the cruise control to be disengaged permanently, or should the automobile accelerate to its previous speed once the braking action has ceased? You have to think about all the aspects of the problem.

Even if you design a correct algorithm, you have to consider the effect erroneous or spurious data will have on your system. One of the most popular criticisms of computers is that they produce meaningless results if you feed them with incorrect data. This idea is summed up by the expression garbage in, garbage out (GIGO). A well-constructed algorithm should detect and filter out any garbage in the input data stream.

In this chapter, we will introduce the following topics:

• The finite state machine
• Solving a problem algorithmically

You can find the programs used in this chapter on GitHub at https://github.com/PacktPublishing/Practical-Computer-Architecture-with-Python-and-ARM/tree/main/Chapter01.

There are remarkably few fundamental concepts that you need to know about to understand what a digital computer does and how it operates. One of the most important concepts is discrete, which lies at the heart of both computer operation and computer programs.

Computers operate on discrete data elements – that is, elements whose values are chosen from a fixed and finite range of values. We use discrete values in everyday life – for example, the letters of the Roman alphabet that belong to the set {A...Z}. A letter is never between two possible values. It’s the same with the days of the week; you can have one of seven days, but you can’t have a day that is slightly Monday or just a little bit bigger than Wednesday. In the case of computers, the fundamental data element is the bit, which can only have values of 0 or 1, and all its data structures are represented by strings of 1s and 0s.

As well as discrete data values, we can have discrete points in time. Imagine that time moves in one direction, from one discrete point to another discrete point. Nothing exists between two discrete points in time. It’s a bit like a digital clock that goes from 12:15:59 to 12:16:00. There’s nothing in between.

Now, imagine state space, which is a grandiose term for all the states a system can be in (for example, a plane can be in the climbing, descending, or level flight state). States are a bit like time, except that you can go forward or backward between discrete points in state space. If there are a limited number of possible states, a device that models the transitions between states is called a finite state machine (FSM). An elevator is a finite state machine: it has states (position at the floors, doors open or closed, and so on) and inputs (the elevator call buttons, floor selection buttons, and door open and close buttons).

Before we take a serious look at FSMs, let’s begin with a simple example of how to use FSMs to describe a real system. Consider the TV of yesterday, which is a device with two states: on and off. It is always in one of these two states, and it can move between these states. It is never in a state that is neither on nor off. Modern TVs often have three states – on, standby, and off– where the standby state provides a fast-on mechanism (that is, part of the electronics is in an active on state, but the display and sound system are powered down). The standby state is often called the sleep state or idle state. We can model discrete states using a diagram. Each state is represented by a labeled circle, as demonstrated in Figure 1.1:

Figure 1.1 – Representing the three states of a television

Figure 1.1 shows the three states, but it doesn’t tell us the most important information we need to know: how we move between states. We can do this by drawing lines between states and labeling them with the event that triggers a change of state. Figure 1.2 does this. Please note that we are going to construct an incorrect system first to illustrate some of the concepts concerning FSMs:

Figure 1.2 – Representing the states of a television with transitions

In Figure 1.2, we labeled each transition by the event that triggers it; in each case, it’s pressing a button on the remote controller. To go from off to on, you have to first press the standby button and then the on button. To go between on and standby, you must press the on button or the standby button.

We’ve forgotten something – what if you are already in a state and you press the same button? For example, let’s say the TV is on, and you press the on button. Also, what’s the initial state? Figure 1.3 rectifies these omissions.

Figure 1.3 has two innovations. There is an arrow to the off state marked Power on. This line indicates the state the system enters when you first plug it into the electricity supply. The second innovation in Figure 1.3 is that each state has a loop back to itself; for example, if you are in the on state and you press the on button, you remain in that state:

Figure 1.3 – The TV control with initialization

The state diagram shown in Figure 1.3 has both a logical error and an ergonomic error. What happens if you are in the off state and press the on button? If you are in the off state, pressing the on button (in this system) is incorrect because you have to go to standby first. Figure 1.4 corrects this error by dealing with incorrect inputs:

Figure 1.4 – The TV control with wrong button correction

Figure 1.4 now provides correct operations from any state and includes the effect of pressing buttons that cause no change of state. But we still have the ergonomic error – that is, it’s a correct design that behaves in a way that many would consider poor. The standby state is a convenience that speeds up operations. However, the user does not need to know about this state – it should be invisible to the user.

Figure 1.5 demonstrates the final version of the controller. We’ve eliminated a standby button, but not the standby state. When the user presses the on button, the system goes directly to the on state. However, when the user presses off when in the on state, the system goes to the standby state. From the standby state, pressing the on button results in the power on state, while pressing off results in the power off state. Note that the same action (pressing off) can have different effects, depending on the current state:

Figure 1.5 – The TV control with a hidden standby state

We’ve labored with this example because the notion of FSMs is at the heart of all digital systems. All digital systems, apart from the most trivial, move from state to state, depending on the current input and past states. In a digital computer, the change-of-state trigger is the system clock. A modern computer operating at a clock speed of 4 GHz changes state every 0.25 x 10-9 s or every 0.25 ns. Light traveling at 300,000 km/s (186,000 mph) moves about 7.5 cm or 3 inches during a clock cycle.

Traffic lights example

Let’s look at a second example of an FSM. A classic example of an FSM is traffic lights at a crossroads. Consider an intersection with traffic moving north-south or east-west. The traffic may move in only one direction at a time. Assume that this is a system with a clock and a change of state is permitted every minute:

Table 1.1 – Traffic lights sequence table

Suppose the traffic is currently flowing north-south. At the next clock, it may either remain flowing north-south or the lights may change to allow east-west traffic. Similarly, if traffic is flowing east-west, at the next clock, it may either remain flowing east-west or the lights may change to permit north-south traffic.

We can use Table 1.1 to describe this system. We have provided the current state of the lights (direction of traffic flow), indicated whether any traffic had been detected in either the north-south or east-west direction, the action to be taken at the next clock, and the next state. The traffic rule is simple: the lights remain in their current state unless there is pending traffic in the other direction.

We can now convert this table into the FSM diagram shown in Figure 1.6. Note that we have made the east-west state the power on state; this is an arbitrary choice:

Figure 1.6 – A finite state machine for Table 1.1

What have we learned? The most important point is that a system is, at any instant, in a particular state and that a transition to another state (or a transition back to the current state) is made according to a defined set of conditions. The FSM has several advantages, both as a teaching tool and a design tool:

• It uses a simple intuitive diagram to describe a system with discrete states
• The state transition diagram (if correct) provides a complete and unambiguous way of describing a system
• The FSM is also an abstract machine in the sense that it models a real system, but we don’t have to worry about how the FSM is implemented in real hardware or software
• Any FSM can be implemented either in hardware or software; that is, if you can define a state diagram on paper, you can build the circuit in dedicated hardware or write the program to run on a general-purpose computer

I have included a brief introduction to FSMs because they can be considered a precursor to the digital computer. An FSM is designed to carry out a specific task; this is built into its hardware. A computer has some of the characteristics of an FSM but you can program the transitions between states.

Solving a simple problem algorithmically

Now that we’ve introduced FSMs, we will describe a problem, solve it, and then construct our computer. A bag contains a mixture of red and white tokens. Suppose that we take a token at a time out of the bag and continue until we have removed three consecutive red tokens. We want to construct an algorithm that tells us to stop removing tokens from the bag when three reds in a row have been detected.

Before creating an algorithm, we’ll provide an FSM for this problem:

Figure 1.7 – FSM for a three-token detector

As you can see, there are four states. We begin in state S0. Each time a token is received, we move to the next state if it’s red, and back to the initial state if it’s white. Once we’ve reached state S3, the process ends. Now, we’ll perform the same operation algorithmically.

If a white token is represented by the symbol W, and a red token by R, a possible sequence of tokens might be RRWRWWWWRWWRRR (the sequence is terminated by the three Rs). An algorithm that tells us when to stop removing tokens can be written in the following form:

• Line 1: Get a token from the bag
• Line 2: If the token is white, then go back to line 1
• Line 3: Get a token from the bag
• Line 4: If the token is white, then go back to Line 1
• Line 5: Get a token from the bag
• Line 6: If the token is white, then go back to Line 1
• Line 7: Success – three consecutive red tokens have been taken out of the bag

As you can see, the algorithm is expressed in plain English. It is read from top to bottom, line by line, and the action specified by each line is carried out before the next line is processed. In this algorithm, each line has a unique name (that is, Line 1, Line 2, and so on). Labeling a line enables us to refer to it; for example, when the algorithm states that we must go back to Line 1, this means that the next step to be carried out is specified by Line 1, and we continue carrying out actions from Line 1 onward. This algorithm is not entirely satisfactory – we haven’t checked that the bag contains only red and white tokens, and we haven’t dealt with the situation in which we run out of tokens before we locate the sequence we’re looking for. At the moment, we are not concerned with these details.

There’s no single solution to this problem – more often than not, lots of algorithms can be constructed to solve a given problem. Let’s derive another algorithm to detect a sequence of three consecutive red tokens:

Line 1: Set the total number of consecutive red tokens found so far to 0

Line 2: Get a token from the bag

Line 3: If the token is white, then go back to Line 1

Line 4: Add 1 to the number of consecutive red tokens found so far

Line 5: If the number of consecutive red tokens is less than 3, then go back to Line 2

Line 6: Success – 3 consecutive red tokens have been taken out of the bag

This algorithm is more versatile because it can easily be modified to detect any number of consecutive red tokens simply by changing the value of 3 in Line 5 of the algorithm.

Figure 1.8 presents this algorithm diagrammatically in the form of a flowchart that shows the sequence of operations that take place when executing an algorithm. Lines with arrowheads indicate the sequence in which operations are carried out. Boxes indicate the actions themselves, and diamonds represent conditional actions. The expression in the diamond is evaluated to yield either “yes” or “no,” and control flows in one direction or another. In general, flowcharts are well suited to depicting simple algorithms, but they are regarded as very unsuitable for complex algorithms. A flowchart for a complex algorithm looks like a bowl of spaghetti – but without the spaghetti’s inherent clarity and organization.

Figure 1.8 – An algorithm represented by a flowchart

Constructing an algorithm

The next step is to provide an algorithm that tells us how to solve this problem clearly and unambiguously. As we step through the sequence of digits, we will need to keep track of what’s happening, as Table 1.2 demonstrates:

Table 1.2 – A sequence of tokens selected at random

Pseudocode is a term that’s applied to a method of expressing an algorithm in something that falls between plain English and a formal programming language. The following pseudocode expresses the actions we need to perform. The initialization operations that we perform once at the beginning are in normal typeface, while the repetitive actions defined by REPEAT...UNTIL are in bold. We will look at these operations in detail when we introduce Python:

1.    Set numRed to 0
2.    Set maxRed to 3
3.    REPEAT
4.        Get a token
5.        IF its color is red
6.        THEN numRed = numRed + 1
7.        ELSE numRed = 0
8.    UNTIL numRed = maxRed

This pseudocode employs two constructs found in many high-level computer languages: the REPEAT...UNTIL construct in lines 3 to 8, and the IF...THEN...ELSE construct on lines 5 to 7. REPEAT...UNTIL lets you carry out an action one or more times, while IF...THEN...ELSE lets you choose between one of two possible courses of action.

The IF...THEN...ELSE construct is central to the operation of digital computers and you will encounter it many times in this book.

The next step is to introduce Python so that we can write a program to implement this algorithm. Then, we can start to look at the computer. The following code shows a Python program and its output when executed. We haven’t introduced Python yet. The purpose of this program is to demonstrate how close it is to the preceding algorithm and the simplicity of Python:

Sequence =['W','R','R','W','R','W','W','W','W','R','W','W','R','R','R']
numRed = 0
maxRed = 3
count  = 0
while numRed != maxRed:
    token = sequence[count]
    if token == 'R':
        numRed = numRed + 1
    else: numRed = 0
    print('count', count,'token',token,'numRed',numRed)
    count = count + 1
print('Three reds found starting at location', count - 3)

The while numRed != maxRed: line means carry out the block of indented operations, so long as (while) the value of numRed is not equal to maxRed. The != Python operator means not equal.

This is the output when the program is executed. It correctly identifies three consecutive reds and indicates the location of the first run in the run of three:

count  0 token  W numRed 0
count  1 token  R numRed 1
count  2 token  R numRed 2
count  3 token  W numRed 0
count  4 token  R numRed 1
count  5 token  W numRed 0
count  6 token  W numRed 0
count  7 token  W numRed 0
count  8 token  W numRed 0
count  9 token  R numRed 1
count 10 token  W numRed 0
count 11 token  W numRed 0
count 12 token  R numRed 1
count 13 token  R numRed 2
count 14 token  R numRed 3
Three reds found starting at location 12

In this first chapter, we introduced the concept of a computer via an FSM. A state machine is an abstraction of any system that can exist in one of several states at any instant. State machines are defined in terms of the states and the transitions between states. We introduced state machines as a precursor to digital systems. State machines introduce the notion of discrete states and discrete times. A state machine moves from one state to another at discrete instants in time. This mirrors the action of a program where actions (change of state) take place only when an instruction is executed.

State machines can model systems as simple as traffic lights to a game of chess or a computer program. We also introduced the idea of algorithms – that is, a set of rules used to solve a problem. Later in this book, we’ll explain how computers can implement algorithms.

In Chapter 2, we’ll provide a brief overview of n. We’ve chosen this language because it has a remarkably shallow learning curve, is very powerful (it does a lot with a few lines of code), is taught in many universities, and is freely available to run on PCs, Macs, and Raspberry Pi systems.