pith. machine review for the scientific record. sign in
theorem proved term proof

tm_simulation_bound

show as:
view Lean formalization →

No prose has been written for this declaration yet. The Lean source and graph data below render without it.

generate prose now

formal statement (Lean)

 208theorem tm_simulation_bound (sim : TMSimulator) :
 209    tm_simulation_time sim = sim.ca_steps * sim.tape_size := by

proof body

Term-mode proof.

 210  simp only [tm_simulation_time, TMSimulator.time_per_step]
 211
 212/-- **HYPOTHESIS**: Turing Machine simulation of SAT evaluation via CA.
 213
 214    STATUS: SCAFFOLD — The total Turing time for SAT evaluation via CA is
 215    predicted to be O(n^{4/3} log n), but this depends on the CA runtime bound.
 216
 217    TODO: Formally prove the simulation time bound. -/

depends on (15)

Lean names referenced from this declaration's body.