The Machine That Guesses

Last week's machine was honest to a fault: one rule per situation, no choices, no luck. This week we hand it a superpower real computers don't have — and on Thursday we take the superpower away and discover, surprisingly, that nothing is lost. That round trip is one of the prettiest ideas in the course, and you'll code it in Project 1.

Start with a job that sounds easy: sort strings by whether the third letter from the end is an a. By eye it's instant — count three from the right, look, done. Now try to be last week's conveyor-belt machine. You read left to right, and you never know when the string is about to end — so any a going past might be the decisive one, and you won't know until two more letters arrive and the belt stops. To cope, an honest machine must constantly memorize the last three letters, just in case: a state for every possible three-letter ending, eight states, arrows everywhere. It works, and building it by hand is miserable.

But notice what a human would love to do: skim along, then at some moment point at an a and say "I bet that's third from the end" — and check that exactly two letters follow. That "I bet" is a guess about the future. Last week's machine can't make one. This week's machine can.

Guessing here isn't luck or coin flips. The rule is: if there was any way to guess right, the answer is yes.

The guessing machine is last week's machine with the "exactly one rule" law repealed. Three things change, and only three.

How do you run a machine that gets choices? Two mental pictures, both correct — use whichever helps.

Picture one: the lucky guesser. Imagine the machine always guesses right, as if someone who has seen the whole string whispers the best choice at every fork. If any winning path exists, the whisperer finds it. So a no means something strong: even perfect luck loses.

Picture two: parallel universes. The machine never chooses — it splits. At every fork, one copy goes each way, and all copies run at once. A copy that hits a dead end vanishes. When the string ends, the answer is yes if at least one surviving copy stands on a yes-state. This is the picture you can actually compute with — just track where all the copies are — and it drives both demos tonight.

Here's the guessing style on a simple job: strings that end with ab. The plan: skim in state 0; at some a, guess "the final ab starts here" and hop to state 1; demand a b to reach state 2; and state 2 insists the string is over — by having no arrows at all.

In a diagram, the guess would show up as two arrows for a leaving state 0 — one looping back, one committing to state 1. In the rule table, boxes now hold lists of options. A dash means no rule at all: any copy standing there when that letter arrives is done for.

Compare with last week: there, every box held exactly one state. Here a box can hold two options, or none.

Run it on ab by hand, following every path. The timid path: stay in 0 on the a, stay in 0 on the b — ends in 0, not a yes-state. The bold path: jump 0 to 1 on the a, then 1 to 2 on the b — ends in 2, a yes-state. One path failed, one succeeded, so ab gets a yes. One success outvotes any number of failures — that's the whole game.

Chasing every path by hand gets old fast. The parallel-universes picture fixes that: keep a running list of every state some copy is standing in, and move the whole list one letter at a time. Each step is mechanical — every copy follows every arrow it can (splitting at forks), copies with no arrow vanish, then any newly available free moves get taken. No guessing. Just bookkeeping.

The tracker below does exactly that: chips are states, lit chips are where copies stand, and the log narrates each step. It holds the "ends with ab" guesser, the "third letter from the end" machine — and a third machine that shows off free moves. That one answers, for strings of a's only, "is the length even, or a multiple of 3?" It's two little counters glued together by free moves out of the start state: before reading anything, the machine has already split into both. That's free moves doing their favorite job — building an "or" out of machines that never interact.

Spend real time here — predict the lit chips before each step, then click. Notice two things as you play: the number of copies can grow (on "ends with ab," every a spawns a fresh "maybe it starts here" copy while the skimmer lives on), and if all copies die at once, no letter can revive them — the answer is already no, with input still left to read.

Look how cheap the hard job from §01 became. "Third letter from the end is a," as a guessing machine: skim in state 0; at some a, guess "the countdown starts now" and hop to state 1; ride out exactly two more letters — any letters — through states 2 and 3. State 3 is the yes-state and has no arrows, so the guess only pays off if the string ends right on cue. Four states, and you can read the strategy straight off the picture. The honest machine needed eight states of rolling memory.

And it scales embarrassingly well. "Tenth letter from the end"? The guesser: eleven states — a skimmer plus a ten-step countdown. The honest machine must memorize the last ten letters at all times: over a thousand states. Same job, and the gap grows out of control.

A guessing machine is how you write the job down. An honest machine is how you run it. Tonight's trick is the translator between them.

That's the real division of labor. Guessers transcribe intent — every "somewhere" becomes a guessed position, every "or" becomes a free-move split. Honest machines execute — one lookup per letter, no luck involved. What's missing is a bridge between them, and that's §06.

Now the payoff. What did the tracker actually need to run a guessing machine? Not luck. Not split universes. Just the list of lit chips — and each step turned the current list into the next by pure bookkeeping. Same list in, same list out, every time. No choices anywhere.

But "no choices, one definite step per letter" is exactly last week's honest machine. So here's the trick, and it's almost cheeky: build an honest machine whose states are the possible lists. Each "which chips are lit" combination becomes one state of a new machine, and the new rule table just records the bookkeeping: from this list, reading this letter, you always get that list. A list counts as a yes-state if any chip in it is a yes-chip — one surviving copy was always enough.

Let's do it for "ends with ab," by hand, chasing only lists that can actually come up:

1. Start: only state 0 is lit — the list is {0}. From {0}: reading a, copy 0 splits, giving the list {0,1} — new, note it down. Reading b: still {0}.
2. From {0,1}: reading a — the 0-copy splits into 0 and 1, the 1-copy dies (no a arrow); result {0,1}, already known. Reading b — the 0-copy stays, the 1-copy advances to 2; result {0,2} — new, note it down.
3. From {0,2}: reading a — 0 splits, 2 dies; {0,1}. Known. Reading b — {0}. Known. Nothing new left. Done.

A finished, honest rule table — every box holds exactly one thing. The names in the boxes happen to be lists, but so what? Names are names. * marks {0,2}, the only list containing yes-chip 2.

Three states — and here's the delightful part: the lists mean something. {0} is "no progress toward a final ab." {0,1} is "the previous letter was an a." {0,2} is "the previous two letters were ab." The mechanical procedure rediscovered exactly the states a thoughtful designer would have invented. And why believe the new machine always agrees with the old? Because at every moment its state is the tracker's list, updated by the tracker's own rule — the same computation in different clothes. Run both demos on the same string and watch them agree, step for step.

This trick is called the subset construction — each new state is a subset, a sub-list, of the old machine's states — and it's the centerpiece of Project 1. The stepper below performs it one row at a time. Predict each row before clicking; that's the whole exercise.

One honest cost, so you're never surprised by it. Usually few lists actually come up — three here, out of eight possible. Sometimes almost all of them do: convert "third letter from the end" in the stepper and count. For "tenth from the end," the converted machine really needs those thousand-plus states — §05's rolling memory wasn't wasteful, it was necessary, and no trick dodges it. The conversion is never wrong; it's occasionally big. (If every copy dies, the construction just adds one extra state — the empty list, a no-trap where dead runs wait out the string.)

Step back at what we proved by doing: every guessing machine can be converted into an honest machine with the same answers. Guessing makes machines wonderfully easy to design — and adds no new power at all.

Same dictionary shape as last week, with the boxes upgraded to hold sets of options. A missing entry means "no rule" — a dead end. Free moves live under the key "": a move that reads nothing, filed under the letter that is nothing. Here's "ends with ab" (no free moves):

ENDS_AB = {
    "alphabet": {"a", "b"},
    "states":   {0, 1, 2},
    "start":    0,
    "accept":   {2},                     # the yes-states
    "delta": {                           # boxes now hold SETS of options
        0: {"a": {0, 1}, "b": {0}},      # on a: fork — stay, or commit
        1: {"b": {2}},                   # no "a" entry: that copy dies
        2: {},                           # no rules at all
    },
}

One helper first: given some states, follow every available free move (and free moves after free moves) until nothing new appears. It returns a frozenset — Python's immutable set, which unlike a plain set may serve as a dictionary key. That matters in a moment.

def add_free_moves(n, states):
    # Everything in `states`, plus anywhere reachable by free moves.
    seen, todo = set(states), list(states)
    while todo:
        q = todo.pop()
        for r in n["delta"].get(q, {}).get("", set()):   # "" holds free moves
            if r not in seen:
                seen.add(r)
                todo.append(r)
    return frozenset(seen)

The runner is the copies tracker, word for word: keep the set of live copies; per letter, every copy follows every arrow it can, then free moves apply. If the set empties, answer no early — nothing revives a dead run.

def run_nfa(n, w):
    # Track every copy at once, one letter at a time.
    copies = add_free_moves(n, {n["start"]})
    for ch in w:
        moved = set()
        for q in copies:                              # each copy follows
            moved |= n["delta"].get(q, {}).get(ch, set())  # every arrow it can
        copies = add_free_moves(n, moved)
        if not copies:
            return False                              # everyone died — no is certain
    return bool(copies & n["accept"])                 # any survivor on a yes-state?

# Empty string first, always — then a yes and a no.
assert run_nfa(ENDS_AB, "") is False
assert run_nfa(ENDS_AB, "ab") is True
assert run_nfa(ENDS_AB, "aba") is False

And the converter? You already know it. It's this same loop, with one change: instead of following one input string, it charts where every letter leads from every list it discovers, until no new lists turn up — exactly what the §06 stepper does row by row. Writing that function, nfa_to_dfa, is the heart of Project 1, and its output should be an honest machine in last week's exact dictionary shape, so run_dfa can run it unchanged. The best test is agreement: for every short string you can generate, run_nfa(n, w) and run_dfa(nfa_to_dfa(n), w) must match. When they don't — and the first version won't — the shortest disagreeing string is small enough to trace by hand in tonight's demos.

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

Project 1 work starts now — every piece its handout asks for has appeared in these notes and Notes 02. Next week builds directly on tonight, so get your hands dirty early.

Coming up

Sessions 6 and 7 (Sept 22, 24) — Notes 04. Search patterns — the match-this-text language you may know as "regular expressions" — and how every pattern compiles into a guessing machine, which tonight's trick then makes honest.

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