Why study computation in the abstract?
You already know how to write programs that run on a real computer. The theory of computation steps back from any particular language or chip and asks blunter, more permanent questions: What can be computed at all? What can be computed quickly? Are there problems that no program, on any machine, now or ever, can solve? These answers do not depend on whether you write Python or C, or on how fast next year's processor is — and that durability is exactly the point.
To ask such questions sharply, we need a model of computation that is simple enough to prove things about, yet honest about what real machines do. The strategy of the whole course is to start with a tiny, weak machine that we can fully understand, then add power one careful step at a time, watching exactly what each new ability buys us. Each model comes paired with a family of problems it can and cannot handle.
The atoms: alphabets, symbols, and strings
Everything we compute over is built from a fixed, finite alphabet, written Σ (the Greek capital sigma). An alphabet is just a set of allowed symbols — for example Σ = {0, 1} for bits, or Σ = {a, b}. A string is a finite sequence of symbols glued together in order, like 0110 or aabba. The number of symbols in a string is its length; the string 0110 has length 4.
There is one special string of length 0: the empty string, written epsilon (the Greek letter ε). It is the string with no symbols at all — not a blank space, not the symbol 0, but genuinely nothing. Epsilon plays the same role for strings that the number 0 plays for addition: gluing it onto either end of a string leaves the string unchanged. Watch out for the classic beginner trap — epsilon is a perfectly real string, just an empty one, and confusing 'no string' with 'the empty string' will bite you later.
Strings combine by concatenation: just stick one after another, so 01 concatenated with 10 gives 0110. Repeating a string n times is its power, written like a^n, so a^3 means aaa and a^0 means epsilon. Pushing this further, the Kleene star applied to the whole alphabet, Σ* (read 'sigma-star'), names the set of ALL strings you could ever form over Σ, of every finite length including epsilon. So Σ* is the universe inside which all of our action takes place.
From strings to languages
Now the central definition of the whole subject. A formal language (or just 'language') over Σ is simply a SET of strings — any subset of Σ* you care to pick. The language could be {a, ab, abb} (finite), or 'all bit strings with an even number of 1s' (infinite), or 'all syntactically valid Python programs'. There is no grammar or meaning attached yet; a language is purely a collection of strings, and that bareness is what makes it so flexible.
Two languages look almost identical but are crucially different, and telling them apart is a rite of passage. The empty language, written ∅ or {}, contains NO strings at all — it is the empty set. The language {epsilon} contains exactly ONE string, the empty string. So ∅ has size 0, while {epsilon} has size 1. By analogy: an empty box versus a box holding one empty bag. They are not the same box.
Because languages are sets, you can combine them with the usual operations and a couple of string-flavored ones: union L1 ∪ L2 and intersection L1 ∩ L2 behave just like for any sets, while concatenation L1·L2 forms every string made by gluing a string from L1 in front of a string from L2, and the Kleene star L* forms every string you get by concatenating zero or more strings drawn from L (note that L* always contains epsilon, from the 'zero strings' case). These operations are the verbs we will use to describe and build languages for the rest of the course.
The big idea: a problem IS a language
Here is the move that unifies everything. Take any yes/no problem — 'Is this number prime?', 'Does this graph have a path visiting every city?', 'Is this program syntactically valid?'. First encode each input as a string over some alphabet (numbers as digits, graphs as text, programs as their source). Then collect exactly the strings whose answer is YES into one set. That set is a language, and it captures the problem completely: solving the problem means deciding membership in that language. This is the idea of a problem encoded as a language.
Phrased this way, every yes/no problem becomes one task: the membership problem — given a string w, is w in the language L? This is also called the decision problem for L. It sounds almost too simple, but reframing wildly different problems as 'is this string in this set?' is precisely what lets us measure them all on one ruler. A machine 'solves' the problem when, fed any string, it correctly answers in/out.
The map: machines, languages, and the Chomsky hierarchy
As we add power to our machines, the families of languages they can decide form a neat ladder of nested rings called the Chomsky hierarchy. At the bottom sit the simplest patterns; at the top sits everything a real computer could ever recognize. Each rung is strictly bigger than the one below it: there are honest languages living in the outer ring that no weaker machine can touch. The table below sketches the climb.
LANGUAGE FAMILY MACHINE EXAMPLE IT CAPTURES ----------------------- ---------------------------- ------------------------- regular finite automaton (DFA/NFA) even number of a's context-free pushdown automaton (PDA) matched brackets, a^n b^n recursively enumerable Turing machine any program's behavior nesting: regular ( context-free ( recursively enumerable ( all languages
The first rung is the regular languages, recognized by a finite automaton — picture a turnstile or a vending machine that only ever remembers its current state, with no extra scratch paper. We will meet the deterministic finite automaton (DFA), design one for 'an even number of a-s', and prove its hard limit using the pumping lemma. A vital honesty check up front: 'regular' does NOT mean 'finite' — the language a* (all strings of a's, including epsilon) is infinite yet perfectly regular. Regular is about the kind of pattern, not the number of strings.
Climb one rung and you reach the context-free languages, recognized by a pushdown automaton — a finite machine handed a stack of plates where you may only touch the top plate. That single stack lets it count and match nesting, so it can recognize matched brackets or the context-free language a^n b^n (n a's followed by n b's), which no finite automaton can do. At the very top live the recursively enumerable languages, recognized by a Turing machine — think of an endless notebook you can read, erase, and rewrite freely. The Turing machine is our stand-in for 'any algorithm whatsoever', and it is precisely here that we will find problems like the halting problem that no machine can decide.
Beyond what, toward how fast
Once we have mapped what can be computed at all, the ladder turns to a second question: among the problems we CAN solve, which are solvable quickly? That is the subject of complexity, and it splits the decidable world by how the running time grows with input size. The class P is the home of problems solvable in polynomial time — the rough stand-in for 'efficiently solvable'.
Sitting around P is the famous class NP, best pictured as a jigsaw puzzle that may be brutal to finish from scratch yet trivial to check once someone hands you a finished solution. Three honest warnings to carry from day one: NP does NOT stand for 'not polynomial' (it means 'nondeterministic polynomial time', and in fact every problem in P is also in NP, so P is a subset of NP); whether P equals NP is a famous OPEN problem, not a settled fact; and even a polynomial-time algorithm can be useless in practice if the exponent is huge, since big-O bounds describe worst-case growth, not exact running time.
The tool that ties the hard problems together is the reduction — a translator that turns one problem into another so that solving the second would solve the first. Reductions let us say 'this problem is at least as hard as that one' without ever finding the actual algorithm. Used carefully (and only in the correct direction — a reduction proves hardness one way, not the other), they organize thousands of stubborn problems into tidy equivalence layers. That is the destination of this ladder; for now, you have the vocabulary and the map. The next guide zooms back in on alphabets, symbols, and strings to make these atoms precise.