Tensions in Practice: Eventual positive answers in tension with bounded work¶
A schematic program-halting question
To test whether a supplied program ever stops, simulate it. If it stops, there is a definite yes. If it keeps running, more simulation may eventually find a stop—or may continue forever. Imposing a time or step limit bounds the work, but the limit produces “unknown,” not proof that the program will never halt. A stopping policy for the investigation is different from a negative answer to its question.
Find every eventual positive
Keep simulating until a halting program supplies its witness.
Bound the investigation
Stop spending resources after a declared finite budget.
Why these aims pull against each other
An unbounded simulation preserves eventual positive discovery but may never finish. A finite budget terminates the investigation by accepting an unresolved result.
Choose an arrangement to see what changes and what remains difficult.
Arrows express the declared relations, not measured effect sizes. Examples and quantities are illustrative.
What this choice protects
What it costs
When it fits
Compare the arrangements
Keep looking for a halt
Simulate each next step until the supplied program stops.
- What it protects
- Any program that eventually halts is eventually recognized.
- What it costs
- A non-halting program consumes unbounded waiting and work under this policy.
- When it fits
- One-sided positive discovery is sufficient and an indefinite investigation is tolerable.
Illustration note: The simulation is a conceptual procedure, not execution of arbitrary code or a complete halting decider.
Stop with unknown at the limit
Simulate only until the program halts or the declared budget expires.
- What it protects
- The investigation has a finite stopping rule.
- What it costs
- A program that would halt later can remain unresolved.
- When it fits
- Resource control is needed and callers can handle an unknown outcome honestly.
Illustration note: The bounded question “halted within this run” is decidable, but differs from eventual halting.
What this illustration does—and does not—establish
The source supplies the stated tension; the selected arrangements are bounded editorial illustrations. Costs and conditions remain part of the comparison.
- A particular program may have a separate proof of non-halting; this simulator does not supply one merely by waiting.
- This does not say all unanswered questions are undecidable or that a difficult instance proves its whole class undecidable.
- No specific runtime limit, machine performance or operational execution policy is recommended.
Source entries
Decidability Computability
This source passage supplies the contextual tension. The concrete arrangements and schematic examples are editorial illustrations, not measured findings.
Full Decidability versus the Semi-Decidable Middle (sign/direction)
T5 — Full Decidability versus the Semi-Decidable Middle (sign/direction). Between decidable and undecidable sits semi-decidability: a procedure that halts with "yes" whenever the answer is yes but may loop forever otherwise.
The source operation
A class of yes/no questions is *decidable* when there exists a finite, mechanical procedure that, applied to any instance, always terminates and returns the correct answer.