The Impossibility Photocopier

Last week you watched a job die. The stopping question — does this machine stop, on this input? — turned out to have no full-warranty answer, not now, not ever, because any checker that claims one can be wired into a Contrarian and fed its own rule table. That argument took real work: a custom machine with a bad attitude, two branches that eat themselves, a story you practiced telling in under a minute. Here is tonight's good news. You will never have to do that work again.

Because last week also hid a second trick in plain sight, and it's the one that scales. When we settled the watch-and-wait job — "does this machine ever say yes?" — we did not build a second Contrarian. We rewired: edit any machine so that every way of stopping says yes, and suddenly a solver for "ever says yes?" would hand you a solver for "does it stop?" — which is impossible, so the solver is too. And the notes told you, in so many words: file away the shape of that rewiring move — "if you could do this job, you could do halting." Next week we industrialize it.

It's next week. The Contrarian dug one hole. Tonight's gadget — call it the impossibility photocopier — copies that hole onto any question you can wire it to. By the end of the evening you'll have run the photocopier yourself, pointed it at three different questions, learned the one direction rule that keeps it honest, and then met the result that makes even the photocopier look slow: a single stamp that covers almost every question about what a program does. One hole, dug once, spent forever.

Dig one hole by hand. Then photocopy it onto everything else.

Here's the machine at the heart of tonight, and the first thing to notice is how humble it is. The photocopier's engine is just a translator: a plain, ordinary program — with a full warranty of its own, it always finishes — that takes any instance of the stopping question and rewrites it as an instance of some new question, so that the answers match. If the old answer was yes, the new answer is yes. If the old answer was no, the new answer is no. The translator never solves anything. It never even runs anything. It just rephrases.

Read that argument once more, slowly, because it's the whole night. Suppose somebody claims to sell a solver for the new question — always stops, always right. You bolt the translator onto the front of their box: stopping question in, translated, their solver answers, and the answer carries straight back, because the translator made the answers match. You are now holding a working halting checker. But there is no working halting checker — a one-page argument with a barber in it made sure of that, permanently. The only way out: the solver they claimed to sell was never real.

Time to build one, slowly, bolt by bolt. Target: the ever-yes question — "does this machine ever say yes, to any input at all?" Last week a quick rewiring showed this question is hopeless; tonight we redo it as an official photocopy, because this exact build is the template for every other one you'll ever make.

The translator receives an instance of the stopping question: a stored machine and a stored input, stapled together. It must output a single new machine whose ever-yes answer equals the stopping answer. Here's the machine it writes — call it the wrapper. The wrapper's entire program is three lines:

1. Throw your own input away. Whatever you were handed — abba, the empty page, a love letter — into the trash, unread.
2. Run the stored machine on the stored input. The one sealed in the envelope. Just run it, step by step, like the workbench does.
3. If that run ever finishes — any way at all, yes or no — say yes.

Now check the mirror, both ways, because the matching answers are the entire job. If the stored run stops: step two always finishes — on every input the wrapper is handed, because step one threw that input away, so every run is the same run. Everything reaches step three. The wrapper says yes to everything, so "does it ever say yes?" is yes. If the stored run never stops: the wrapper spends eternity inside step two — again on every input — and never reaches the yes. Its yes pile is empty, so the ever-yes answer is no. Stops ↔ yes. Runs forever ↔ no. A perfect mirror — which means a solver for ever-yes, with this translator in front, answers the stopping question. Stamp it: the ever-yes question has no full warranty, ever.

One design choice deserves a spotlight: why does the wrapper trash its own input? Because the mirror needs the wrapper's fate to be all-or-nothing. If the wrapper peeked at its input, different inputs might end differently, and "ever says yes" would tangle up with what got fed in. Trash the input, and the wrapper has exactly one possible life, replayed on every input: either everything gets a yes or nothing does, and which one depends only on the envelope. That one rude move — ignore the customer, consult the envelope — is the signature move of nearly every photocopy ever built.

Second target, and this one should sting a little, because every teacher on Earth wants it: the twins question, also known as the same-yes-pile question — "do these two machines have the same yes pile?" Say yes to exactly the same inputs, no to exactly the same inputs: twins in behavior, whatever their rule tables look like. A solver for this is the dream autograder: compare the student's code to the reference answer on all inputs at once, no test cases needed.

The photocopy takes two sentences. The translator builds the same wrapper as before — trash your input, run the envelope, say yes if it finishes — and then grabs one more part off the shelf: the cheerleader, a one-rule machine that says yes to everything, instantly, no questions asked. The instance of the twins question is the pair: wrapper on the left, cheerleader on the right. Are they twins?

Walk the mirror. If the stored run stops, the wrapper says yes to everything — which is precisely the cheerleader's yes pile. Same pile: the twins answer is yes. If the stored run never stops, the wrapper's pile is empty while the cheerleader's pile is everything — as far from twins as two machines can be. The answer is no. Stops ↔ yes, runs forever ↔ no, mirror confirmed. A twins solver would answer the stopping question through this two-sentence translation, so: stamped. No machine can always tell whether two machines behave the same. The dream autograder joins the halting checker in the museum of gadgets that never were.

Every powerful tool has the one way to hold it wrong, and here is the photocopier's. The translation must run from the question you already know is impossible, into the new one. From the stopping question, into fresh territory. Point it the other way and the machine still hums, lights still blink — and it proves absolutely nothing.

Here's the analogy to keep: "If I could lift the car, I could certainly lift the couch." True! And it tells you nothing about the couch, because you can't lift the car — a claim that starts from an impossible feat ends nowhere. The useful direction is the other one: "if I could lift the couch, I could lift the car" — say, because a cunning system of levers turns one into the other. That would be big news about the couch: since the car is beyond everyone, the couch must be too. The translator is exactly that system of levers, and it must turn couch-lifting into car-lifting, not the reverse.

After a few photocopies, a pattern should be itching at you. Ever says yes? Stamped. Says yes to the empty page? Stamped — same wrapper, we'll run it in the lab. Same yes pile as another machine? Stamped. Every target so far has been a question about a machine's behavior — about its yes pile, about what it does. And meanwhile a whole family of questions never gets stamped at all, because they're not about behavior. They're about the paper.

"Does the rule table have more than ten rules?" Count the rows. "Does it ever mention the letter b?" Read the table. "More than five states?" List them. These are questions about the document — ink on a page, finite, sitting still, fully visible. You don't predict anything; you look. Full warranty, trivially, every time. The entire dark magic of this course lives on the other side of that line, where a finite page of ink commits the machine to an endless, unreadable future.

The stamp, stated plainly

And one honest boundary from the other side: the stamp is about the machine's whole, unbounded behavior. A question with a built-in patience slider — "does it stop within 1,000 steps on this input?" — isn't in the cloud at all. Just run it for 1,000 steps and look; a bounded run is a finite job, full warranty, done. The stamp owns the questions where the answer could hide past every step count you'll ever reach.

Here's why you should believe it

One photocopier template handles every behavior question at once — that's the whole argument, and you already own every part. Take any behavior question that isn't trivial. First, look at the machine whose yes pile is empty (the stonewaller's pile): either it fails your question or it passes. Say it fails (if it passes instead, run everything below with your yes-glasses and no-glasses swapped — one extra wire, like in the twins build). Second, since your question isn't trivial, some machine passes it — pick any one and call it the pet. Now re-aim the wrapper from photocopy no. 1, changing only line three:

1. Hold your input — don't read it yet.
2. Run the envelope: the stored machine on the stored input.
3. If that run ever finishes, dig your input back out and behave exactly like the pet on it — same answer the pet would give, yes or no.

If the stored run stops, every run of this wrapper gets past step two, and from there it is the pet, answer for answer: its yes pile is the pet's yes pile, so it passes your question. If the stored run never stops, the wrapper never answers yes to anything: empty pile, and we arranged for the empty pile to fail. Passes ↔ stops. Fails ↔ runs forever. That's a working translator from the stopping question into your question — whichever behavior question it was, because nothing in the build cared which. A solver for your question would resurrect the halting checker. Stamp comes down. The photocopier didn't just copy the hole one more time. It copied it onto an entire category, in one motion.

Let's spend the stamp. Each of these is a product somebody — your future boss, possibly — will one day ask you to build "perfectly." Each is a behavior question in a trench coat, and each one is already on the wall.

Now, before this turns into a funeral: look around. Virus scanners exist. Dead-code warnings exist. Autograders graded your Project 2. The wall didn't kill the tools — it killed the word perfect, and real tools shrugged and kept shipping, because they were never built on full warranties in the first place. They live on the fine print, and on something even humbler: the patience slider.

Run the production line yourself. Pick a target question and a test case, then step the order through the pipeline: watch the translator wire up the wrapper, watch the wrapper's fate get decided by the envelope, let the pretend solver answer, and watch the verdict flow home. Do all three targets, both cases each — six runs. By the third run you'll be narrating the steps before clicking them, which is the point.

You're the clerk now. Twelve question cards hit your desk, one at a time. For each, decide: is it answerable with a full warranty — a paper question you can settle by looking, or a bounded run you can settle by running — or is it a genuine behavior question that gets the stamp? Fair warning: several cards are dressed to fool you, in both directions. The feedback is instant and each reason is one sentence; a wrong sort here is the cheapest tuition you'll pay all semester.

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

Two weeks ago you owned one machine. Last week, one impossibility. Tonight, an infinite supply of both. Spend some of it:

Coming up

Notes 13 — time complexity, P, and NP. And with it, the great turn of the whole course. For eleven weeks we've asked one question: can this be done at all? We built the shelves, found the walls, stamped the impossible. Next week the question changes costume and becomes the one your laptop actually cares about: can it be done before the sun burns out? Because here's the uncomfortable discovery waiting there — a job can carry a full warranty, decidable, provably doable… and still need more steps than there are atoms in the universe. Possible is not the same as practical, and the gap between those two words contains the most famous unsolved question in computer science. Bring your patience slider. It's about to become the main character.

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