§4 Prop. 3: computing costs at least infinitely often
ProvedBSS.floor_halting_time_lower_boundProposition 3 of §4 (p. 22). Suppose a machine over computes the greatest integer function on the positive reals. Then for an unbounded set of .
The paper's argument is topological: for each nonnegative integer there is an open set of inputs on which the machine outputs ; the time- halting set is covered by at most pieces on each of which is a rational map, hence constant when its values are integers; so at least pieces are needed to realize the values below , giving .
import Definitions.Def_BSSFeasibility
namespace BSS
theorem floor_halting_time_lower_bound (M : Machine ℝ)
(hM : ∀ x : ℝ, 0 < x → M.Halts (Finsupp.single 0 x) ∧
M.outputVal (Finsupp.single 0 x) = (⌊x⌋ : ℝ)) :
∀ L : ℝ, ∃ x : ℝ, L < x ∧
Real.logb 2 x ≤ (M.haltingTime (Finsupp.single 0 x) : ℝ) := by sorry
end BSS
Read-back
What the Lean code literally says, in plain math · NON-BLIND: written by the drafting agent (Aristotle, Harmonic), not an independent auditor
⚠️ NON-BLIND READ-BACK — NOT INDEPENDENT TESTIMONY. This read-back was not written by an independent blind auditor. It was written by the same agent that drafted this item's Lean statement, at the explicit instruction of the proposal owner. The author therefore already knew what the statement was intended to say, which is exactly the bias a read-back exists to exclude. Treat this text as the author's own rendering of their own code, not as corroborating evidence, and obtain a genuinely independent audit before relying on it.
Let be a machine over , and write for the point whose coordinate is and whose other coordinates are .
Hypothesis. For every real : halts on the input , and its output value there — coordinate of the part of the halting state — equals the real number , the greatest integer not exceeding . Nothing is assumed about on inputs that are not of the form with , and in particular nothing at .
Conclusion. For every real there exists a real with and
where is the halting time of on , cast from a natural number to a real, and is the base- logarithm.
The inequality is non-strict and is in the direction . The quantifier ranges over all reals, including negative ones, and is only required to exceed , so the conclusion is that the set of witnessing the bound is unbounded above. Note for and, by the convention that of a nonpositive number is , also for ; the force of the statement is therefore entirely at large , where the hypothesis does apply.