Theory of computation

Introduction

We begin our exciting journey through computer science by looking at just what it is computers actually do: computation. The branch of computer science that explores the capabilities and limitations of computation is known as theory of computation or computational theory. It builds and analyses mathematical models to probe computation in the abstract.

I promised lots of practical computer science information in this book. So why are we starting off with all this abstraction? A good craftsman should have a deep understanding of how their tools work. As programmers, we structure computation in order to achieve results. The better we understand what our computers can and can’t do, the better programmers we will be. You don’t want to waste a week trying to solve a problem that’s been proven to be unsolvable! Secondly, the terms and concepts from theory of computation pop up surprisingly often in day-to-day programming and it’s useful to have at least an acquaintance with them.

Finally, theory of computation is where computer science anchors itself to mathematics, logic and philosophy. It provides the foundations for everything else and will help you to develop a much more sophisticated understanding of what computing is and why computers work. It’s super interesting!

Because of the mathematics, theory of computation has a reputation for being very abstract and dense. Certainly it’s very maths heavy and the textbooks contain plenty of proofs. If you’re not mathematically confident, don’t let that hold you back! Lots of important results are straightforward to grasp without any mathematical background.

Theory of computation is made up of three main areas: automata theory, computability theory and complexity theory.

Automata theory is all about using mathematics to create computational models and explore what they can do. The reason for doing this is that physical computers are hugely complex devices that vary wildly in their design and performance. By using mathematical models, we can strip away all of these superfluous details and better understand the capabilities of the underlying model. We’ll see that an surprisingly simple model of computation is capable of representing any computation.

Once we have the necessary mathematical models we can use them to explore the capabilities and limitations of computation itself. This is computability theory. As we’ll see, there are some surprising limits to what can be computed. Besides being a fascinating intersection of computing and philosophy, you’ll regularly hit against these limitations in everyday programming so it’s vital that you’re aware of them.

After those two sections, we’ll be close to having a solid theoretical base. We’ll still need to sort out a few simple concepts: time and space. Complexity theory is the branch of computational theory that investigates the complexity of algorithms by analysing the resources, primarily time and space, that they require. It gives us ways to understand and measure algorithmic performance and how to classify algorithms according to their complexity.

Automata theory

Let’s begin by asking ourselves: what do we actually mean by the words “computation” and “computer”?

In mathematics we don’t really care how results are worked out. I can assign the square root of a number to a variable and blithely use that variable in equations without worrying about how to actually calculate the square root. My calculator doesn’t have it so easy. It has to know some sequence of steps that will calculate the square root so that it can show me the result. My calculator is performing computation.

A computer, then, is any machine that performs a computation by executing a defined sequence of operations, known as an algorithm. It may optionally generate some kind of result at the end. The particular state of the machine at any given moment indicates the state of the computation. This is a really important concept. A computer is something that takes a list of operations and converts them into some kind of observable form. In my trippier moments I like to imagine that a computer takes a verb (the instruction) and converts it into an object (the state) that represents the outcome of that instruction. The next instruction is then executed against the object, generating a new object that forms the input for the next instruction and so on. Far out!

Note that nothing in this definition requires the computer to be an actual, physical device. We could represent a computer by drawing on paper some states and arrows specifying rules for moving between them. We’ll see diagrams like this below. When defined with a more robust mathematical notation these models are known as automata, from the Greek automatos meaning “self-acting”.

Automata theory determines the capabilities and limitations of various automata designs. In our exploration of the subject we’ll start with the most basic model: the finite automaton. We’ll see that it can do a surprising amount but is ultimately limited by its simple design. We’ll then see how to amend its design to create the more powerful push-down automaton. Finally, we’ll look at the most powerful automaton of all: the Turing machine.

The point of all this is not to come up with a blueprint for a real computer. The point is to find a mathematical model that is both simple to understand yet powerful enough to model any arbitrary computation. Spoiler: such a thing exists and is the Turing machine. Once we have a model for performing arbitrary computation, we can analyse that model to better understand computation itself. Our aim here is to put together the necessary tools so that we can study computation in the abstract.

Finite automata

We have already defined a computer as a machine that can transition through a series of states, each reflecting a step in some algorithm. If there is only a finite number of states and a finite number of transitions, then such a machine is known as a finite automaton or finite state machine (FSM). The finite automaton is the simplest kind of computational model. It’s very useful for modelling primitive devices.

For example, this state diagram represents a turnstile. You may not have thought of a turnstile as a computer but look carefully and you’ll see that it meets our definition above:

We designate one state to be the start state. This is marked on the diagram by a circle with an arrow pointing to locked. This is the state our turnstile sits in, waiting for something to happen. At each state there are two possible inputs: push and coin. Pushing a locked turnstile doesn’t do anything – it remains locked. We represent this with an arrow looping back to the same state. Inserting a coin causes the turnstile to transition to the unlocked state. Inserting more coins has no effect. As the turnstile is now unlocked, a person can push through, thus resetting the turnstile back to its original locked state.

The possible ways of moving between states are defined by the transition function:

1 transition :: (oldState, input) -> (newState, output?)

I’m using Haskell-like type signature syntax here. The double colons mean “is of type”, so transition is a function that takes a state and an input and outputs a new state and an output. The question mark on output is my way of indicating that it’s optional.

Laying out all of the valid transitions creates a representation of the FSM known as a state transition table:

Even this very simple automaton has a limited form of memory. If the automaton is in the unlocked state we know that the previous input was a coin. But once we transition back to locked we lose this information. We have no way of telling whether a locked turnstile has never been unlocked or whether it’s been unlocked thousands of times.

A machine is deterministic if it consistently gives the same output for a given input. This is generally a desirable quality. An automaton is a deterministic finite automaton (DFA) if there is only ever a single possible transition from each state for a given input. You can see from the state diagram above that the turnstile is deterministic because each input only appears on a single transition at each state.

We can define a non-deterministic finite automaton (NFA) simply by allowing multiple transitions from a state for a given input. This requires a minor change to the transition function:

1 outcome :: (newState, output?)
2 transition :: (oldState, input) -> [outcome1, outcome2...]

For each pair of state and input there may be zero or more transitions. Each transition outputs a new state and optional output. On a state machine diagram this is represented simply by having multiple labels on transition arrows. This raises an obvious question: if a NFA has two available transitions for a given input, how does it choose which transition to take?

The surprising answer is that the NFA follows every possible transition. Remember that we’re talking about mathematical models here. Each time it is faced with multiple transitions, the NFA duplicates itself and each duplicate follows a different transition. Duplicates can in turn duplicate themselves whenever they encounter more transitions. The NFA works a bit like the broomstick from the Sorcerer’s Apprentice, duplicating and reduplicating itself as necessary to cover every possible path.

The duplicates all run in parallel, each one following a different computational path. If one of the duplicates reaches a state where it has no more open transitions, then it’s stuck in a dead end and can be removed. We’ll end up with a whole herd of automata, representing the complete set of possible paths through the transitions. If one of them reaches an accept state, the path it represents is a valid path. We say that the automaton has accepted the input if there is at least one valid path.

This definition applies to deterministic automata too. A DFA is a NFA that just happens to only ever have one possible transition for a given input. This means that a DFA is also a valid NFA. What’s more, any NFA can be represented as a valid DFA. In fact, deterministic and non-deterministic automata are equivalent. Anything that can be computed with a DFA can be computed with an NFA and vice versa. Given this, it seems that NFAs add quite a lot of complexity for a questionable advantage. Why bother? The benefit is that some computations can be more concisely expressed (using fewer states) as a non-deterministic automaton than as a deterministic automaton.

Finite automata, whether deterministic or non-deterministic, are very simple beasts. In fact, they’re so basic that you might at first not even recognise what they’re doing as computation. It appears that finite automata are nothing more than a starting point on our journey. Yet they have another trick up their sleeve. Finite automata pop up surprisingly often embedded in other programs. I’ll refer to code versions of finite automata as state machines. They will appear in codebases you work on, either explicitly or implicitly defined. They’re super useful for modelling processes that flow through a series of states. When you recognise that you’ve got an implicit state machine lurking in your code, pulling it out into an explicit structure can be a great way to manage complexity. This is called the state machine pattern.

Take a complex, multiple step user flow. A good example would be Airbnb’s identify verification flow. Each step in the flow can be represented by a state in a state machine. The actions in the flow are the transitions between states. You might have a state in which you ask the user for basic contact information. When they input their details, the state machine transitions to another state in which the user is asked to upload a photo of their identity card. The upload triggers another transition to a state in which the photo is sent to an analysis service that compares the identity card’s details to the information provided by the user in the first state. If everything matches, the state machine transitions to a success state. If there’s a problem, the state machine transitions to an error-handling state. The user is informed and given the option to repeat the upload process.

It’s possible to do all of the state management and validation manually but it’s brittle and error-prone. Let’s see how the above flow might be implemented without a state machine and then see whether a state machine improves things:

 1 class User
 2   enum status: [:new, :info_provided, :pending, :verified, :rejected]
 3 end
 4 
 5 class UserSignupFlow
 6   def new(user)
 7     @user = user
 8   end
 9 
10   def perform
11     if !@user.status == :info_provided
12       @user.contact_info = get_contact_info
13       @user.status = :info_provided
14     end
15 
16     if !(@user.status == :pending || @user.status == :verified)
17       @user.photo = get_id_photo
18       @user.status = :pending
19     end
20 
21     if IDValidator.valid?(photo, contact_info)
22       @user.status = :verified
23     else
24       @user.status = :rejected
25     end
26   end
27 end

That looks like a mess and I haven’t even handled retrying the photo upload. Admittedly, the code could be tidied up a little by extracting things out into methods and so on. Either way, you can’t get around the fact that perform has to check the status attribute of the user to determine if an action is permitted. In a small flow this is probably manageable, especially with good unit testing. However, it will be very easy to cause subtle errors by performing an incorrect check. This will lead to the user incorrectly transitioning to an invalid state that might not manifest itself until much later in the program. The transitions are not explicitly defined and instead have to be inferred from the conditional clauses, which can easily be incorrectly modified. This is a design that will not scale well at all.