What Is a Computation?

Every computing course you have taken so far was about making a computer do something. This one asks a stranger question: what can a computer never do — no matter how fast it is, no matter how good the programmer, no matter how long you let it run?

That sounds gloomy. It isn't. It turns out there is a real line between "a computer can do this" and "no computer can ever do this," and you can learn to see where the line is. Some perfectly ordinary-sounding requests — things a client might actually ask you to build — sit on the impossible side. Knowing that saves you from wasting months trying.

There is a second payoff, and you will use it more often. Between "easy" and "impossible" there is a big middle zone: things a computer can do, but only with certain kinds of memory, or only at a certain cost. Search patterns, spell checkers, compilers, and the reason some programs are fast and others crawl — they all live in that middle zone. This course hands you the map.

The real skill isn't proving things impossible. It's recognizing which kind of problem you're holding, before you build.

Here is the plan. We study a series of imaginary machines, starting with the simplest one anyone has ever invented and working up. Each new machine gets a little more memory and can do a little more. At every step we ask the same two questions: what can this machine handle, and what stumps it? By November we reach the top of the ladder, and something genuinely strange happens there. But that is later. Next week, we start with a machine so simple you can be one yourself.

We meet twice a week, Tuesday and Thursday, 6:00 to 7:50 PM, live on Google Meet. It is a small section, so class is a working session, not a lecture at you. Expect to show something most weeks — a bit of code, a diagram, a question you are stuck on — and to comment on other people's work. Come with your screen ready to share.

Your whole grade is four projects, 25% each. No midterm, no final. Each project is a working program plus a short written explanation, and the writing counts — a program that happens to pass tests is not the same as a program you can explain.

The four projects

1. Automata Simulator — build the simple machines from the first month of the course, in Python. Due end of Week 5.
2. Grammars and Parsing — design a tiny language of your own and build the tools that read it. Due end of Week 8.
3. Turing Machine Workbench — build the most powerful machine of all, and see where even it fails. Due Week 12.
4. Capstone — a project on hard problems, presented live in the final week.

You need Python 3.11 or later, Git, and a GitHub account. Everything is submitted as a repository link plus a short report on Brightspace. These notes are posted before each session and stay up all term. There is no textbook to buy.

To say anything solid about "all computers" and "all problems," we first need to agree on what a problem even looks like. The field settled on one simplifying move a long time ago, and it is the one idea to take home tonight.

The move: every input is a row of symbols, and every problem is a yes-or-no question about that row.

Sounds like it throws away too much, right? Computers show pictures, play songs, hold conversations. But look closer: a picture is just a long row of numbers. A song is a row of numbers. This very page is a row of characters. Deep down, everything a computer touches is a row of symbols — usually just 0s and 1s. Nothing got thrown away. It was already all strings.

The yes-or-no part is the bigger squeeze, so here is the honest defense. Suppose the real job is "sort this list." The yes-or-no version is "is this second list the sorted version of the first?" Not the same job — but if a computer can't even check an answer, it certainly can't produce one. So whenever we show a yes-or-no question is impossible, the full job is impossible too. We lose nothing that matters.

Every input in this course looks like this: a row of symbols, read left to right. The highlighted box is where some machine is currently looking. This picture is the whole subject.

The course runs on a tiny vocabulary — three words. Two of them mean something narrower here than in everyday English, so let's be careful once, now.

That last definition always feels too loose on first reading. It's loose on purpose: we didn't want to sneak an assumption in. Later in the course, that looseness pays off in a surprising way — it turns out most languages have no pattern at all, and no program can handle them. But that's a story for November.

One more thing to notice: even from a two-symbol alphabet like {a, b}, the collection of all possible strings never runs out — a, aa, aaa, and on forever. Play with it below and watch how fast the pile grows.

Now the two halves click together, and this is the sentence to leave class with. A yes-or-no question splits all possible strings into two piles: the ones where the answer is yes, and the rest. The yes pile is a collection of strings. A collection of strings is a language. So:

Every problem is a language — its own pile of yes-strings. Solving the problem means sorting strings into the right pile.

"Is this a valid email address?" is really the language of all valid email addresses. "Is this file a real photo?" is the language of all strings of bytes that are real photos. Three questions from three different worlds, all now the same shape — which means we can compare them and ask which needs the bigger machine.

This is why we spend the first month on tiny toy languages over {a, b}. They aren't toys — each one isolates exactly one kind of difficulty. "Even number of a's" isolates remembering one small fact. "Some a's followed by the same number of b's" isolates counting with no limit. Once you can spot which difficulty a real problem hides, you know which machine it needs.

Two more tools and tonight's kit is complete. Neither needs any math background — I promise. Skim this now, and come back to it the first time a project report asks you to explain your reasoning.

A set is a club

A set is just a collection where the only thing that matters is membership: you're in, or you're out. Think of a club roster, or a playlist. The order doesn't matter — a playlist and the same playlist shuffled contain the same songs. Repeats don't matter either — adding a song twice doesn't make it more of a member. That's the entire concept.

You've already met three sets tonight without noticing: an alphabet is a set of symbols, a language is a set of strings, and the yes pile from §05 is a set. When I write {a, b}, the curly braces just mean "the club containing a and b, and nothing else."

One tiny distinction earns its keep later, so take it now. An empty club — a language containing no strings at all — is not the same thing as a club whose only member is the empty string. The first club has zero members. The second has one member, which happens to be a string with nothing in it. An empty box versus a box containing an empty bag. Your Project 1 test suite will check that your code knows the difference.

A proof is an airtight argument

A proof is nothing fancier than an argument with no wiggle room — an explanation so tight that a stubborn skeptic has nowhere left to push back. You will write a short one with every project. In this course, almost every argument you'll ever need comes in one of three flavors. Here's each one, in one bite.

Flavor 1 — show it by building it. To convince someone something is possible, build an example and hold it up. Want to show strings can be as long as you like? Easy: a, aa, aaa, aaaa… keep going, and nothing ever stops you. Done. Most of your semester is this flavor: to show a machine for some job exists, you'll build the machine and show it working.

Flavor 2 — show it's impossible by hitting a wall. To convince someone something can't be done, pretend for a moment that it can — then follow that pretend world until it crashes into itself. Try it: could one finite sheet of paper list every possible string? Pretend it could. Find the longest string on the sheet and stick one more letter on it. That new string should be on the sheet — the sheet supposedly has everything — but it can't be, because it's longer than the longest thing there. The pretend world just contradicted itself, so it was never possible. That's the whole technique.

Flavor 3 — dominoes. To convince someone something is true for every string, no matter how long: check it for the shortest string, then show that whenever it's true for one string, adding one more symbol keeps it true. Tip the first domino, make sure each domino knocks over the next, and the whole endless line falls. Strings are built one symbol at a time, so this flavor fits them perfectly — it quietly powers next week's machine.

That's the entire toolkit. When you write an argument for me, just say which flavor you're using in your first sentence — "here's a working example," or "pretend it's possible; here's the wall" — and the rest almost writes itself.

Six questions. Decide on your answer before you click — being wrong here is free, and useful.

Nothing to read. There is setup to finish before Session 2, because next week we start building machines in class.

Coming up

Sessions 2 and 3 (Sept 8, 10) — Notes 02. The simplest machine there is: how it works, how to run it by hand and in Python, and how to design your own. The Project 1 handout comes out that week.

If anything tonight didn't land, email me — yair.chaya@liu.edu — or grab an office-hours slot. I reply within 24 hours.