1

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 V2, 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:

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

Technical requirements

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

The finite state machine

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...