The Question No Machine Can Answer

Here is where we stand. Every job we've ever met sits on one of the nested shelves: honest-machine jobs inside stack-machine jobs, inside the decidable jobs — full warranty, always an answer — inside the recognizable jobs, where the fine print says every yes gets caught but silence is not a no. The outermost edge of that picture is dashed, because last week we couldn't say what, if anything, is past it. Two questions were left hanging there, and the watch-and-wait job — "does this machine ever say yes?" — was left standing between them like a suspect with no verdict.

The two questions, once more, plainly. One: is there any job outside the last shelf — so hard that no machine can even catch its yeses? Two: is there a job on the recognizable shelf but not on the decidable shelf — a job where the fine print is the best warranty anyone can ever offer?

Tonight both get answered. Not with hand-waving, and not with a wall of symbols either — with one short story about a machine built to be disagreeable. You can tell the whole argument out loud in about a minute, and by the end of these notes you will. It is, I'll say it now, the strangest and most beautiful thing in this course.

One page of plain words is about to put a permanent hole in what machines can do.

Before we break something, let's be clear about what we'd be breaking. Imagine the gadget every programmer has wished for at 2 AM: a halting checker. Feed it any rule table and any input string, and it always — always — stops and gives one of two answers: "this machine stops" or "this machine runs forever." Full warranty. No shrug, no drained meter, no "out of patience." An answer, every time, and a correct one.

Feel the stakes before we go further, because they're enormous. With a halting checker in hand:

• Every infinite loop ever shipped gets caught before it ships. Your editor doesn't say "possible infinite loop" — it says "infinite loop, line 40," and it is never wrong.
• The watch-and-wait job gets a full warranty. "Does this machine ever say yes?" — first ask the checker whether the run stops. If "runs forever," the machine never gets to say yes: answer no, done. If "it stops," run it to the end — a finite wait, guaranteed — and read the answer off the screen. The fine print becomes a full warranty. Question Two, solved in a paragraph.
• Last week's patience slider becomes a museum piece. The tester's "OUT OF PATIENCE" shrug gets replaced by a true "NEVER," stamped with certainty.

And it gets stranger. Some of the most famous unsolved questions in mathematics are secretly questions about whether a small search program ever stops. Here's one, honestly framed:

So the halting checker would be, no exaggeration, the most valuable object ever built. Which is exactly why what happens next hurts. Tonight we show it can't exist — not "we haven't been clever enough yet," but cannot exist, the way the barber in the next section cannot exist.

The weapon we'll use is older than computers, and you may have met it at a party. A small town has exactly one barber, and the town charter is very proud of its rule: the barber shaves exactly the people who do not shave themselves. Everyone who doesn't shave himself — the barber shaves him. Everyone who does shave himself — the barber leaves him alone. Sounds like a perfectly sensible job description.

Now ask the party-trick question: who shaves the barber? Try both answers. If the barber shaves himself, then he's one of the people who shave themselves — and the rule says the barber must not shave those people. So he must not shave himself. But if he doesn't shave himself, then he's one of the people who don't — and the rule says the barber must shave exactly those. So he must shave himself. Each answer forces the other. There's no way out, and the conclusion isn't "what a puzzling barber." The conclusion is that no such barber can exist. The job description sounded fine, but the moment you turn it on the person doing the job, it eats itself.

Hold on to that exact shape: a rule about everyone, turned on itself, with a twist of "do the opposite" built in. ("This sentence is false" is the same trick in six words.) Tonight's argument is the barber with one substitution: instead of a rule about who shaves whom, a rule about which machines stop. And here's the part that should raise your eyebrows: the halting checker's job description quietly covers every rule table — including rule tables of machines that have the checker built into them. The rule covers the barber. All we need is a machine petty enough to exploit that.

Pretend, for the next few minutes, that the halting checker exists. Someone hands it to you: a working gadget, tested, boxed, full warranty. We're going to take it apart — not by finding a bug in it, but by building one small, legal, slightly evil machine around it.

First, a sanity check that the building materials are legal. Can a machine take a rule table as its input? Of course — you do it every day. A rule table is just symbols written in a row, and your Project 3 workbench eats exactly that: a machine, written down, handed to a program as data. Notes 10's runner was six lines of Python that takes any rule table and runs it. Machines reading machines isn't exotic. It's Tuesday.

Now the build. Around the checker, wire up a new machine. Call it the Contrarian. It takes one input: any rule table. And it does exactly two things:

1. It asks its built-in checker one question: "this machine here — would it stop, if you fed it its own rule table?"
2. Then it does the opposite of whatever the checker said. Checker says "it stops"? The Contrarian throws itself into a do-nothing loop, on purpose, forever. Checker says "it runs forever"? The Contrarian stops immediately, with a polite little bow.

So far, nothing illegal has happened. The Contrarian is a perfectly ordinary machine: it has a rule table of its own, sitting right there, written down. Which means…

Now feed the Contrarian its own rule table

The question on the table becomes: does this very run — the Contrarian, eating its own rule table — stop, or run forever? The checker inside is being asked exactly that question. Walk both of its possible answers, slowly.

Suppose the checker says "it stops." Then the Contrarian, hearing that, takes its first branch: it loops forever, on purpose. But wait — the run the checker was asked about is this run. The checker said this run stops, and this run just… didn't. The checker was wrong.

Suppose instead the checker says "it runs forever." Then the Contrarian, hearing that, takes its other branch: it stops, immediately. The checker said this run never stops, and the run just stopped, politely, right in front of everyone. Wrong again.

Step back and look at what just happened. The checker had exactly two possible answers, and we walked both: each one comes out wrong. But "always right" was the checker's entire job description — one guaranteed-wrong answer and it isn't a halting checker, just another program with opinions. And the Contrarian wasn't the suspicious part of the build: it's two steps of wiring that anyone with a checker could do. If the wiring is innocent and the result is impossible, the blame lands on the only exotic component in the box. The halting checker was never possible in the first place.

Notice what the argument did not use: nothing about speed, nothing about memory, nothing about today's technology. Only the checker's own promise, turned on itself with a twist of "do the opposite." That's why no future laptop, no quantum machine, no alien hardware escapes it — the Church–Turing thesis says they're all the machine with paper in a costume, and the Contrarian is waiting for each of them in exactly the same spot.

This section is optional dessert — the same argument again, drawn as a picture of infinity. If the Contrarian already clicked for you, you can skim this and lose nothing. If you like pictures, this one is a classic.

Imagine an endless table. Down the rows: every machine there is, one per row — machine 1, machine 2, machine 3, forever. Across the columns: every rule table, used as an input. Each cell records what happens: does machine number so-and-so stop when fed table number so-and-so, or run forever? One infinite spreadsheet holding the complete behavior of every machine that will ever exist. Now look at the diagonal — the cells where a machine meets its own table — and build a new row by walking that diagonal and flipping every cell: stop becomes never, never becomes stop. The flipped row can't be row 1 (it disagrees with row 1 in column 1), can't be row 2 (disagrees in column 2), can't be any row at all — it was built to disagree with row number whatever in column number whatever. But the table supposedly listed every machine. So no machine behaves like the flipped row… and the Contrarian is precisely a recipe for building a machine that does, if a halting checker exists to read the diagonal. The recipe is fine; the checker is the impossible part. Same argument, now in a spreadsheet.

One sentence of lore: the flip-the-diagonal trick was invented in the 1870s by Georg Cantor, who used it to show some infinities are bigger than others — and sixty years later Turing picked the same key off the shelf and opened this lock with it. Play with the finite toy version:

Time to pay last week's debts. Two questions were hanging over the shelves picture. The Contrarian settles both — one directly, one with a clever assist from a trick you already know.

Question Two: the gap is real

Take the job the Contrarian just demolished: "does this machine stop on this input?" Is it recognizable? Yes — by the humblest method in the course. Run the machine and watch. If it stops, you see it stop: ring the yes-bell. Every yes gets caught, sooner or later. That's the fine-print warranty, honored in full. But decidable? We just proved no machine always answers it. So here, at last, is a job that is on the recognizable shelf and provably not on the decidable shelf. The gap between the warranties isn't a gap in our knowledge. It's a gap in the world.

And the watch-and-wait job — "does this machine ever say yes?" — lives in the gap right beside it. Recognizable: same humble method, run it and wait for the yes. Not decidable, by a five-minute rewiring: take any machine you'd like to ask "does it stop?" about, and edit its rule table so that every way of stopping says yes — turn REJECT into ACCEPT, give every missing rule a rule that accepts. The rewired machine says yes exactly when the original stops. So a full-warranty answer to "does it ever say yes?" would hand you a full-warranty answer to "does it stop?" — and the Contrarian is standing right there, arms crossed. The two jobs are siblings: each is the other wearing a hat. The verdict on watch-and-wait: recognizable, not decidable. The fine print really is the best warranty it can ever have.

(File away the shape of that rewiring move — "if you could do this job, you could do halting." Next week we industrialize it.)

Question One: there is something beyond the last shelf

Now flip the question around: "does this machine run forever?" — the exact opposite job, where yes means never stops. Watch-and-wait is useless here, and not just slow-useless: there is no moment at which "it's still running" becomes "it will run forever." You can't finish watching nothing happen. But maybe some cleverer machine catches these yeses some other way? Here's why you should believe nothing can.

Remember last week's two-phones trick — you worked it out yourself in a reveal box: if a job has a fine-print machine and its opposite job has one too, run both machines taking turns, one step each. One of your two friends is home, so one phone eventually gets answered, and whichever rings first settles the question — always, in finitely many steps. A full warranty, built from two fine prints.

Now suppose "does it run forever?" were recognizable — some detector that eventually rings yes on every machine that never stops. Put it on one phone. On the other phone, put plain watch-and-wait for "does it stop?" — which we just said is recognizable. Every machine either stops or doesn't, so one of the two phones must ring. Whichever rings first, you have a guaranteed, always-correct, finite-time answer to "does this machine stop?" You have rebuilt the halting checker — the gadget the Contrarian killed an hour ago. Contradiction delivered. So no such detector exists: "does this machine run forever?" is not even recognizable. It sits outside the last shelf — a job so hard that no machine can so much as catch its yeses. The dashed edge has something beyond it after all.

One tidy way to say the whole picture: for the stop question, yes has a finite witness and no doesn't. If a machine stops, there's a moment you can point to — step 169, there, it stopped — and that pointable moment is why the yes side can always be caught. If it runs forever, there is no moment that proves it; the evidence would be infinitely long. The fine print catches exactly the jobs whose yeses come with a pointable moment. Their opposites — whose yeses are endless silences — fall off the shelf entirely.

The promised lore, kept short. In the 1920s, the great mathematician David Hilbert asked for something wonderful: a mechanical method that could answer every yes-or-no question in mathematics — feed in the question, crank the handle, out comes the truth. The dream even had a grand German name, the Entscheidungsproblem, "the decision problem." In 1931 Kurt Gödel shook it badly, and in 1936 a 23-year-old Alan Turing finished it: to even state what "a mechanical method" is, he invented the machine with paper — and then built the Contrarian and showed the method Hilbert wanted cannot exist. The machine you've spent three weeks with wasn't invented to compute. It was invented to prove this one impossibility. The computer is a by-product of tonight's argument.

Reading the argument is one thing. Losing to it is another. In this lab, you are the halting checker. Six exhibits: five ordinary machines to warm up on, and then the Contrarian itself. For each exhibit, give your verdict — stops, or runs forever — and the simulator runs the truth. The warm-ups are honest and you'll get good at them fast. The last exhibit is wired differently: it listens to your verdict first.

Do it in this order:

1. Warm up on all five. The sprinter and the zigzag are old friends; the ping-pong and the wanderer wear their fates in their rules; the marathon will test your nerve near the cap. Build a streak. Feel like a good halting checker — for these toys, you genuinely are one.
2. Then open the last exhibit. Read its description carefully: it contains your verdict as a component, and it's fed its own rule table. Call it.
3. Call it the other way. Notice that both buttons lose, and read why. Then say the §04 argument out loud, once, from memory. If it comes out in under a minute, you own it.

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

You now own something rare: a genuine impossibility, proved, in your pocket. Next week we learn to spend it.

Coming up

Sessions 22 and 23 (Nov 17, 19) — Notes 12. Now that we own one impossible job, we get wonderfully lazy. To prove a new job impossible, we'll stop building new Contrarians and instead show: "if you could do that, you could do halting" — a photocopier for impossibility. You caught the first copy tonight, in the rewiring trick and the antivirus question. Then Rice's theorem, the heavyweight: one result that stamps "undecidable" on almost every question about what a program does. Project 3 is due 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.