The Simplest Machine

Last week we agreed that every problem is a sorting job: given a string, put it in the yes pile or the no pile. This week we build the simplest gadget that can do any sorting at all. It's so simple you can be one yourself — so let's start there.

Think of a subway turnstile. It can be in exactly two situations: locked and unlocked. Tap your card — it switches to unlocked. Push through — it switches back. That's the whole device. It doesn't remember who you are or how many people came through today. All it knows is which situation it's in right now. We'll call each situation a state.

Now put that idea to work on a sorting job. You stand at a conveyor belt. Letters stream past, one at a time, left to right. You see each letter once — no going back, no peeking ahead, no notepad. When the belt stops, you answer yes or no on the spot. The only thing you carry from letter to letter is which state you're in, and you must pick your full set of states before the belt starts.

Could you sort strings by "even number of a's" under these rules? You could — with just two states. Call them E ("even so far") and O ("odd so far"). Start in E, because zero a's is even. Every a that passes, switch states. Every b, stay put. When the belt stops, say yes if you're in E. Notice what you never did: count. You have no idea if you saw four a's or four thousand. You tracked one small fact, and it was enough.

This machine can't do much. That's exactly why we start with it — everything it can do teaches us something sharp.

Plan for the week: Tuesday we pin the machine down and run it, by hand and in the simulator. Thursday we practice designing our own, find the machine's limit, and write it in Python.

Time to write the conveyor-belt game down precisely — because in Project 1 you'll feed machines to a program, and a program needs an exact format. Here's the good news: a machine is completely described by five plain things.

Look hard at rule number 3, because one word carries all the weight: exactly one instruction per state-and-letter pair. Never zero — the machine can't get stuck. Never two — it never has a choice. Hand it a string and its whole path is settled before the first letter arrives. Machines like that are called deterministic — from "determined": the outcome is decided in advance. Next week we break this rule on purpose.

Here's the even-a's machine as its five things. States: E and O. Alphabet: {a, b}. Rules: in E, an a sends you to O and a b keeps you in E; in O, an a sends you back to E and a b keeps you there. Start state: E. Yes-states: just E. Two states, four rules, done.

Whatever this machine knows about everything it has read, it knows as one thing: which state it's standing in.

Sit with that for a second — it's the deepest fact about this machine. After a million letters, its entire memory of them is one state name. If two different inputs lead to the same state, the machine has permanently forgotten every difference between them, and will treat their futures identically. Pocket that; it returns in §06 as the machine's fatal weakness.

Nobody thinks in five numbered lists. There are two standard pictures of a machine, and they're good at different jobs.

The diagram

Circles are states. The arrow coming in from nowhere marks the start state. A double circle marks a yes-state. Each labeled arrow is one rule: "on this letter, go where the arrow points." Here's the even-a's machine:

The rule table

The same machine as a table: one row per state, one column per letter, each box holding the state you go to. We mark the start state with → and yes-states with *.

→ marks the start state; * marks a yes-state.

Use the diagram for thinking — your eye follows arrows the way the machine follows input, and a bad design usually looks wrong. Use the table for checking and for code: every box filled with exactly one state, visible at a glance, and it's character-for-character what you'll type into Python in §07.

Running a machine is a walk. Put a finger on the start state, read the input left to right, and let each letter push your finger along an arrow. Here's the even-a's machine on abba, written out in full:

1. Before reading anything: in E.
2. Read a — rule says E plus a goes to O. Now in O.
3. Read b — O plus b stays at O. Still in O.
4. Read b — still in O.
5. Read a — O plus a goes back to E. Now in E.

Out of letters. We ended in E, and E is a yes-state, so abba gets a yes — correct, since it has two a's. Notice: a four-letter input made a five-state walk, because there's a state before the first letter too. Half the off-by-one bugs in Project 1 come from forgetting that first state.

And the empty string? The machine reads nothing, so it just stands on its start state. If that's a yes-state, the empty string gets a yes — the verdict is settled before anything is read. That's why the empty string is the first test in every suite you'll write.

Now stop reading and drive the thing. Pick a machine below, type an input, and step through one letter at a time. Watch three things move together: the finger on the tape, the current state (with its plain-words meaning), and the highlighted box of the rule table — the rule about to fire. Whenever any of the three surprises you, that's the lesson.

Every machine design starts with the same question, so memorize it: what is the least I need to remember about what I've seen so far? Each possible answer becomes one state. If a handful of answers covers every situation, you have your machine — wire the arrows, mark the yes-states, done. Two worked examples.

1 · "Ends with b" — remember only the last letter

To know whether a string ends with b, you only need one fact at any moment: was the most recent letter a b? Two states: N ("last letter wasn't b — or nothing read yet") and B ("last letter was b"). Every new letter simply overwrites the memory.

The empty string gets a no here — N isn't a yes-state — which is right: a string with no letters doesn't end with b.

2 · "Contains bb somewhere" — a progress meter

Now the memory is progress toward a goal: no b just now, one b just now, found bb. Watch the middle state: if you're one b in and an a arrives, your progress is wasted — back to the start. But once bb has appeared, nothing can un-appear it, so the third state is a trap: all its arrows loop back to itself. A yes-trap means "found is found forever"; the simulator's "starts with ab" machine has a no-trap too, for strings that blew their chance on letter one.

q1 means "the previous letter was b, no bb yet" — an a wastes that progress and sends you back to q0. q2's row is all q2: found means found. Draw the diagram yourself as practice; the simulator below will grade your intuition.

Step through both in the §04 simulator with your own inputs. And build this habit now: name each state with the plain fact it stands for — "last letter was b," "one b of progress." If you can't say what a state means, the design isn't done.

After §05 you might suspect that a clever enough choice of states can handle anything. It can't, and you can feel exactly where the wall is. Take the counting language from Notes 01: some a's, then exactly the same number of b's — ab, aabb, aaabbb, and so on.

Ask the design question: while the a's stream past, what's the least you must remember? The exact count. Not "even or odd," not "more than five" — the count itself, because at the end you'll have to match it against the b's. And the count has no ceiling, while your states were fixed before the belt started.

Here's why that's fatal, in plain words. Say your machine has ten states, and I feed it eleven all-a strings: a, aa, aaa, up to eleven a's. Eleven strings, ten states — two of them must land on the same state. Say it's three a's and seven a's. From §02 you know what that means: the machine has permanently forgotten the difference. Now append three b's to each. One result is aaabbb — counts match, should be yes. The other is seven a's and three b's — should be no. But both walks continue from the same state reading the same letters, so they end in the same place, with the same answer. Whatever the machine says, it's wrong about one of them. A bigger machine just needs a longer list of a-strings to trip it.

This machine can count up to any limit you build in ahead of time. What it can't do is count without a limit.

(Notice the argument's style — assume it works, hit a wall. Flavor 2 from Notes 01, doing real work.) So the field test is: does the job need a handful of remembered situations, or an endless supply? "At most 40 a's" — fine, forty-odd situations, fixed in advance. "Same number of a's as b's" — hopeless; the count can grow forever. Jobs that need unlimited counting have walked off this rung of the ladder, and they wait for Week 6's bigger machine.

The payoff of "five plain things": the machine drops into Python with almost no translation. A machine is just data — a dictionary with five entries. Here's even-a's:

EVEN_AS = {
    "alphabet": {"a", "b"},          # the letters allowed
    "states":   {"E", "O"},          # the situations it can be in
    "start":    "E",                 # where it stands before reading
    "accept":   {"E"},               # the yes-states
    "delta": {                       # the rule table ("delta" is its
        "E": {"a": "O", "b": "E"},   #  traditional name in every book)
        "O": {"a": "E", "b": "O"},
    },
}

Compare "delta" with the §03 table — they match box for box. The runner is the conveyor-belt game as a loop: start state, one rule-table step per letter, then check for a yes-state. Ten lines, and they're the seed of Project 1.

def run_dfa(m, w):
    # Walk machine m over string w. One pass, no peeking ahead.
    state = m["start"]
    for ch in w:
        if ch not in m["alphabet"]:
            raise ValueError(f"{ch!r} is not one of this machine's letters")
        state = m["delta"][state][ch]      # look up the one rule and follow it
    return state in m["accept"]            # did the walk end on a yes-state?

# The empty string first, always — then the shortest strings that differ.
assert run_dfa(EVEN_AS, "") is True        # zero a's is even
assert run_dfa(EVEN_AS, "a") is False
assert run_dfa(EVEN_AS, "abba") is True

Notice what's not in run_dfa: anything about a's, b's, or evenness. It runs any machine you hand it — the job lives entirely in the data. That separation is the whole design of Project 1: one engine, many machines. Type these lines yourself tonight — type, don't paste — and the project's first milestone is half done.

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

The Project 1 handout comes out this week on the course repository. Next week's machine is a small twist on this one — a machine that's allowed to guess — so arrive with tonight's machine solid.

Coming up

Sessions 4 and 5 (Sept 15, 17) — Notes 03. A machine that's allowed to guess, and the trick that turns its guesses back into honest work. Project 1 begins in earnest.

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