Why is running a job and waiting to see whether it stops not a decision procedure?
answer
- two different promises, not one
- yes arrives, no never does
- recognizable versus decidable
- no computable step budget exists
- dovetailing still yields no negatives
basics
~10 sSimulation confirms only the yes case: every job that stops is eventually observed stopping, but a job still running is indistinguishable from one that never stops. Halting is therefore recognizable, not decidable.
solid answer
~40 sA **decider** must always terminate with the correct answer. Simulating the job gives you something weaker, a **recognizer**: if it stops you find out, eventually; if it never stops, the simulation never stops either and no answer is produced. The asymmetry is that a yes is confirmed by an event, while a no would need the permanent absence of an event, which no finite observation establishes. You cannot patch it with a cut-off, because no computable function turns a job's size into a step budget by which every stopping job of that size has already stopped. Even dovetailing - running every job under a growing step budget - still reports only the ones that stop.
go deeper
Remember that watching a job run only ever confirms that it finished. Still running tells you nothing, so waiting is not an answer however long you wait.
Define decider versus recognizer precisely and explain the asymmetry: a yes is witnessed by an event in finite time, a no would need the permanent absence of one. Say why no computable cut-off repairs it.
Turn it into wording and telemetry discipline: report budget exceeded rather than infinite loop, separate slow from stuck with progress signals, and treat repeated-state observations as evidence rather than proof.
Own the budget as a business trade-off. Since no principled cut-off exists, set it per job class against the cost of wasted capacity versus falsely failed work, and make the retry policy explicit.
## Two different promises A **decider** for a yes/no question always halts and always gives the right answer. A **recognizer**, also called a semi-decision procedure, promises less: on inputs whose answer is yes it eventually halts and says yes, and on inputs whose answer is no it may run forever, saying nothing. Confusing the two is the most common way this material is misremembered. | | Says yes when the answer is yes | Says no when the answer is no | Always terminates | |---|---|---|---| | Decider | yes | yes | yes | | Recognizer | eventually | never required to | no | The halting question is recognizable and not decidable, and that gap is the whole content of this question. ## What simulation actually gives you Stepping the job faithfully and watching is a perfect recognizer of halting: - If the job stops after k steps, the simulation stops after roughly k steps of its own and reports yes. Every stopping job is confirmed, with no exceptions and no cleverness required. - If the job never stops, the simulation never stops. It produces no answer at all - not a wrong answer, not a no, nothing. So the watching procedure is sound and complete on the yes side and silent on the no side. What it never does is **terminate on every input**, which is exactly the property a decision procedure must have. ## The missing half The asymmetry has a simple cause. A yes is witnessed by an **event**: the run finished, and that event is observable in finite time. A no would have to be witnessed by the **permanent absence** of an event, and no finite stretch of observation establishes permanence. "Still running after ten million steps" is equally consistent with "will stop at step ten million and one" and with "will never stop". The obvious repair is a cut-off rule: if it has not stopped by step N, answer no. For that to be a decision procedure, N must depend computably on the job and be large enough, and no such function exists. There is no computable bound on how long a stopping program of a given size may run before it stops. Any fixed or computed cut-off therefore misclassifies some job that was about to finish. ## Dovetailing: recognizing the whole set at once There is a stronger-looking trick that still buys no decision. Instead of running one job to completion, interleave all of them: 1. For budget b = 1, 2, 3, and so on; 2. run each of the first b jobs for b steps on its input; 3. report every job that stopped within its budget. Every job that halts is reported at some finite stage, because the stage where b exceeds both its index and its running time eventually arrives. This **dovetailing** converts "run them one at a time and get stuck on the first bad one" into "make progress on all of them at once" - and still yields no negative answers. Nothing is ever ruled out. That is the sharpest demonstration that better scheduling is not the missing ingredient. ## Why it matters for a watchdog The practical consequence is how you word the result. A build watchdog that kills a job at a budget has performed a resource action, not a classification: - Report "exceeded the ten-minute budget", never "infinite loop detected". The first is true; the second is not established. - Distinguish **slow** from **stuck** in your telemetry. Progress counters, output since the last checkpoint, and repeated observed state are heuristic evidence of being stuck. Useful evidence, not proof. - Decide the policy explicitly - retry with a larger budget, fail, or quarantine - because with the verdict unavailable the policy is the only real decision being made. - Keep the budget configurable per job class. Since no principled budget exists, the number is a business trade-off between wasted machine time and falsely failed work. ## The vocabulary trap Three words get swapped for one another under pressure, and interviewers listen for it. **Decidable** means a procedure always terminates with the right answer. **Recognizable** means yes-instances are eventually confirmed and no-instances may hang. **Undecidable** means no decider exists, which leaves open whether the problem is recognizable - halting is. A related slip is calling one particular job undecidable. Undecidability is a property of a problem, that is, of the whole set of instances. A single job either stops or it does not; there is nothing undecidable about that job.
- Why does adding a generous cut-off not turn the recognizer into a decider?Because the cut-off has to be right for every job, and no computable function maps a job's size to a step count by which all stopping jobs of that size have stopped. Programs of modest size can run enormously long and then finish, so any budget you can actually compute misclassifies some of them as non-terminating.
- What does dovetailing achieve, if it still produces no negative answers?It recognizes the halting set uniformly: by raising a shared step budget and running more jobs under it each round, every job that stops is eventually reported, without getting permanently blocked on one that does not. It removes the scheduling obstacle while leaving the logical one untouched.
- Is a problem where the no-instances are eventually confirmed also called recognizable?That is the mirror property, usually called co-recognizable: a recognizer exists for the complement. A problem with both is decidable, since you can run the two recognizers together and one must answer. Halting has the first and, as a consequence, not the second.
saying these in an interview costs you the question
- Says running it and waiting decides halting, given enough patience.
- Thinks silence after a long wait proves the job never stops.
- Believes a sufficient step budget can be computed from program size.
- Uses undecidable and unrecognizable as interchangeable words.
- Calls one specific job undecidable rather than the problem.