Pillar 4 · Theory of Computation

Theory of Computation

What can be computed, and how fast. Eight guides in the full TechForge style — diagrams, quizzes, interview questions — from finite automata to P vs NP.

Start here

Why does theory matter?

Theory of computation is the study of a single question with two halves: what can a computer solve at all, and which of those can it solve fast enough to matter. It draws the map of every problem you will ever face — and tells you which corner yours sits in.

The payoff is not abstract. It’s knowing when to stop: some problems are provably unsolvable (the halting problem), others provably slow (NP-complete). Recognizing which one you’ve hit saves you from hunting for an algorithm that cannot exist.

The thread runs from the simplest machine (finite automata, no memory) up the ladder of power to Turing machines (everything computable), then pivots to speed — Big-O, complexity classes, and the million-dollar P vs NP question.

Learning path

Eight guides, in order — diagrams, worked examples, interview questions and a quiz in each.

1
Finite Automata
The simplest computer — states, DFA vs NFA, and the limits of no memory.
→
2
Regular Languages & Regex
The regex you use daily is a state machine — its powers, its limits, and ReDoS.
→
3
Grammars & Parsing
Add a stack and you get nesting — context-free grammars, PDAs, and how compilers parse.
→
4
Turing Machines
Add an infinite tape and you get the definition of computable itself.
→
5
Decidability & Halting
Some problems no computer can ever solve — the halting problem, proven.
→
6
Time Complexity
Solvable isn’t enough — Big-O, the growth hierarchy, and complexity classes.
→
7
P vs NP
The million-dollar question, NP-completeness, and reductions — explained plainly.
→
8
Hardness in the Wild
Spotting hard problems in real work, and what the theory tells you to do next.
→