Bounded resources — decide within a horizon

Parent: relaxing-undecidability

Undecidability lives in the limit. Cap the resource and it evaporates.

Bounded halting

"Does M halt on x within t steps?" is decidable — just simulate t steps. Likewise "is there a certificate of degree ≤ d?" is a finite search.

So every practical convergence question with a horizon — "reach the ε-ball within T steps", "stabilize within budget" — is decidable. The undecidable version is only the t,T,d → ∞ idealization.

The catch: the honest bound can be uncomputable. The busy-beaver function BB(n) (max steps an n-state machine runs before halting) grows faster than any computable function. So "if it hasn't halted by step t, it never will" needs a t you often cannot compute. Bounding buys decidability, but the safe horizon may be astronomically — even uncomputably — large.

Control tie: finite-horizon / practical stability ("enters and stays in the ε-ball over [0,T]") is the decidable surrogate engineers actually use — and, like everywhere here, it trades the asymptotic truth for a checkable one. Same trade as bounding the SOS certificate degree.