UTM · Master of Computer Science · bridging subject

Theory of Computer Science

What can be computed, by what kind of machine, and at what cost. Three questions, each answered here by something you can run and watch rather than only read.

What the field is

Most of computing is about building things that work. Theory of computer science asks a different question: what is possible at all, and what does it cost?

It turns out you can answer that precisely. Give a machine a fixed set of states and no memory, and there are patterns it provably cannot recognise — no matter how clever the programmer. Add a stack and it can match brackets. Add a read-write tape and it can compute anything computable at all. And some problems are solvable in principle but so expensive that solving them exactly is out of reach for any computer we will ever build.

The three areas below walk that ladder: the machines, the translation from notation into a machine, and the cost of running one.

Four milestones

  1. 1936Alan Turing

    Defines a machine with a read-write tape and shows some questions no machine can answer. Computation gets a definition before computers exist. — Automaton

  2. 1951Stephen Kleene

    Introduces regular expressions and proves they describe exactly what a finite-state machine can recognise. Notation and machine turn out to be the same thing. — Regex

  3. 1956Noam Chomsky

    Ranks grammars by power — regular, context-free, and beyond — matching each to the machine that can parse it. — Automaton

  4. 1971Stephen Cook & Leonid Levin

    Show that a whole class of hard problems are equivalent: crack one efficiently and you crack them all. P vs NP is still open. — Complexity

The three areas

Automaton

What is the simplest machine that can recognise this kind of pattern?

Five machines — NFA, DFA, DFA minimisation, pushdown automaton and Turing machine — each running your input one step at a time, with the active state lit up.

C++ compiled to WebAssembly, running in your browser

Regex

How does a regular expression actually become a machine?

Type an expression, watch Thompson's construction assemble an NFA piece by piece, then watch subset construction collapse it into a deterministic machine.

Go, running as its own service on the server

Complexity

Why are some problems easy and others effectively impossible?

Shortest paths solved instantly, next to the travelling salesman problem solved two ways — exactly, and by a fast approximation that stops being optimal as it grows.

Python with NetworkX, on the server