skip to content

A colleague proposes a checker that decides whether any submitted job ever writes output; how would you show it is impossible?

level: seniorimportance: should knowfreq 36%

answer

  1. do not attack the implementation
  2. borrow the impossibility from halting
  3. a build step, not a simulation
  4. known-impossible problem is the source
  5. write reachable only after the return

basics

~20 s

Map any halting question into the proposed check: transform a program and input into a job that simulates them and only then writes one byte. That job writes exactly when the original halts, so the checker would decide halting - impossible.

solid answer

~40 s

Do not attack the proposed checker's implementation; show it would be too powerful. Given an arbitrary program `P` and input `x`, mechanically build a new job `P'` whose body is: simulate `P` on `x`, then write one byte, then stop. The build step is a text transformation and always finishes. Now `P'` writes output **exactly when** `P` halts on `x`: if the simulation returns, control reaches the write; if it never returns, the write is never reached. So a total, always-correct `EVER_WRITES` composed with the build would answer the halting question for every pair - which nothing can do. Therefore the proposed checker cannot exist as specified, and the honest deliverable is a conservative one that may answer `unknown`.

code

pseudocode · 14 lines
pseudocode
# BUILD is a text transformation: it always finishes, it runs nothing
function BUILD(P, x):
    return text of job P_PRIME:
        simulate P on x          # may never return
        write one byte to output # reached only if the simulation returned
        stop

# if EVER_WRITES were total and always correct, then:
function HALTS(P, x):
    return EVER_WRITES(BUILD(P, x))

# P halts on x     -> simulation returns -> byte written  -> true
# P never halts    -> simulation hangs   -> never written -> false
# so HALTS would decide halting, which nothing can

go deeper

for a junior

Know that impossibility for a new analysis question is shown by borrowing it from the halting problem rather than by examining the proposed tool. Recognising the move is enough here.

for a middle

Build the mapping yourself: a terminating text transformation whose output exhibits the behaviour exactly when the original program halts, and check that yes maps to yes and no maps to no.

for a senior

Deliver it as a design conversation: state precisely which capability is impossible, show the construction briefly, and put a sound three-valued checker or a restricted job language on the table as the buildable alternative.

for a principal

Treat it as a platform boundary. Deciding what submitted jobs may express determines which guarantees you can ever offer, so the durable choice is restriction versus approximation, not a better analyser.

## The shape of the argument You are not going to find a bug in your colleague's design. The argument is indirect: show that the proposed capability, if it existed, would hand you something already known to be impossible. Concretely, you build a **transformation** that converts any instance of the halting question into an instance of their question, preserving the yes/no answer, and the transformation itself must be an ordinary program that always finishes. That combination is what makes the conclusion bite. If their checker were total and always correct, then "transform, then ask their checker" would be a total, always-correct procedure for halting. ## Building the transformation Given an arbitrary program `P` and an input `x`: 1. Emit the **text** of a new job `P'`. This is a mechanical text construction - nothing is executed at build time, so this step always finishes quickly. 2. The body of `P'` is: simulate `P` on `x`; then write one byte to the output directory; then stop. 3. Hand `P'` to the proposed checker and return its answer as the answer about `P` on `x`. The only subtlety is ordering. The write must be **after** the simulation and on the path that the simulation returning leads to, so that reaching it is equivalent to the simulation having returned. ## Checking the mapping in both directions A reduction is only valid if it preserves yes **and** no. Walk both: - **`P` halts on `x`.** The simulation inside `P'` returns after finitely many steps, control reaches the write, and `P'` writes. So the checker's honest answer about `P'` is yes. - **`P` does not halt on `x`.** The simulation never returns, the write is never reached, and `P'` produces no output ever. The checker's honest answer is no. So "`P'` ever writes" and "`P` halts on `x`" are the same proposition. Skipping the second bullet is the classic sloppy version of this proof, and an interviewer will ask for it. ## What the argument does and does not claim - It refutes a **total, always-correct** checker over arbitrary submitted jobs. It does not refute useful output analysis. A checker that answers `definitely never writes`, `may write`, or `unknown` is perfectly buildable and often valuable. - It does not apply to restricted inputs. If submitted jobs are written in a language with no unbounded loops, the question becomes decidable, because the construction above cannot be expressed in that language. - It says nothing about any particular job. Most real jobs can be classified by inspection; the impossibility is about the procedure that must handle all of them. - The transformation itself must be computable and total. A "transformation" that simulates `P` while building `P'` would smuggle the non-termination into the build step and prove nothing. ## The error that ruins the proof The fatal mistake is running the mapping the wrong way round - taking instances of the new problem and encoding them as halting questions. That direction only shows the new problem is no harder than halting, which is consistent with the new problem being easy, so it establishes nothing about impossibility. The problem that is already known to be impossible has to sit on the **source** side: you must be able to answer *it* by asking *their* checker, not the other way round. A quick self-test before you present: finish the sentence "if their checker existed, I could now solve ...". If the blank is not the known-impossible problem, the argument is backwards. ## How to deliver it to a colleague The register matters as much as the proof, because you are refusing a feature request: 1. **State what is impossible, precisely.** A checker that always answers, is never wrong, and accepts arbitrary jobs. 2. **Show the one-paragraph construction.** Simulate, then write. Walk both directions in two sentences. 3. **Offer the buildable version.** Three-valued output, sound in one direction, with the `unknown` verdicts surfaced rather than folded silently into a pass. 4. **Offer the other lever.** Restrict what submitted jobs may express, and the question becomes answerable by construction. This is usually the more valuable half of the conversation, because it converts an impossibility into a platform design choice. The same pattern generalises to most "can we detect X about arbitrary submitted code" requests: look for a way to arrange that X happens exactly when some arbitrary program halts. If you can, the answer is no, and the discussion should move to approximation or restriction.

  • Why must the transformation itself always terminate?
    Because the composed procedure has to be a decider. If building the new job required simulating the original, the build could hang and the composition would no longer always answer - the impossibility would have been hidden in the transformation rather than exposed in the checker.
  • What would you actually offer your colleague instead?
    A conservative checker with three verdicts - definitely never writes, may write, unknown - sound in whichever direction the use case needs, with unknowns surfaced. Alternatively, restrict what submitted jobs may express: in a language without unbounded loops the question is decidable by construction.
  • Does the same construction work for checks other than writing output?
    For most observable behaviours, yes: append the behaviour after the simulation so it occurs exactly when the simulated program halts. The pattern fails only where the property cannot be made to depend on reaching that point, for instance a purely syntactic property of the job's text.

saying these in an interview costs you the question

  • Encodes the new problem as a halting question and calls it proved.
  • Tries to disprove the checker by auditing its proposed implementation.
  • Lets the build step simulate the program before emitting the job.
  • Checks only that halting maps to yes, never the no case.
  • Concludes no useful output analysis is possible at all.