Finite tape simulation of a RAM division instruction
ProvedLax759944Proofs.RamToTM.finite_div_instructionalgorithmscomputational-complexity
Fix a finite RAM program, an instruction-argument bound, a word width , and a normalized sparse memory. Suppose the fetched instruction is division by an operand with value . Assume the accumulator is below . The finite local tape interpreter executes this instruction and returns to the next fetch boundary with accumulator
The dispatch-state projection is preserved, the other encoded RAM fields are unchanged, and the number of actual local transitions is at most .
This instruction theorem is reusable in finite simulation of any RAM program. Natural division includes its zero-divisor convention.
Preamble
import Definitions.Def_EdgeSublinearMWIS_Main_NativeSchemeInterfaces
Formal statement
theorem Lax759944Proofs.RamToTM.finite_div_instruction : ∀ {p : Lax759944Proofs.Microcode.Program} {N pc w : ℕ} (hbound : Lax759944Proofs.RamToTM.programArgumentBound p ≤ N)
(o : Lax759944Proofs.Microcode.Op),
p[pc]? = Option.some (Lax759944Proofs.Microcode.Instr.div o) →
∀ (s : Lax759944Proofs.RamToTM.SparseState),
s.acc < 2 ^ w →
Lax759944Proofs.RamToTM.SparseMemory.Normalized w s.mem →
∀ (state : Lax759944Proofs.RamToTM.FullInterpreterState N),
∃ steps ≤ Lax759944Proofs.RamToTM.divideInstructionTotalBound w s.mem + 3,
∃ finalState,
Lax759944Proofs.RamToTM.FullInterpreterState.dispatchLens.get finalState =
Lax759944Proofs.RamToTM.FullInterpreterState.dispatchLens.get state ∧
(fun x =>
x.bind
(Turing.TM2.step (Lax759944Proofs.RamToTM.finiteInterpreterProgram p N hbound)))^[steps]
(Option.some
(Lax759944Proofs.RamToTM.finiteInterpreterCfg
(Lax759944Proofs.RamToTM.FiniteInterpreterLabel.fetch (Lax759944Proofs.RamToTM.boundPC p pc))
state (Lax759944Proofs.RamToTM.coreStacks w s))) =
Option.some
(Lax759944Proofs.RamToTM.finiteInterpreterCfg
(Lax759944Proofs.RamToTM.FiniteInterpreterLabel.fetch
(Lax759944Proofs.RamToTM.nextPC p (Lax759944Proofs.RamToTM.boundPC p pc)))
finalState
(Lax759944Proofs.RamToTM.coreStacks w
{ pc := s.pc, acc := s.acc / Lax759944Proofs.RamToTM.sparseValue w o s.mem % 2 ^ w,
mem := s.mem, inp := s.inp, out := s.out })) := by sorrySource