Unit 1 · Lesson 1 of 3 11 min

Introduction to the Theory of Computation

Before you ask what a computer can do fast, ask what any machine can do at all.

Type your PIN into a POS terminal at a market stall in Onitsha. Four digits go in, and the little machine decides: approved or declined. It does not "think". It moves from one fixed situation to the next as each key arrives, and when the last key lands it is either in a happy situation or it is not. That tiny, mechanical decision-maker is an automaton, and this course is the study of such machines: what they can recognise, what they cannot, and how much memory each extra power costs.

Automata, Computability and Complexity

The theory of computation is the branch of computer science that studies which problems can be solved by an abstract machine, and how efficiently. It sets aside the brand of laptop and the programming language, and asks questions about computation itself. It has three classic branches, and this course visits all three.

The Three Branches of the Theory of Computation

Branch	Central question	Where it appears in this course
Automata theory	What can machines with limited memory recognise, and how do we describe the languages they recognise?	Finite automata, regular expressions, grammars, pushdown automata (Units 1–5)
Computability theory	Which problems can be solved by any algorithm at all?	Turing machines, decidability, the halting problem (Unit 6)
Complexity theory	Among solvable problems, which can be solved efficiently, using reasonable time and space?	P, NP and NP-completeness (Unit 6)

The word automaton (plural automata) comes from Greek for "self-acting". An automaton is an abstract self-operating machine that reads an input one symbol at a time and changes its internal state according to fixed rules. "Abstract" matters: it is a mathematical object, defined precisely enough that we can prove things about it, not a box of wires.

The General Model of an Automaton

The general model of a finite automaton. The input sits on a tape; a read head moves one cell to the right per step; the finite control is always in exactly one of finitely many states; after the last symbol the machine accepts or rejects.

Every machine in this course is a variation on the picture above. There is an input, written as a string of symbols on a tape. There is a read head that looks at one cell at a time. And there is a finite control, which is in one of a fixed, finite number of states. At each step the machine reads a symbol, consults its rules and moves to a new state.

The machines differ in what extra memory they have. A finite automaton has none beyond its current state. A pushdown automaton adds a stack. A Turing machine can write on its tape and move both ways, which turns out to be all the memory any computer could ever need. Each extra power lets the machine recognise more languages.

The hierarchy of machines studied in this course. Each machine adds memory to the one before it, recognises a strictly larger class of languages, and matches one type of grammar in the Chomsky hierarchy.

Historical Development of the Theory

A true story

From logic puzzles to every compiler on Earth

In 1936, before any electronic computer existed, the English mathematician Alan Turing asked what it means for a human clerk to "compute" by following rules with pencil and paper. His answer, the Turing machine, let him prove that some problems can never be solved by any procedure. In the same year Alonzo Church reached the same limit by a different route.

In 1943 Warren McCulloch and Walter Pitts modelled brain neurons as simple on/off units, an early ancestor of finite automata. In 1956 Stephen Kleene showed that the patterns these networks recognise are exactly the ones described by what we now call regular expressions, and Noam Chomsky, a linguist studying human sentences, classified grammars into the four-level hierarchy you see above. In 1959 Michael Rabin and Dana Scott introduced nondeterministic finite automata, work that later earned them the Turing Award.

None of this was built for practical use, yet today every compiler's lexical analyser is a finite automaton, every parser is a pushdown automaton in disguise, and every "find" box that accepts a pattern runs a regular-expression engine.

Applications of Automata Theory

You will meet these ideas in places that look nothing like theory:

Compilers. The lexical analyser that splits source code into tokens (keywords, identifiers, numbers) is a finite automaton generated from regular expressions. The parser that checks nesting of brackets and statements is built from a context-free grammar.
Text processing and search. Pattern search in editors, input validation (an 11-digit BVN, a phone number starting 080, 081, 070 or 090) and spam filters use regular expressions.
Digital hardware. Sequential circuits, traffic-light controllers and vending machines are finite-state machines, often with output (Moore and Mealy machines).
Communication protocols. A network connection moves through states such as "listening", "connected" and "closing"; protocol designers check these state machines for deadlock.
Software limits. Computability tells us why no tool can perfectly detect every infinite loop in every program, so engineers know when to stop looking for a perfect checker.

Pause & think

A lift (elevator) in a four-storey office block in Abuja waits on a floor, moves up, moves down, or opens its doors. Is it reasonable to model its controller as a finite automaton? What are the "symbols" it reads?

A machine's power is decided by its memory. Everything in this course is a careful answer to one question: with this much memory, which languages can a machine recognise, and which are forever out of reach?

📌 If you remember nothing else…

The theory of computation studies what abstract machines can compute and how efficiently.
Its three branches are automata theory, computability theory and complexity theory.
An automaton reads its input one symbol at a time and changes state by fixed rules; at the end it accepts or rejects.
Finite automaton → pushdown automaton → linear bounded automaton → Turing machine: each adds memory and recognises more languages.
Applications include lexical analysis and parsing in compilers, pattern search, digital circuits and protocol design.

Quick check

Did it land?

1. Which branch of the theory of computation asks whether a problem can be solved by any algorithm at all?

Spotted a mistake?