Notes 01 · Session 1 · Thursday, September 3, 2026
What Is a Computation?
Course overview, and the single idea the rest of the semester is built on: every question a computer can be asked is a question about strings.
The question this course is about
Every course you have taken about computers so far has been about getting a machine to do something. This one is about the opposite. It asks what a machine cannot be made to do, no matter how clever the programmer, how fast the hardware, or how many years you let it run.
That sounds like a pessimistic subject, and students often expect it to be a dry one. It is neither. The reason it matters is that the boundary between possible and impossible turns out to be sharp, it is knowable, and it is closer than your intuition suggests. There are perfectly reasonable-sounding questions — questions a client might ask you for in a sprint planning meeting — that no program can answer. Not "no program yet." No program, ever. Once you can recognize the shape of such a question, you stop burning weeks trying to build the thing, and you start building the approximation that actually ships.
There is a second payoff, and in practice it is the one you will use more often. Between "easy" and "impossible" there is a large middle territory: problems that can be solved, but only by machines with particular kinds of memory, and only at particular costs. Regular expressions, parsers, compilers, database query planners, protocol validators, type checkers, and the reason your build takes four minutes instead of four hours all live in that territory. This course gives you the map.
The practical skill is not proving things impossible. It is recognizing, early, which kind of problem you are holding.
We will build up through four models of computation, each strictly more powerful than the last: finite automata, pushdown automata, Turing machines, and then Turing machines with a stopwatch attached. It is a ladder, and each rung differs from the one below it in exactly one respect — how much memory the machine has, and how it may use it. At every rung the same three questions recur: what can this model do, what can it provably not do, and how do we know? And at the top of the ladder, in November, the climb ends somewhere genuinely strange — precisely stated questions that no machine on any rung can answer, ever. We will get there honestly, one machine at a time, starting Tuesday with the smallest one.
This is a theory course taught constructively. You will not be asked to memorize a definition and reproduce it on an exam — there are no exams. You will be asked to implement the machine, run it on real inputs, and then explain in writing why your implementation is correct. A model you have coded is a model you understand. That is the whole pedagogical bet of this course.
How the course runs
We meet twice a week, Tuesday and Thursday, 6:00 to 7:50 PM, live on Google Meet. This is a small tutorial section, so sessions are working sessions rather than lectures delivered at you. Every meeting, you should expect to show something — a function, a failing test, a diagram you are stuck on — and to comment on someone else's work. Come with your environment running and your screen ready to share.
The entire grade is four projects, 25% each. There is no midterm, no final, and no participation grade. Each project is a working artifact plus a written argument, and the written half is worth real points, because a program that happens to pass tests is not the same as a program you can justify.
The four projects
- Automata Simulator — a simulator that accepts DFA and NFA definitions, decides membership, converts NFA to DFA by the subset construction, and compiles regular expressions into automata. Due end of Week 5.
- Grammars and Parsing — a context-free grammar for a small language of your own design, plus a parser and a pushdown-automaton simulator, plus an argument for something the grammar provably cannot capture. Due end of Week 8.
- Turing Machine Workbench — a Turing machine simulator with several tape variants, some encoded languages to run on it, and a written demonstration of why the halting problem cannot be solved by any of them. Due Week 12.
- Capstone: Reductions and Complexity — a toolkit that transforms instances of one NP-complete problem into another, verified empirically, presented live in the final week.
Python 3.11 or later, Git, and a GitHub account. Everything is submitted as a repository link plus a report through Brightspace, and your commit history is part of the evidence that the work is yours. Notes — this document is Notes 01 — are posted to the course repository before each session and stay up all term. There is no textbook to buy.
You may use AI tools the way you would use any other reference, with two conditions: disclose which parts of a submission were AI-assisted in your report, and be able to explain and defend every line you hand in. The defense is 20% of each project rubric, and it is where undisclosed use falls apart. Ask me before the deadline if you are unsure where a line is.
The move: turning questions into strings
Here is the difficulty that the entire field had to solve before any of this could be studied. We want to make claims about all possible programs and all possible problems. But "problem" is a vague word, and "program" depends on which language you happen to like this year. You cannot prove a theorem about a vague word.
So the field made one simplifying move, and it is the move you need to absorb tonight, because everything else is a consequence of it. The move is this: every input is written down as a finite sequence of symbols, and every problem is reduced to a yes-or-no question about such a sequence.
Consider what that costs us, honestly. It looks like it throws away most of what computers do. Computers return images, sort lists, train models, hold conversations. Where did all that go? The answer is that it did not go anywhere — it was already a sequence of symbols. An image is bytes. A model is bytes. This very document is bytes. A computer's memory, at the bottom, is a long finite string over the alphabet {0, 1}, and every operation it performs is a rewriting of that string.
The yes-or-no restriction seems more damaging, and it deserves a straight answer. Suppose the real task is "sort this list." The corresponding yes-or-no question is "is list B the sorted version of list A?" These are not the same task, but they are close enough for the purpose at hand: if you cannot even check an answer, you certainly cannot produce one. Throughout the semester, when we prove something is impossible, we prove the yes-or-no version is impossible — which makes the full version impossible too, and makes the result stronger, not weaker.
Every input we study looks like this: finite, written left to right, over a fixed set of symbols. The highlighted cell is where some machine currently is. That picture is the whole subject.
Think first: what is the yes-or-no version of "compile this source file"?
One good version: "is this pair — source file S, machine code M — such that M is a correct compilation of S?" Another, weaker but very useful one: "is S a syntactically valid program in this language?" We will spend Weeks 6 through 8 on exactly that second question, and you will build a parser that answers it.
Three words: alphabet, string, language
The vocabulary is small. Three terms carry the whole course, and two of them mean something narrower than they do in English, which is exactly why they are worth stating carefully.
An alphabet is any finite, non-empty set of symbols. We write it Σ (sigma). It might be {0, 1}, or {a, b}, or the 128 ASCII characters, or the set of tokens your parser emits. Which symbols they are does not matter; that there are finitely many of them matters enormously.
A string over Σ is a finite sequence of symbols drawn from Σ. Finite is not a technicality — it is the definition. Every string ends. The string of length zero is called the empty string, written ε (epsilon). It is a legitimate string, it is not the same thing as the empty set, and forgetting it is the single most common source of bugs in Project 1.
A language over Σ is any set of strings over Σ. That is the entire definition. It does not need a grammar, a pattern, or a description. It does not need to be finite. It does not need to be interesting. Any collection of strings you can point to is a language.
That last one always feels too permissive on first reading, and the permissiveness is deliberate. If we had defined "language" as "the set of strings matching some pattern," we would have quietly assumed the answer to the question we are trying to ask. By letting a language be any set of strings, we leave room for a punchline we will earn properly in Week 11: almost every language has no pattern, no grammar, and no program at all.
One more piece of notation, and it earns its place. Σ* means the set of all strings over Σ, of every finite length, including ε. So if Σ = {a, b}, then Σ* = { ε, a, b, aa, ab, ba, bb, aaa, … } going on forever. Σ* is always infinite, and a language over Σ is always a subset of Σ*. Play with it below.
Playground · build Σ*
click any string to test it in §5Think first: why does the count of strings of length n grow the way it does?
Each of the n positions is filled independently from |Σ| choices, so there are |Σ|n strings of that length. With Σ = {a, b}, that is 1, 2, 4, 8, 16 — doubling every step. This is the first hint of why brute-force enumeration is not a strategy, and it is the seed of the complexity material in Weeks 13 through 15.
Every problem is a language
Now the two halves join, and this is the sentence to leave class with. A yes-or-no problem is nothing more than a rule that splits Σ* into two piles: the strings for which the answer is yes, and the rest. The pile of yes-strings is a set of strings. It is a language.
Solving a problem means deciding membership in its language. Nothing else.
So "is this a valid email address?" is the language of all strings that are valid email addresses. "Is this a well-formed JSON document?" is the language of well-formed JSON documents. "Does this program halt on this input?" is the language of all program-and-input pairs where the program halts. Three questions from three very different worlds, all now the same shape — and because they are the same shape, we can compare them, rank them, and prove things about them.
This is why the course spends its first month on what look like toy languages over the alphabet {a, b}. They are not toys; they are the smallest examples that isolate a specific difficulty. "Strings with an even number of a's" isolates the difficulty of remembering one bit. "anbn" isolates the difficulty of counting without a bound. Once you know which difficulty a real problem contains, you know which machine it needs.
Playground · decide membership
type a string, or click one aboveChange the language and leave the input alone. The same string flips from accepted to rejected without a single character changing. The string has no properties of its own — membership is a fact about a string and a language together. Students lose points on Project 1 for writing simulators that forget this and hard-code the language into the machine.
Think first: is ε in the language "strings with an even number of a's"?
Yes. ε has zero a's, and zero is even. This is the kind of edge case that is obvious once stated and invisible until your test suite catches it. Make ε the first test case in every automaton you build this semester.
The toolkit: sets, and three kinds of proof
We have been leaning on the word set all evening — an alphabet is a finite set of symbols, a language is a set of strings — so let us pin down exactly how much set machinery this course uses, which is not much, and the three proof moves it uses constantly, which you will write in every project report. This is a toolkit section, not a destination. Skim it tonight; come back to it the first time a report asks you to argue something.
Sets, at working speed
A set is an unordered collection of distinct things. Braces list members: {a, b}. Order and repetition mean nothing — {a, b}, {b, a}, and {a, a, b} are the same set. Set-builder notation describes members by a condition: { w ∈ Σ* | w has an even number of a's } reads "the set of all strings w in Σ* such that w has an even number of a's" — and that is how we will write languages from now on. Membership is w ∈ A. Containment is A ⊆ B: every member of A is also in B. Two sets are equal precisely when each contains the other, which is why a proof that two languages are equal always has two halves.
Because languages are sets, the set operations come free. For languages A and B over Σ: the union A ∪ B holds the strings in either; the intersection A ∩ B holds the strings in both; the complement of A, written Σ* ∖ A, holds every string over Σ that is not in A. |A| is the number of members when A is finite. Two more will earn their keep within a fortnight: the Cartesian product A × B is the set of ordered pairs (x, y) with x from A and y from B — pairs of states are how we will run two machines at once in Week 2 — and the power set P(A) is the set of all subsets of A, which has 2|A| members and is the star of Week 3.
One distinction does real work in this course, so make it tonight. ∅ is the empty set: a language with no strings in it. ε is the empty string: a string, of length zero. And {ε} is a language with exactly one string in it, which happens to be the empty one. So |∅| = 0 but |{ε}| = 1, and a machine that accepts nothing and a machine that accepts only ε are different machines. Project 1's test suite checks that your simulator knows the difference.
Think first: over Σ = {a, b}, describe the complement of "strings containing bb" in words. Is ε in it?
It is the set of strings in which no two b's are ever adjacent. And yes: ε contains no bb — it contains nothing at all — so it fails the "contains bb" test and lands in the complement. Complement always splits Σ* cleanly: every string is in exactly one of A and Σ* ∖ A.
Three proofs, worked once each
There are no exams in this course, but every project ships with a written argument, and three patterns cover nearly everything you will ever need to write for me. Here is each one, stated as a move and then worked honestly on tonight's material.
Half of a clear proof is telling the reader, in the first sentence, which kind of proof it is.
Construction. To show something is possible, or exists, build it — and then show it does the job. Most of your semester is this pattern: to show a language is regular, you will hand me an automaton and argue that it accepts exactly the right strings.
Claim. For every alphabet Σ, the set Σ* is infinite.
Proof. An alphabet is non-empty by definition, so pick any symbol in Σ and call it a. Now construct the strings ε, a, aa, aaa, … — for each n ≥ 0, the string an made of n copies of a. Each is a finite sequence of symbols from Σ, hence a member of Σ*. Any two of them have different lengths, so they are pairwise distinct. That is infinitely many distinct members of Σ*. ∎
Notice where the construction leaned on the definition: non-emptiness. Drop that requirement and the claim dies — over an empty alphabet, the only string is ε.
Contradiction. To show something is impossible, assume it is possible and follow the consequences until two of them collide. You will use this in Week 5 to prove languages non-regular, and it powers the great impossibility results at the end of the term.
Claim. No finite language equals Σ*.
Proof. Suppose, for contradiction, that some finite language L equals Σ*. L is not empty, since ε ∈ Σ* = L, and a non-empty finite set of strings has a member of maximum length — call it w. Pick any symbol a ∈ Σ. Then wa is a string over Σ, so wa ∈ Σ* = L. But |wa| = |w| + 1 > |w|, contradicting the choice of w as a longest member of L. The assumption was the only step that could be at fault, so no finite language equals Σ*. ∎
Induction. To show something holds for every string, show it holds for ε, then show that if it holds for any string it still holds after you append one more symbol. Dominoes: knock over the first, guarantee each one topples the next, and the whole line falls. Because strings are built one symbol at a time, induction on length is the native proof form of this entire subject — next week's argument that a finite automaton's verdict is even well-defined is exactly this shape.
Claim. For every n ≥ 0, there are exactly |Σ|n strings of length n over Σ — the doubling you watched in the §04 playground.
Proof. By induction on n. Base: there is exactly one string of length 0, namely ε, and |Σ|0 = 1. Step: suppose there are exactly |Σ|n strings of length n. Every string of length n + 1 splits in exactly one way as w followed by a — its first n symbols, then its last symbol — and every such pair gives a distinct string of length n + 1. So the strings of length n + 1 correspond one-to-one with (length-n string, symbol) pairs, of which there are |Σ|n · |Σ| = |Σ|n+1. ∎
That is the entire toolkit. When a report asks you to argue, name your pattern in the opening line — "we argue by contradiction," "we prove this by induction on the length of w" — and the rest of the writing becomes mechanical in the best sense: you know what you owe the reader, and the reader knows what to check.
Think first: which pattern proves "some machine accepts exactly the strings with an even number of a's"?
Construction — you exhibit the machine and argue it is correct. And the correctness argument inside it will be an induction on the length of the input. The patterns nest, and that pairing — construct, then induct — is the skeleton of every correctness argument in Project 1.
Quick check
Six questions. Answer before you click — being wrong here is free and useful.
Before Tuesday
Nothing to read. There is setup to do, and it needs to be finished before Session 2, because Week 2 starts with finite automata and you will be writing code in class.
Coming up
Session 2 and 3 (Sept 8, 10) — Notes 02. Deterministic finite automata: the formal definition, how a computation actually runs step by step, and how to construct one for a language you are handed. The Project 1 specification is released that week.
If any part of tonight did not land, email me — yair.chaya@liu.edu — or ask for an office-hours slot. Replies within 24 hours.