The Machine With Paper

Quick recap of the climb. The honest machine of Week 2 had no paper at all — its entire memory was which state it was standing in. The stack machine of Week 7 got a stack of plates: real memory, but it could only ever look at the top plate. And every wall we hit all semester — the counting language, palindromes, equal a's, b's, and c's — came from the same place: crippled memory.

So this week we stop crippling it. Take the machine from Week 2 and hand it one thing: an endless strip of paper, divided into squares, with the input already written on it. The machine can read the square it's standing on, write over it, and step left or right. That's the entire upgrade. No second gadget, no new trick — just paper and a pencil with an eraser.

It doesn't sound like much. It is everything. With that one upgrade, the machine can do anything your laptop can do — anything any physical computer can do. The ladder we've been climbing since Week 1 ends here, on this rung. There is no stronger machine coming in Week 12.

Every wall we ever hit was a memory problem. This machine has no memory problem.

A moment for the person it's named after. In 1936 — roughly a decade before the first real computers were built — a young British mathematician named Alan Turing sat down and invented the computer on paper: he imagined a person doing arithmetic with a pencil, an eraser, and a long strip of squared paper, and asked what the laziest possible version of that person could still compute. Every laptop, phone, and server on Earth is his paper invention wearing plastic, which is why the machine you meet tonight is called a Turing machine.

Here is the whole machine. Three parts, all of which you already know in some form.

Two of the states are special, and they end the run on the spot. Reach ACCEPT and the machine stops and says yes. Reach REJECT and it stops and says no. There's also a quieter way to reject: if the machine is in some state, sees some symbol, and the rule table simply has no rule for that combination — no rule means no, and it stops.

Notice what disappeared: the conveyor belt. The old machines read the input once, left to right, and whatever rolled past was gone forever. This machine's input just sits there on the tape. It can read a square, walk away, come back, read it again, cross it out, write something else. The tape isn't just input — it's scratch paper.

And now the strange part, said gently. The old machines always finished: the input ran out, and with it the run. This machine's run ends only when it reaches ACCEPT or REJECT — and nothing guarantees it ever does. A machine can walk right forever, looking for a letter that isn't there. So every run has three possible endings now: yes, no, or it just keeps going. Hold that thought for Week 11 — it turns out to be the most important loose thread in this course.

Suppose a run is going and I hit pause. What do you need to write down so that, a week from now, anyone could resume the run exactly where it left off? Think about it — the answer is exactly three facts:

1. What's on the tape — every square that's been written on.
2. Where the head is standing.
3. Which state the machine is in.

Which means a run is nothing mysterious: it's a filmstrip of snapshots, each frame produced from the one before it by a single rule. First frame: input on the tape, head on the leftmost square, start state. Then frame, frame, frame — until a frame lands in ACCEPT or REJECT, or the filmstrip just never ends.

Why make a word for something this simple? Because the snapshot is how your simulator will work. When you build Project 3, your run function won't be clever: it'll hold one snapshot in three variables and loop — look up the one rule that fits, produce the next snapshot, repeat. The machine on paper and the machine in Python are the same filmstrip. And in Week 11, snapshots become the star of the strangest argument in the course.

Time to settle an old score. The counting language — some a's, then exactly that many b's — beat the honest machine in Week 2 and needed the loop trick in Week 5 to prove it. Tonight it falls in four states, and you'll watch every step.

How would you check equal a's and b's with a pencil and no ability to count past ten? You'd pair them off: cross out an a, cross out a b, and repeat until something runs out. That's exactly the machine's plan, and because the head can only shuffle one square at a time, the plan looks like a zigzag:

1. Grab the leftmost fresh a and cross it off (write x over it).
2. Hunt rightward for the first fresh b, and cross it off (write y).
3. Walk back left to the frontier of crossed-off letters, and repeat.
4. When there are no fresh a's left, sweep right to make sure no stray letters survived — then ACCEPT.

If anything is ever out of place — a b where an a should be, a letter left over after the pairing — there's simply no rule for it, and no rule means REJECT. Here's the filmstrip for aabb, abbreviated to the interesting frames. The square in brackets is where the head stands:

Two a's, two b's, all crossed off in pairs, nothing left over. Yes. Feed it aab instead and the hunt for the second b finds only a blank — no rule for that, so REJECT.

Now drive it yourself. This simulator is the heart of the week — and it's the seed of Project 3, because what it does is exactly the snapshot loop from §03. Watch four things move together: the head on the tape, the state (with its plain-words meaning), the highlighted rule about to fire, and the log of snapshots scrolling by. Press Play and let it zigzag; press Step when you want to see one rule at a time.

Three machines to explore. The zigzag is tonight's hero — try aabb, ab, the empty string, then watch aab, abb, and ba die in three different ways. Even number of a's is Week 2's honest machine wearing its new clothes: it never writes, never turns around, and you can see how little of the tape's power it uses. And the wanderer is the dark one: it accepts nothing, rejects nothing, and never, ever stops. Give it any input and watch the step counter climb. That queasy feeling is Week 11 knocking.

Here's the week's second headline, and it's the opposite of everything the ladder taught you. Until now, more hardware meant more power: a stack beat no stack, guessing beat honesty. Give the Turing machine upgrades, though, and something new happens — the upgrades make it faster and comfier, but not one bit smarter. Same jobs, same yes piles, exactly.

More tapes? Same machine.

Give the machine three tapes, each with its own head. Lovely for the zigzag: input on tape one, crossed-off a's on tape two, no walking back and forth at all. But it can't do anything new — a one-tape machine can imitate it. Picture a cook with three counters versus a cook with one long counter: the one-counter cook keeps the three work areas side by side on it, with a little marker where each "head" would be, and jogs between them. Same dishes come out of the kitchen. More trips.

A guessing version? Same machine.

Remember Notes 03: let the machine split into parallel copies, one per choice, and say yes if any copy reaches ACCEPT. For the honest machine, guessing added no power. For the stack machine, it genuinely did. Up here? No power again. An ordinary Turing machine can chase the copies itself: keep a to-do list of every live copy's snapshot on its tape, and work through the list — exactly the copies tracker you built in Week 3, just living on paper. Possibly outrageously slower, and that word "slower" is a loaded gun: whether guessing buys Turing machines speed is the P versus NP question from the Week 7 ladder aside, waiting for us in Week 13.

A tape that's endless both ways? Same machine.

Our tape has a left end and runs forever to the right. Some books let it run forever in both directions. Doesn't matter: take the both-ways tape and fold it in half at square zero, like folding a long ribbon. Now the squares sit in two layers on a one-way tape, and the machine just remembers (in its state) which layer it's reading. Every both-ways machine becomes a one-way machine with a crease in it.

Every reasonable upgrade lands in the same place. This rung isn't just higher — it's the ceiling.

And that's the moral, stated big. More tapes, guessing, a fancier tape, a bigger alphabet of tape symbols, even random access like your laptop's memory — people have tried them all, and every single one simulates down to the plain one-tape machine. When every road leads to the same summit, you start to suspect the summit is the real thing. One sentence of vocabulary for next week: anything any physical computer can do, this paper machine can do — textbooks call that idea the Church–Turing thesis, and Week 10 is about why nearly everyone believes it.

Same move as Week 2: the machine is data, and the runner is a short loop that knows nothing about any particular job. The rule table is a dictionary. Each key is a pair — which state, which symbol it sees. Each value answers the three questions: write what, step which way, go to which state. Here's the zigzag, whole:

ZIGZAG = {
    "start": "grab",
    "blank": "_",                              # what an untouched square holds
    "rules": {
        # (state, symbol it sees): (write this, step this way, go here)
        ("grab",  "a"): ("x", "R", "hunt"),    # cross off an a, go hunt its b
        ("grab",  "y"): ("y", "R", "sweep"),   # no fresh a's left: final sweep
        ("grab",  "_"): ("_", "R", "ACCEPT"),  # empty input counts as paired
        ("hunt",  "a"): ("a", "R", "hunt"),
        ("hunt",  "y"): ("y", "R", "hunt"),
        ("hunt",  "b"): ("y", "L", "back"),    # cross off its b, turn around
        ("back",  "a"): ("a", "L", "back"),
        ("back",  "y"): ("y", "L", "back"),
        ("back",  "x"): ("x", "R", "grab"),    # frontier found: grab the next a
        ("sweep", "y"): ("y", "R", "sweep"),
        ("sweep", "_"): ("_", "R", "ACCEPT"),  # only crossed-off letters remain
    },
}

def run_tm(m, w, cap=10_000):
    # One snapshot = tape + head + state. Loop: next snapshot, next snapshot...
    tape = dict(enumerate(w))                  # square number -> symbol
    head, state = 0, m["start"]
    for _ in range(cap):                       # why a cap? hold that thought (Week 11)
        seen = tape.get(head, m["blank"])
        if (state, seen) not in m["rules"]:
            return False                       # no rule fits: reject
        write, step, state = m["rules"][(state, seen)]
        tape[head] = write
        head += 1 if step == "R" else -1
        if state == "ACCEPT": return True
        if state == "REJECT": return False
    raise RuntimeError(f"still running after {cap:,} steps -- maybe forever?")

# The empty string first, always.
assert run_tm(ZIGZAG, "") and run_tm(ZIGZAG, "ab") and run_tm(ZIGZAG, "aabb")
assert not run_tm(ZIGZAG, "aab") and not run_tm(ZIGZAG, "abb") and not run_tm(ZIGZAG, "ba")

Read the loop against §03 and you'll see they're the same picture: tape, head, state are the snapshot's three facts, and each pass of the loop is one frame of the filmstrip. The tape is a dictionary rather than a list for one sweet reason: a dictionary doesn't care if head wanders to square 500 or square -3 — untouched squares just read as blank. Endless paper, four lines of bookkeeping.

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

The ladder is climbed. What's left of the course is learning what the view from the top shows — starting next week with what this machine can decide, and in Week 11, what even it cannot.

Coming up

Sessions 18 and 19 (Nov 3, 5) — Notes 10. The Church–Turing thesis gets its full hearing: why "computable" means "this machine can do it," and the difference between a job a machine can decide and one it can merely recognize — which is where the third ending, "never stops," stops being a curiosity and starts being the whole story.

And Project 3's spec drops this week — watch the course page.

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