One Machine to Rule Them All

Where the ladder left us. All semester, more hardware meant more power: the stack machine beat the honest machine, the paper machine beat them both. Then Notes 09 ended on something strange. We souped the paper machine up every way we could think of — three tapes, a guessing version, a tape endless in both directions — and not one upgrade could do a single new job. Every road led back to the same summit.

That pattern is either a coincidence or a discovery. Tonight we treat it as a discovery, give it its proper name, and ask two blunt questions about it. First: when we say every design lands in "the same place," what place, exactly? Second — and this is the week's real business — the boast says the paper machine can do any job a machine can do. But what does "can do a job" even mean for a machine that is allowed to run forever? It turns out there are two meanings, and the gap between them is where the rest of this course lives.

The boast comes with a warranty. This week we read the fine print.

Here is the claim, in one breath. Anything any physical computer can ever do — your laptop, a supercomputer the size of a building, a quantum machine, a computer built by aliens we haven't met — the paper machine can also do. Maybe absurdly slowly. But it can do it. There is no computing device, built or buildable, that sorts even one string into a yes pile the paper machine couldn't sort into the same pile.

Why would anyone believe something that sweeping? Because of what you watched happen last week, repeated across ninety years. Every time someone invents a new design for a computing machine, the same ritual plays out: the inventor shows what it can do, somebody sits down and shows the paper machine can imitate it, and the new design lands exactly on the paper machine's yes piles. Never once above. More tapes — same piles. The guessing version — same piles. A tape endless both ways, a bigger alphabet of tape marks, memory the head can jump around in like your laptop's — same piles, same piles, same piles.

One of those boxes deserves its trivia-night minute. Months before Turing drew his machine, an American logician named Alonzo Church built a system for computing with no machine at all — just recipes plugged into other recipes, pure pencil-and-paper substitution. (Its name, for trivia night: the lambda calculus; it's the great-grandparent of half of modern programming languages.) Two inventions, two totally different shapes, the same year — and they compute exactly the same yes piles. When two strangers dig tunnels from opposite sides of a mountain and meet in the middle, you start to believe the middle is really there. That's why the thesis carries both names.

Why it's a "thesis" and not a fact

Notice the careful word. Everything else in this course, we've been able to show: build the machine, or show no machine can exist. Why not this? Because look at what the claim quantifies over — not machines on a page, but every machine anyone could ever physically build, in this universe, forever. That's not a chess piece you can push around with logic. It's a claim about physical reality, and claims about reality can't be settled with a pencil. They can only be tested.

So here's the honest status of the Church–Turing thesis: it is a bet about the world that has survived ninety years of attempts to break it, by some very clever people, with some very exotic hardware. Think of the rule "no machine can run forever on no fuel" — perpetual motion. Physics can't prove that the way you prove two plus two; what it has instead is every attempt in history failing, so thoroughly that patent offices stopped reading the applications. Engineers bet bridges on that rule. Computer scientists bet this entire field on this one.

Not a fact you can prove — a bet about the universe that nobody has managed to lose in ninety years.

Here is the payoff, and it's enormous. From tonight on, the sentence "there is an algorithm for it" means exactly one thing: "a paper machine can do it." And because of the thesis, that means your Python function counts as a machine. Your pseudocode counts. A recipe written in plain English, precise enough that a patient person with no imagination could follow it, counts. They're all just outfits the paper machine wears.

Feel what that does to our workload. In Notes 09 you watched the zigzag take eighty-odd steps to compare a few letters, and writing its rule table was fiddly work. If the rest of the course had to happen at that altitude, we'd never get anywhere. The thesis is our permission slip to climb out of the engine room: when we want to claim "a machine can do this job," we no longer draw a rule table — we write a clear recipe, in Python or in sentences, and the thesis guarantees a rule table exists down below. This, by the way, is why every textbook on Earth draws Turing machines for exactly one chapter and then never again. We're doing the same. You've now seen the gears; from next week, we write recipes.

One thing the trade-in does not change: the three endings. A recipe, like the machine it stands for, can answer yes, answer no — or run forever. while True: pass is two lines of Python. The ghost from Notes 09 followed us up the ladder.

Now the fine print. Bring back the wanderer from Notes 09 — the little machine that accepts nothing, rejects nothing, and never, ever stops. It's about to go from a curiosity to the most important machine of the month. Because once "never stops" is on the table, the phrase "a machine can do this job" quietly splits into two different promises, and they are not the same.

Ask a machine a question — hand it a string, press go — and exactly three things can happen:

That third branch splits "this job is doable" into two grades, and this is the heart of the week. Plain words first, names after.

The good grade: a machine that always answers

The best thing a job can have is a machine that always stops and always answers correctly. Feed it any string whatsoever: some number of steps later — maybe many, but always some — it halts and says yes or no, and it's right. Like a vending machine: coin in, answer out, every single time. No run ever takes the third branch.

Our old friend "some a's, then exactly that many b's" is decidable, and the zigzag is the proof you can watch. Here's why you should believe the zigzag always stops, on every string, guaranteed: every lap crosses off one fresh a and one fresh b, so the stock of fresh letters strictly shrinks — and no walk between crossings can be longer than the written part of the tape. Shrinking stock, bounded walks: the run cannot go on forever. It isn't lucky; it's arithmetic.

The fine-print grade: a machine that answers if the answer is yes

Now the weaker promise. Some jobs come with a machine that catches every yes — feed it a yes-string and it will, sooner or later, stop and say yes — but on some no-strings it doesn't say no. It just… keeps running. It never lies; it may simply never speak. And here's the cruel part, the part the lab below will make you feel: while you're waiting, "about to say yes" and "never going to answer" look exactly the same. A climbing step counter, nothing else.

The analogy to keep: calling a friend who has no voicemail. If they're home, they pick up — eventually. If they're not, the phone just rings. At minute ten, what do you know? Nothing. They might be reaching for the phone right now; they might be on another continent. Ringing-forever and not-home are indistinguishable from your end of the line.

Ringing forever and not-home look exactly the same from your end of the line.

A job that wears the fine print

Does any natural job actually come with only the weaker promise? Here's one that at least smells like it. Take any rule table and any input string, and ask: "will this machine ever reach ACCEPT on this input?"

There's an obvious method: run it and watch. Simulate the machine step by step — your Project 3 workbench literally does this. If the answer is yes, the simulation will reach ACCEPT after some number of steps, and you'll see it: yes caught, fine print honored. But if the answer is no because the machine runs forever — a wanderer — your simulation runs forever right along with it. You wait, the counter climbs, and you can't tell "about to say yes" from "never." So the watch-and-wait method is a fine-print machine for this job: a recognizer, not a decider.

Careful, now — tonight we claim only that the obvious method has the fine-print flaw. Maybe somebody cleverer than us can find a method that always answers, some way to inspect the rule table and see "never" written in it without waiting. Whether such a method exists is exactly next week's question, and it is the most famous question in this field. Plant it; don't pick it.

Time to update the ladder one last time — except it isn't a ladder anymore. It's a set of nested shelves, every job we've met this semester sorted onto them:

Read it from the inside out, in plain sentences. Every honest-machine job is also a stack-machine job — a stack machine can simply ignore its stack. Every stack-machine job is decidable — your Project 2 checker answered yes or no on every string and always finished, and what that script did, a machine can do. And every decidable job is recognizable — the full warranty already includes everything the fine print asks for. Four shelves, each inside the next, with real jobs sitting on every one: "ends with abb" on the innermost, palindromes one shelf out, "equal a's, b's, and c's" — the language that beat the stack machine in Week 8 — comfortably on the decidable shelf.

And now the two questions this picture begs. Look at the dashed outer edge. Question one: is there any job at all outside the last shelf — a job so hard that no machine can even catch its yeses? Question two: is there a job on the outer shelf but not the inner one — genuinely recognizable, genuinely not decidable, a job where the fine print is the best warranty anyone can ever offer? Our watch-and-wait job from §04 is the obvious candidate… but a candidate is not a verdict.

Both answers come next week — and one of them broke mathematics a little.

You can't see a warranty by reading a machine's face. From the outside, a running machine is a running machine. The only way to feel the difference between the two grades is to wait on them — so here is a lab built entirely around waiting.

Four machines. Three of them carry the full warranty; one carries nothing at all. You get an input, a patience slider — the number of steps you're willing to wait — and a Fire button. The meter drains as the machine runs. Either the machine answers before your patience runs out, or it doesn't — and when it doesn't, notice precisely how much you've learned: nothing.

Experiments, in order — do them, don't skim them:

1. Feel "slow." Pick the marathon, keep the 12-letter input, patience at 150. Fire. It runs out of patience around step 150 — out of answer, out of luck. Now drag the patience to 500 and fire again. It answers, on its own, at step 169. "Slow" just means your patience was too small.
2. Feel "never." Switch to the wanderer. Any input, patience 150: out of patience. Patience 3000: out of patience. Patience one trillion, if the slider went there: out of patience. "Never" means no patience is ever enough.
3. Now the punchline. Put experiments 1 and 2 side by side in your head, at patience 150. The marathon's screen and the wanderer's screen were identical: a climbing counter, a drained meter, no answer. One machine needed a nudge more patience; the other will outlast the sun. Nothing on the screen distinguishes them. That is the fine print, felt from the outside.
4. Feel the full warranty. Run the zigzag and the even-a's machine on everything — long strings, junk strings, the empty string. They always land. That calm you start to feel, that you never have to wonder? That's what "decidable" buys. Mid-run, try dragging the patience slider or switching machines — the tester handles it; your curiosity should too.

One last upgrade to the Week 9 runner, and it's a vocabulary upgrade. The old version returned True or False and raised an error at the cap. But the lab just taught us the honest names for what a capped run can report — so let the runner say them:

def run_tm(m, w, cap=10_000):
    # Same snapshot loop as Week 9 -- only the verdicts grew up.
    tape = dict(enumerate(w))                 # square number -> symbol
    head, state = 0, m["start"]
    for _ in range(cap):
        seen = tape.get(head, m["blank"])
        if (state, seen) not in m["rules"]:
            return "REJECT"                   # no rule means no
        write, step, state = m["rules"][(state, seen)]
        tape[head] = write
        head += 1 if step == "R" else -1
        if state in ("ACCEPT", "REJECT"):
            return state                      # a real answer: the machine stopped itself
    return "STILL-RUNNING-AFTER-CAP"          # not an answer. a shrug.

assert run_tm(ZIGZAG, "aabb") == "ACCEPT"
assert run_tm(ZIGZAG, "ba") == "REJECT"
assert run_tm(WANDERER, "a") == "STILL-RUNNING-AFTER-CAP"

Read the three verdicts carefully, because they are not three answers. ACCEPT and REJECT are answers — the machine stopped itself. STILL-RUNNING-AFTER-CAP is not an answer; it's the drained meter from the lab wearing a longer name. The cap turns every machine into an always-stopper — but wrongly: it cannot tell "needed one more step" from "never," so the third verdict lumps the marathon and the wanderer into the same bucket, and they do not belong in the same bucket. Week 11 is about whether anything, anywhere, can sort that bucket correctly.

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

One machine, one thesis, two warranties, and a dashed line with a question mark beyond it. Next week we cross the line.

Coming up

Sessions 20 and 21 (Nov 10, 12) — Notes 11. Next week we meet a question no machine can answer — and we prove it in one page of plain words. Both cliffhangers from §05 get their answers, the watch-and-wait job gets its verdict, and the argument that settles it is the strangest and most beautiful thing in this course. One of those answers broke mathematics a little. Come rested.

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