Charged macro loops and scaled ceiling semantics
ProvedDecrAlmostLinearSSSP.Decremental.Certificates.normal_laws_1Let a source program be a fixed finite deterministic scalar RAM program. Host states contain natural and real registers and memory; scaled instances, cached observations, advancing pointers and dirty queues are the objects defined by the wrapper interface.
Structured bounded loops have finite evaluations with the stated exact or upper instruction costs. Native ceiling routines realize rounded nonnegative real quantities using charged arithmetic, comparisons and doubling. Source-memory write observations identify every changed public entry and preserve unmodified entries.
For every parameter tuple and state satisfying the explicit source-execution and representation hypotheses, all component contracts hold simultaneously:
Here the component assertions are the execution, exact memory-image, preservation, observation and charged-cost contracts described above, each with its own universal quantifiers. They are used to verify the arbitrary-weight scaling reduction for and .
Formalization Note The collection uses a balanced conjunction so its component contracts can be reused through short projections. It does not supply correctness or termination as a hypothesis on the external graph input.
import Definitions.Def_DecrAlmostLinearSSSP_RAMFoundation set_option autoImplicit false set_option maxRecDepth 10000 set_option maxHeartbeats 2000000 open scoped ENNReal NNReal attribute [local instance] Classical.propDecidable
theorem DecrAlmostLinearSSSP.Decremental.Certificates.normal_laws_1 : (((((((∀ (test : DecrAlmostLinearSSSP.Decremental.Structured.Test) (body : DecrAlmostLinearSSSP.Decremental.Structured.Cmd)
(invariant : DecrAlmostLinearSSSP.Decremental.Structured.Data → Prop)
(rank : DecrAlmostLinearSSSP.Decremental.Structured.Data → Nat) (B : Nat),
(∀ (s : DecrAlmostLinearSSSP.Decremental.Structured.Data),
invariant s →
test.holds s →
∃ t cost,
And (DecrAlmostLinearSSSP.Decremental.Structured.Eval body s cost t)
(And (invariant t)
(And (@LT.lt.{0} Nat instLTNat (rank t) (rank s)) (@LE.le.{0} Nat instLENat cost B)))) →
∀ (s : DecrAlmostLinearSSSP.Decremental.Structured.Data),
invariant s →
∃ t cost,
And
(DecrAlmostLinearSSSP.Decremental.Structured.Eval
(DecrAlmostLinearSSSP.Decremental.Structured.Cmd.loop test body) s cost t)
(And (invariant t)
(@LE.le.{0} Nat instLENat cost
(@HAdd.hAdd.{0, 0, 0} Nat Nat Nat (@instHAdd.{0} Nat instAddNat)
(@HMul.hMul.{0, 0, 0} Nat Nat Nat (@instHMul.{0} Nat instMulNat)
(@HAdd.hAdd.{0, 0, 0} Nat Nat Nat (@instHAdd.{0} Nat instAddNat) B
(@OfNat.ofNat.{0} Nat (nat_lit 2) (instOfNatNat (nat_lit 2))))
(rank s))
(@OfNat.ofNat.{0} Nat (nat_lit 2) (instOfNatNat (nat_lit 2))))))) ∧ (∀ (test : DecrAlmostLinearSSSP.Decremental.Structured.Test) (body : DecrAlmostLinearSSSP.Decremental.Structured.Cmd)
(invariant : DecrAlmostLinearSSSP.Decremental.Structured.Data → Prop)
(rank budget : DecrAlmostLinearSSSP.Decremental.Structured.Data → Nat),
(∀ (s : DecrAlmostLinearSSSP.Decremental.Structured.Data),
invariant s →
test.holds s →
∃ t cost,
And (DecrAlmostLinearSSSP.Decremental.Structured.Eval body s cost t)
(And (invariant t)
(And (@LT.lt.{0} Nat instLTNat (rank t) (rank s))
(@LE.le.{0} Nat instLENat
(@HAdd.hAdd.{0, 0, 0} Nat Nat Nat (@instHAdd.{0} Nat instAddNat)
(@HAdd.hAdd.{0, 0, 0} Nat Nat Nat (@instHAdd.{0} Nat instAddNat) cost
(@OfNat.ofNat.{0} Nat (nat_lit 2) (instOfNatNat (nat_lit 2))))
(budget t))
(budget s))))) →
∀ (s : DecrAlmostLinearSSSP.Decremental.Structured.Data),
invariant s →
∃ t cost,
And
(DecrAlmostLinearSSSP.Decremental.Structured.Eval
(DecrAlmostLinearSSSP.Decremental.Structured.Cmd.loop test body) s cost t)
(And (invariant t)
(@LE.le.{0} Nat instLENat
(@HAdd.hAdd.{0, 0, 0} Nat Nat Nat (@instHAdd.{0} Nat instAddNat) cost (budget t))
(@HAdd.hAdd.{0, 0, 0} Nat Nat Nat (@instHAdd.{0} Nat instAddNat) (budget s)
(@OfNat.ofNat.{0} Nat (nat_lit 2) (instOfNatNat (nat_lit 2)))))))) ∧ ((∀ (test : DecrAlmostLinearSSSP.Decremental.Structured.Test) (body : DecrAlmostLinearSSSP.Decremental.Structured.Cmd)
(cost : Nat) (s t : DecrAlmostLinearSSSP.Decremental.Structured.Data),
DecrAlmostLinearSSSP.Decremental.Structured.Eval (DecrAlmostLinearSSSP.Decremental.Structured.Cmd.loop test body) s
cost t →
Not (test.holds t)) ∧ (∀ (s : DecrAlmostLinearSSSP.Decremental.Structured.Data),
DecrAlmostLinearSSSP.Decremental.Structured.Eval
(DecrAlmostLinearSSSP.Decremental.Structured.sequence
(@List.map.{0, 0} DecrAlmostLinearSSSP.Decremental.Structured.Atom DecrAlmostLinearSSSP.Decremental.Structured.Cmd
DecrAlmostLinearSSSP.Decremental.Structured.Cmd.atom DecrAlmostLinearSSSP.Decremental.ScaledCeiling.initAtoms))
s (@OfNat.ofNat.{0} Nat (nat_lit 8) (instOfNatNat (nat_lit 8)))
(DecrAlmostLinearSSSP.Decremental.ScaledCeiling.initial s)))) ∧ (((∀ (s : DecrAlmostLinearSSSP.Decremental.Structured.Data),
DecrAlmostLinearSSSP.Decremental.Structured.Eval DecrAlmostLinearSSSP.Decremental.ScaledCeiling.buildBody s
(@OfNat.ofNat.{0} Nat (nat_lit 5) (instOfNatNat (nat_lit 5)))
(DecrAlmostLinearSSSP.Decremental.ScaledCeiling.buildStep s)) ∧ (∀ (s : DecrAlmostLinearSSSP.Decremental.Structured.Data),
DecrAlmostLinearSSSP.Decremental.Structured.Eval DecrAlmostLinearSSSP.Decremental.ScaledCeiling.chooseBody s
(@OfNat.ofNat.{0} Nat (nat_lit 2) (instOfNatNat (nat_lit 2)))
(DecrAlmostLinearSSSP.Decremental.ScaledCeiling.chooseStep s))) ∧ ((∀ (s : DecrAlmostLinearSSSP.Decremental.Structured.Data),
∃ cost,
And (@LE.le.{0} Nat instLENat cost (@OfNat.ofNat.{0} Nat (nat_lit 7) (instOfNatNat (nat_lit 7))))
(DecrAlmostLinearSSSP.Decremental.Structured.Eval DecrAlmostLinearSSSP.Decremental.ScaledCeiling.greedyBody s cost
(DecrAlmostLinearSSSP.Decremental.ScaledCeiling.greedyStep s))) ∧ ((∀ (s : DecrAlmostLinearSSSP.Decremental.Structured.Data) (N : Nat),
DecrAlmostLinearSSSP.Decremental.ScaledCeiling.BuildInvariant
(s.natReg (@OfNat.ofNat.{0} Nat (nat_lit 0) (instOfNatNat (nat_lit 0))))
(s.realReg (@OfNat.ofNat.{0} Nat (nat_lit 0) (instOfNatNat (nat_lit 0)))) N
(DecrAlmostLinearSSSP.Decremental.ScaledCeiling.initial s)) ∧ (∀ (s : DecrAlmostLinearSSSP.Decremental.Structured.Data),
And
(@Eq.{1} Nat
((DecrAlmostLinearSSSP.Decremental.ScaledCeiling.buildStep s).natReg
(@OfNat.ofNat.{0} Nat (nat_lit 1) (instOfNatNat (nat_lit 1))))
(@HAdd.hAdd.{0, 0, 0} Nat Nat Nat (@instHAdd.{0} Nat instAddNat)
(s.natReg (@OfNat.ofNat.{0} Nat (nat_lit 1) (instOfNatNat (nat_lit 1))))
(s.natReg (@OfNat.ofNat.{0} Nat (nat_lit 4) (instOfNatNat (nat_lit 4))))))
(And
(@Eq.{1} Real
((DecrAlmostLinearSSSP.Decremental.ScaledCeiling.buildStep s).realReg
(@OfNat.ofNat.{0} Nat (nat_lit 1) (instOfNatNat (nat_lit 1))))
(@HAdd.hAdd.{0, 0, 0} Real Real Real (@instHAdd.{0} Real Real.instAdd)
(s.realReg (@OfNat.ofNat.{0} Nat (nat_lit 1) (instOfNatNat (nat_lit 1))))
(s.realReg (@OfNat.ofNat.{0} Nat (nat_lit 1) (instOfNatNat (nat_lit 1))))))
(And
(@Eq.{1} Nat
((DecrAlmostLinearSSSP.Decremental.ScaledCeiling.buildStep s).natReg
(@OfNat.ofNat.{0} Nat (nat_lit 2) (instOfNatNat (nat_lit 2))))
(@HAdd.hAdd.{0, 0, 0} Nat Nat Nat (@instHAdd.{0} Nat instAddNat)
(s.natReg (@OfNat.ofNat.{0} Nat (nat_lit 2) (instOfNatNat (nat_lit 2))))
(s.natReg (@OfNat.ofNat.{0} Nat (nat_lit 2) (instOfNatNat (nat_lit 2))))))
(And
(@Eq.{1} Real
((DecrAlmostLinearSSSP.Decremental.ScaledCeiling.buildStep s).realReg
(@OfNat.ofNat.{0} Nat (nat_lit 2) (instOfNatNat (nat_lit 2))))
(s.realReg (@OfNat.ofNat.{0} Nat (nat_lit 2) (instOfNatNat (nat_lit 2)))))
(And
(@Eq.{1} Nat
((DecrAlmostLinearSSSP.Decremental.ScaledCeiling.buildStep s).natReg
(@OfNat.ofNat.{0} Nat (nat_lit 3) (instOfNatNat (nat_lit 3))))
(s.natReg (@OfNat.ofNat.{0} Nat (nat_lit 3) (instOfNatNat (nat_lit 3)))))
(And
(@Eq.{1} (Nat → Real) (DecrAlmostLinearSSSP.Decremental.ScaledCeiling.buildStep s).realMem
(@Function.update.{1, 1} Nat (fun a => Real) instDecidableEqNat s.realMem
(s.natReg (@OfNat.ofNat.{0} Nat (nat_lit 1) (instOfNatNat (nat_lit 1))))
(s.realReg (@OfNat.ofNat.{0} Nat (nat_lit 1) (instOfNatNat (nat_lit 1))))))
(@Eq.{1} (Nat → Nat) (DecrAlmostLinearSSSP.Decremental.ScaledCeiling.buildStep s).natMem
(@Function.update.{1, 1} Nat (fun a => Nat) instDecidableEqNat s.natMem
(s.natReg (@OfNat.ofNat.{0} Nat (nat_lit 1) (instOfNatNat (nat_lit 1))))
(s.natReg (@OfNat.ofNat.{0} Nat (nat_lit 2) (instOfNatNat (nat_lit 2)))))))))))))))) ∧ ((((∀ {P : Nat} {x : Real} {s : DecrAlmostLinearSSSP.Decremental.Structured.Data},
DecrAlmostLinearSSSP.Decremental.ScaledCeiling.Constants P x s →
DecrAlmostLinearSSSP.Decremental.ScaledCeiling.Constants P x
(DecrAlmostLinearSSSP.Decremental.ScaledCeiling.buildStep s)) ∧ (∀ {P N : Nat} {x : Real} {s : DecrAlmostLinearSSSP.Decremental.Structured.Data},
DecrAlmostLinearSSSP.Decremental.ScaledCeiling.BuildInvariant P x N s →
@LE.le.{0} Real Real.instLE x
(@HPow.hPow.{0, 0, 0} Real Nat Real
(@instHPow.{0, 0} Real Nat (@NPow.toPow.{0} Real (@Monoid.toNPow.{0} Real Real.instMonoid)))
(@OfNat.ofNat.{0} Real (nat_lit 2)
(@instOfNatAtLeastTwo.{0} Real (nat_lit 2) Real.instNatCast
(@Nat.instAtLeastTwoHAddOfNat (@OfNat.ofNat.{0} Nat (nat_lit 1) (instOfNatNat (nat_lit 1)))
(@Nat.instNeZeroSucc (@OfNat.ofNat.{0} Nat (nat_lit 0) (instOfNatNat (nat_lit 0)))))))
N) →
DecrAlmostLinearSSSP.Decremental.ScaledCeiling.buildTest.holds s →
And
(DecrAlmostLinearSSSP.Decremental.ScaledCeiling.BuildInvariant P x N
(DecrAlmostLinearSSSP.Decremental.ScaledCeiling.buildStep s))
(@LT.lt.{0} Nat instLTNat
(@HSub.hSub.{0, 0, 0} Nat Nat Nat (@instHSub.{0} Nat instSubNat) N
((DecrAlmostLinearSSSP.Decremental.ScaledCeiling.buildStep s).natReg
(@OfNat.ofNat.{0} Nat (nat_lit 1) (instOfNatNat (nat_lit 1)))))
(@HSub.hSub.{0, 0, 0} Nat Nat Nat (@instHSub.{0} Nat instSubNat) N
(s.natReg (@OfNat.ofNat.{0} Nat (nat_lit 1) (instOfNatNat (nat_lit 1)))))))) ∧ ((∀ {P N : Nat} {x : Real} {s : DecrAlmostLinearSSSP.Decremental.Structured.Data},
DecrAlmostLinearSSSP.Decremental.ScaledCeiling.BuildInvariant P x N s →
@LE.le.{0} Real Real.instLE x
(@HPow.hPow.{0, 0, 0} Real Nat Real
(@instHPow.{0, 0} Real Nat (@NPow.toPow.{0} Real (@Monoid.toNPow.{0} Real Real.instMonoid)))
(@OfNat.ofNat.{0} Real (nat_lit 2)
(@instOfNatAtLeastTwo.{0} Real (nat_lit 2) Real.instNatCast
(@Nat.instAtLeastTwoHAddOfNat (@OfNat.ofNat.{0} Nat (nat_lit 1) (instOfNatNat (nat_lit 1)))
(@Nat.instNeZeroSucc (@OfNat.ofNat.{0} Nat (nat_lit 0) (instOfNatNat (nat_lit 0)))))))
N) →
∃ t cost,
And
(DecrAlmostLinearSSSP.Decremental.Structured.Eval DecrAlmostLinearSSSP.Decremental.ScaledCeiling.buildLoop s
cost t)
(And (DecrAlmostLinearSSSP.Decremental.ScaledCeiling.BuildInvariant P x N t)
(And (Not (DecrAlmostLinearSSSP.Decremental.ScaledCeiling.buildTest.holds t))
(@LE.le.{0} Nat instLENat cost
(@HAdd.hAdd.{0, 0, 0} Nat Nat Nat (@instHAdd.{0} Nat instAddNat)
(@HMul.hMul.{0, 0, 0} Nat Nat Nat (@instHMul.{0} Nat instMulNat)
(@OfNat.ofNat.{0} Nat (nat_lit 7) (instOfNatNat (nat_lit 7)))
(@HSub.hSub.{0, 0, 0} Nat Nat Nat (@instHSub.{0} Nat instSubNat) N
(s.natReg (@OfNat.ofNat.{0} Nat (nat_lit 1) (instOfNatNat (nat_lit 1))))))
(@OfNat.ofNat.{0} Nat (nat_lit 2) (instOfNatNat (nat_lit 2)))))))) ∧ (∀ (s : DecrAlmostLinearSSSP.Decremental.Structured.Data),
And
(@Eq.{1} Nat
((DecrAlmostLinearSSSP.Decremental.ScaledCeiling.greedyPrefix s).natReg
(@OfNat.ofNat.{0} Nat (nat_lit 1) (instOfNatNat (nat_lit 1))))
(@HSub.hSub.{0, 0, 0} Nat Nat Nat (@instHSub.{0} Nat instSubNat)
(s.natReg (@OfNat.ofNat.{0} Nat (nat_lit 1) (instOfNatNat (nat_lit 1))))
(s.natReg (@OfNat.ofNat.{0} Nat (nat_lit 4) (instOfNatNat (nat_lit 4))))))
(And
(@Eq.{1} Real
((DecrAlmostLinearSSSP.Decremental.ScaledCeiling.greedyPrefix s).realReg
(@OfNat.ofNat.{0} Nat (nat_lit 2) (instOfNatNat (nat_lit 2))))
(s.realReg (@OfNat.ofNat.{0} Nat (nat_lit 2) (instOfNatNat (nat_lit 2)))))
(And
(@Eq.{1} Real
((DecrAlmostLinearSSSP.Decremental.ScaledCeiling.greedyPrefix s).realReg
(@OfNat.ofNat.{0} Nat (nat_lit 4) (instOfNatNat (nat_lit 4))))
(@HAdd.hAdd.{0, 0, 0} Real Real Real (@instHAdd.{0} Real Real.instAdd)
(s.realReg (@OfNat.ofNat.{0} Nat (nat_lit 2) (instOfNatNat (nat_lit 2))))
(s.realMem
(@HSub.hSub.{0, 0, 0} Nat Nat Nat (@instHSub.{0} Nat instSubNat)
(s.natReg (@OfNat.ofNat.{0} Nat (nat_lit 1) (instOfNatNat (nat_lit 1))))
(s.natReg (@OfNat.ofNat.{0} Nat (nat_lit 4) (instOfNatNat (nat_lit 4))))))))
(And
(@Eq.{1} Nat
((DecrAlmostLinearSSSP.Decremental.ScaledCeiling.greedyPrefix s).natReg
(@OfNat.ofNat.{0} Nat (nat_lit 3) (instOfNatNat (nat_lit 3))))
(s.natReg (@OfNat.ofNat.{0} Nat (nat_lit 3) (instOfNatNat (nat_lit 3)))))
(And
(@Eq.{1} Nat
((DecrAlmostLinearSSSP.Decremental.ScaledCeiling.greedyPrefix s).natReg
(@OfNat.ofNat.{0} Nat (nat_lit 6) (instOfNatNat (nat_lit 6))))
(s.natMem
(@HSub.hSub.{0, 0, 0} Nat Nat Nat (@instHSub.{0} Nat instSubNat)
(s.natReg (@OfNat.ofNat.{0} Nat (nat_lit 1) (instOfNatNat (nat_lit 1))))
(s.natReg (@OfNat.ofNat.{0} Nat (nat_lit 4) (instOfNatNat (nat_lit 4)))))))
(And
(@Eq.{1} (Nat → Real) (DecrAlmostLinearSSSP.Decremental.ScaledCeiling.greedyPrefix s).realMem s.realMem)
(@Eq.{1} (Nat → Nat) (DecrAlmostLinearSSSP.Decremental.ScaledCeiling.greedyPrefix s).natMem s.natMem))))))))) ∧ (((∀ {P : Nat} {x : Real} {s : DecrAlmostLinearSSSP.Decremental.Structured.Data},
DecrAlmostLinearSSSP.Decremental.ScaledCeiling.Constants P x s →
DecrAlmostLinearSSSP.Decremental.ScaledCeiling.Constants P x
(DecrAlmostLinearSSSP.Decremental.ScaledCeiling.greedyPrefix s)) ∧ (∀ {P : Nat} {x : Real} {s : DecrAlmostLinearSSSP.Decremental.Structured.Data},
DecrAlmostLinearSSSP.Decremental.ScaledCeiling.Constants P x s →
DecrAlmostLinearSSSP.Decremental.ScaledCeiling.Constants P x
(DecrAlmostLinearSSSP.Decremental.ScaledCeiling.chooseStep s))) ∧ ((∀ (s : DecrAlmostLinearSSSP.Decremental.Structured.Data),
And
(@Eq.{1} Nat
((DecrAlmostLinearSSSP.Decremental.ScaledCeiling.chooseStep s).natReg
(@OfNat.ofNat.{0} Nat (nat_lit 1) (instOfNatNat (nat_lit 1))))
(s.natReg (@OfNat.ofNat.{0} Nat (nat_lit 1) (instOfNatNat (nat_lit 1)))))
(And
(@Eq.{1} Real
((DecrAlmostLinearSSSP.Decremental.ScaledCeiling.chooseStep s).realReg
(@OfNat.ofNat.{0} Nat (nat_lit 2) (instOfNatNat (nat_lit 2))))
(@HAdd.hAdd.{0, 0, 0} Real Real Real (@instHAdd.{0} Real Real.instAdd)
(s.realReg (@OfNat.ofNat.{0} Nat (nat_lit 4) (instOfNatNat (nat_lit 4))))
(s.realReg (@OfNat.ofNat.{0} Nat (nat_lit 5) (instOfNatNat (nat_lit 5))))))
(And
(@Eq.{1} Nat
((DecrAlmostLinearSSSP.Decremental.ScaledCeiling.chooseStep s).natReg
(@OfNat.ofNat.{0} Nat (nat_lit 3) (instOfNatNat (nat_lit 3))))
(@HAdd.hAdd.{0, 0, 0} Nat Nat Nat (@instHAdd.{0} Nat instAddNat)
(s.natReg (@OfNat.ofNat.{0} Nat (nat_lit 3) (instOfNatNat (nat_lit 3))))
(s.natReg (@OfNat.ofNat.{0} Nat (nat_lit 6) (instOfNatNat (nat_lit 6))))))
(And (@Eq.{1} (Nat → Real) (DecrAlmostLinearSSSP.Decremental.ScaledCeiling.chooseStep s).realMem s.realMem)
(@Eq.{1} (Nat → Nat) (DecrAlmostLinearSSSP.Decremental.ScaledCeiling.chooseStep s).natMem s.natMem))))) ∧ ((∀ {P : Nat} {x : Real} {s : DecrAlmostLinearSSSP.Decremental.Structured.Data},
DecrAlmostLinearSSSP.Decremental.ScaledCeiling.GreedyInvariant P x s →
DecrAlmostLinearSSSP.Decremental.ScaledCeiling.greedyTest.holds s →
And
(DecrAlmostLinearSSSP.Decremental.ScaledCeiling.GreedyInvariant P x
(DecrAlmostLinearSSSP.Decremental.ScaledCeiling.greedyStep s))
(@LT.lt.{0} Nat instLTNat
((DecrAlmostLinearSSSP.Decremental.ScaledCeiling.greedyStep s).natReg
(@OfNat.ofNat.{0} Nat (nat_lit 1) (instOfNatNat (nat_lit 1))))
(s.natReg (@OfNat.ofNat.{0} Nat (nat_lit 1) (instOfNatNat (nat_lit 1)))))) ∧ (∀ {P : Nat} {x : Real} {s : DecrAlmostLinearSSSP.Decremental.Structured.Data},
DecrAlmostLinearSSSP.Decremental.ScaledCeiling.GreedyInvariant P x s →
∃ t cost,
And
(DecrAlmostLinearSSSP.Decremental.Structured.Eval DecrAlmostLinearSSSP.Decremental.ScaledCeiling.greedyLoop s
cost t)
(And (DecrAlmostLinearSSSP.Decremental.ScaledCeiling.GreedyInvariant P x t)
(And (Not (DecrAlmostLinearSSSP.Decremental.ScaledCeiling.greedyTest.holds t))
(@LE.le.{0} Nat instLENat cost
(@HAdd.hAdd.{0, 0, 0} Nat Nat Nat (@instHAdd.{0} Nat instAddNat)
(@HMul.hMul.{0, 0, 0} Nat Nat Nat (@instHMul.{0} Nat instMulNat)
(@OfNat.ofNat.{0} Nat (nat_lit 9) (instOfNatNat (nat_lit 9)))
(s.natReg (@OfNat.ofNat.{0} Nat (nat_lit 1) (instOfNatNat (nat_lit 1)))))
(@OfNat.ofNat.{0} Nat (nat_lit 2) (instOfNatNat (nat_lit 2))))))))))))) ∧ (((((∀ {P : Nat} {x : Real} {s : DecrAlmostLinearSSSP.Decremental.Structured.Data},
DecrAlmostLinearSSSP.Decremental.ScaledCeiling.GreedyInvariant P x s →
Not (DecrAlmostLinearSSSP.Decremental.ScaledCeiling.greedyTest.holds s) →
@Eq.{1} Nat
(@HAdd.hAdd.{0, 0, 0} Nat Nat Nat (@instHAdd.{0} Nat instAddNat)
(s.natReg (@OfNat.ofNat.{0} Nat (nat_lit 3) (instOfNatNat (nat_lit 3))))
(s.natReg (@OfNat.ofNat.{0} Nat (nat_lit 0) (instOfNatNat (nat_lit 0)))))
(@HMul.hMul.{0, 0, 0} Nat Nat Nat (@instHMul.{0} Nat instMulNat) P
(@Nat.ceil.{0} Real Real.semiring Real.partialOrder
(@FloorRing.toFloorSemiring.{0} Real Real.instRing Real.linearOrder Real.instFloorRing) x))) ∧ (∀ (s : DecrAlmostLinearSSSP.Decremental.Structured.Data) (N : Nat),
@LE.le.{0} Real Real.instLE (@OfNat.ofNat.{0} Real (nat_lit 0) (@Zero.toOfNat0.{0} Real Real.instZero))
(s.realReg (@OfNat.ofNat.{0} Nat (nat_lit 0) (instOfNatNat (nat_lit 0)))) →
@LE.le.{0} Real Real.instLE (s.realReg (@OfNat.ofNat.{0} Nat (nat_lit 0) (instOfNatNat (nat_lit 0))))
(@HPow.hPow.{0, 0, 0} Real Nat Real
(@instHPow.{0, 0} Real Nat (@NPow.toPow.{0} Real (@Monoid.toNPow.{0} Real Real.instMonoid)))
(@OfNat.ofNat.{0} Real (nat_lit 2)
(@instOfNatAtLeastTwo.{0} Real (nat_lit 2) Real.instNatCast
(@Nat.instAtLeastTwoHAddOfNat (@OfNat.ofNat.{0} Nat (nat_lit 1) (instOfNatNat (nat_lit 1)))
(@Nat.instNeZeroSucc (@OfNat.ofNat.{0} Nat (nat_lit 0) (instOfNatNat (nat_lit 0)))))))
N) →
∃ t cost,
And
(DecrAlmostLinearSSSP.Decremental.Structured.Eval DecrAlmostLinearSSSP.Decremental.ScaledCeiling.routine s
cost t)
(And
(@Eq.{1} Nat (t.natReg (@OfNat.ofNat.{0} Nat (nat_lit 3) (instOfNatNat (nat_lit 3))))
(@HMul.hMul.{0, 0, 0} Nat Nat Nat (@instHMul.{0} Nat instMulNat)
(s.natReg (@OfNat.ofNat.{0} Nat (nat_lit 0) (instOfNatNat (nat_lit 0))))
(@Nat.ceil.{0} Real Real.semiring Real.partialOrder
(@FloorRing.toFloorSemiring.{0} Real Real.instRing Real.linearOrder Real.instFloorRing)
(s.realReg (@OfNat.ofNat.{0} Nat (nat_lit 0) (instOfNatNat (nat_lit 0)))))))
(@LE.le.{0} Nat instLENat cost
(@HAdd.hAdd.{0, 0, 0} Nat Nat Nat (@instHAdd.{0} Nat instAddNat)
(@HMul.hMul.{0, 0, 0} Nat Nat Nat (@instHMul.{0} Nat instMulNat)
(@OfNat.ofNat.{0} Nat (nat_lit 16) (instOfNatNat (nat_lit 16))) N)
(@OfNat.ofNat.{0} Nat (nat_lit 14) (instOfNatNat (nat_lit 14)))))))) ∧ ((∀ (c : DecrAlmostLinearSSSP.Decremental.Machine) (N : Nat),
@Eq.{1} Nat c.pc (@OfNat.ofNat.{0} Nat (nat_lit 0) (instOfNatNat (nat_lit 0))) →
@Eq.{1} Bool c.halted Bool.false →
@Eq.{1} Bool c.fault Bool.false →
@LE.le.{0} Real Real.instLE (@OfNat.ofNat.{0} Real (nat_lit 0) (@Zero.toOfNat0.{0} Real Real.instZero))
(c.realReg (@OfNat.ofNat.{0} Nat (nat_lit 0) (instOfNatNat (nat_lit 0)))) →
@LE.le.{0} Real Real.instLE (c.realReg (@OfNat.ofNat.{0} Nat (nat_lit 0) (instOfNatNat (nat_lit 0))))
(@HPow.hPow.{0, 0, 0} Real Nat Real
(@instHPow.{0, 0} Real Nat (@NPow.toPow.{0} Real (@Monoid.toNPow.{0} Real Real.instMonoid)))
(@OfNat.ofNat.{0} Real (nat_lit 2)
(@instOfNatAtLeastTwo.{0} Real (nat_lit 2) Real.instNatCast
(@Nat.instAtLeastTwoHAddOfNat (@OfNat.ofNat.{0} Nat (nat_lit 1) (instOfNatNat (nat_lit 1)))
(@Nat.instNeZeroSucc (@OfNat.ofNat.{0} Nat (nat_lit 0) (instOfNatNat (nat_lit 0)))))))
N) →
∃ d,
And
(DecrAlmostLinearSSSP.Decremental.Ends
(DecrAlmostLinearSSSP.Decremental.Structured.program
DecrAlmostLinearSSSP.Decremental.ScaledCeiling.routine
DecrAlmostLinearSSSP.Decremental.Structured.Cmd.skip)
c d)
(And
(@Eq.{1} Nat (d.natReg (@OfNat.ofNat.{0} Nat (nat_lit 3) (instOfNatNat (nat_lit 3))))
(@HMul.hMul.{0, 0, 0} Nat Nat Nat (@instHMul.{0} Nat instMulNat)
(c.natReg (@OfNat.ofNat.{0} Nat (nat_lit 0) (instOfNatNat (nat_lit 0))))
(@Nat.ceil.{0} Real Real.semiring Real.partialOrder
(@FloorRing.toFloorSemiring.{0} Real Real.instRing Real.linearOrder Real.instFloorRing)
(c.realReg (@OfNat.ofNat.{0} Nat (nat_lit 0) (instOfNatNat (nat_lit 0)))))))
(@LE.le.{0} Nat instLENat d.work
(@HAdd.hAdd.{0, 0, 0} Nat Nat Nat (@instHAdd.{0} Nat instAddNat)
(@HAdd.hAdd.{0, 0, 0} Nat Nat Nat (@instHAdd.{0} Nat instAddNat) c.work
(@HMul.hMul.{0, 0, 0} Nat Nat Nat (@instHMul.{0} Nat instMulNat)
(@OfNat.ofNat.{0} Nat (nat_lit 16) (instOfNatNat (nat_lit 16))) N))
(@OfNat.ofNat.{0} Nat (nat_lit 15) (instOfNatNat (nat_lit 15))))))) ∧ (∀ (p : DecrAlmostLinearSSSP.Decremental.Program) (c : DecrAlmostLinearSSSP.Decremental.Machine) (d factor count : Nat),
@Ne.{1} Nat factor d →
@Eq.{1} Bool c.halted Bool.false →
(∀ (j : Nat),
@LT.lt.{0} Nat instLTNat j count →
@Eq.{1} (Option.{0} DecrAlmostLinearSSSP.Decremental.Instruction)
(@GetElem?.getElem?.{0, 0, 0} (List.{0} DecrAlmostLinearSSSP.Decremental.Instruction) Nat
DecrAlmostLinearSSSP.Decremental.Instruction
(fun as i =>
@LT.lt.{0} Nat instLTNat i (@List.length.{0} DecrAlmostLinearSSSP.Decremental.Instruction as))
(@List.instGetElem?NatLtLength.{0} DecrAlmostLinearSSSP.Decremental.Instruction) p.code
(@HAdd.hAdd.{0, 0, 0} Nat Nat Nat (@instHAdd.{0} Nat instAddNat) c.pc j))
(@Option.some.{0} DecrAlmostLinearSSSP.Decremental.Instruction
(DecrAlmostLinearSSSP.Decremental.Instruction.nadd d d factor))) →
@Eq.{1} DecrAlmostLinearSSSP.Decremental.Machine (DecrAlmostLinearSSSP.Decremental.execute p c count)
{ pc := @HAdd.hAdd.{0, 0, 0} Nat Nat Nat (@instHAdd.{0} Nat instAddNat) c.pc count, realReg := c.realReg,
natReg :=
@Function.update.{1, 1} Nat (fun a => Nat) instDecidableEqNat c.natReg d
(@HAdd.hAdd.{0, 0, 0} Nat Nat Nat (@instHAdd.{0} Nat instAddNat) (c.natReg d)
(@HMul.hMul.{0, 0, 0} Nat Nat Nat (@instHMul.{0} Nat instMulNat) count (c.natReg factor))),
realMem := c.realMem, natMem := c.natMem, halted := c.halted, fault := c.fault,
work := @HAdd.hAdd.{0, 0, 0} Nat Nat Nat (@instHAdd.{0} Nat instAddNat) c.work count }))) ∧ (((∀ (d factor q : Nat),
@Eq.{1} Nat
(@List.length.{0} DecrAlmostLinearSSSP.Decremental.Instruction
(DecrAlmostLinearSSSP.Decremental.constantProductCode d factor q))
(@HAdd.hAdd.{0, 0, 0} Nat Nat Nat (@instHAdd.{0} Nat instAddNat) q
(@OfNat.ofNat.{0} Nat (nat_lit 1) (instOfNatNat (nat_lit 1))))) ∧ (∀ (p : DecrAlmostLinearSSSP.Decremental.Program) (c : DecrAlmostLinearSSSP.Decremental.Machine) (d factor q : Nat),
@Ne.{1} Nat factor d →
@Eq.{1} Bool c.halted Bool.false →
@Eq.{1} (Option.{0} DecrAlmostLinearSSSP.Decremental.Instruction)
(@GetElem?.getElem?.{0, 0, 0} (List.{0} DecrAlmostLinearSSSP.Decremental.Instruction) Nat
DecrAlmostLinearSSSP.Decremental.Instruction
(fun as i => @LT.lt.{0} Nat instLTNat i (@List.length.{0} DecrAlmostLinearSSSP.Decremental.Instruction as))
(@List.instGetElem?NatLtLength.{0} DecrAlmostLinearSSSP.Decremental.Instruction) p.code c.pc)
(@Option.some.{0} DecrAlmostLinearSSSP.Decremental.Instruction
(DecrAlmostLinearSSSP.Decremental.Instruction.natural d
(@OfNat.ofNat.{0} Nat (nat_lit 0) (instOfNatNat (nat_lit 0))))) →
(∀ (j : Nat),
@LT.lt.{0} Nat instLTNat j q →
@Eq.{1} (Option.{0} DecrAlmostLinearSSSP.Decremental.Instruction)
(@GetElem?.getElem?.{0, 0, 0} (List.{0} DecrAlmostLinearSSSP.Decremental.Instruction) Nat
DecrAlmostLinearSSSP.Decremental.Instruction
(fun as i =>
@LT.lt.{0} Nat instLTNat i (@List.length.{0} DecrAlmostLinearSSSP.Decremental.Instruction as))
(@List.instGetElem?NatLtLength.{0} DecrAlmostLinearSSSP.Decremental.Instruction) p.code
(@HAdd.hAdd.{0, 0, 0} Nat Nat Nat (@instHAdd.{0} Nat instAddNat)
(@HAdd.hAdd.{0, 0, 0} Nat Nat Nat (@instHAdd.{0} Nat instAddNat) c.pc
(@OfNat.ofNat.{0} Nat (nat_lit 1) (instOfNatNat (nat_lit 1))))
j))
(@Option.some.{0} DecrAlmostLinearSSSP.Decremental.Instruction
(DecrAlmostLinearSSSP.Decremental.Instruction.nadd d d factor))) →
@Eq.{1} DecrAlmostLinearSSSP.Decremental.Machine
(DecrAlmostLinearSSSP.Decremental.execute p c
(@HAdd.hAdd.{0, 0, 0} Nat Nat Nat (@instHAdd.{0} Nat instAddNat) q
(@OfNat.ofNat.{0} Nat (nat_lit 1) (instOfNatNat (nat_lit 1)))))
{
pc :=
@HAdd.hAdd.{0, 0, 0} Nat Nat Nat (@instHAdd.{0} Nat instAddNat) c.pc
(@HAdd.hAdd.{0, 0, 0} Nat Nat Nat (@instHAdd.{0} Nat instAddNat) q
(@OfNat.ofNat.{0} Nat (nat_lit 1) (instOfNatNat (nat_lit 1)))),
realReg := c.realReg,
natReg :=
@Function.update.{1, 1} Nat (fun a => Nat) instDecidableEqNat c.natReg d
(@HMul.hMul.{0, 0, 0} Nat Nat Nat (@instHMul.{0} Nat instMulNat) q (c.natReg factor)),
realMem := c.realMem, natMem := c.natMem, halted := c.halted, fault := c.fault,
work :=
@HAdd.hAdd.{0, 0, 0} Nat Nat Nat (@instHAdd.{0} Nat instAddNat) c.work
(@HAdd.hAdd.{0, 0, 0} Nat Nat Nat (@instHAdd.{0} Nat instAddNat) q
(@OfNat.ofNat.{0} Nat (nat_lit 1) (instOfNatNat (nat_lit 1)))) })) ∧ ((∀ (width offset returnPC pc : Nat) (ins : DecrAlmostLinearSSSP.Decremental.Instruction),
@LE.le.{0} Nat instLENat (@OfNat.ofNat.{0} Nat (nat_lit 8) (instOfNatNat (nat_lit 8))) width →
@LE.le.{0} Nat instLENat
(@HAdd.hAdd.{0, 0, 0} Nat Nat Nat (@instHAdd.{0} Nat instAddNat)
(DecrAlmostLinearSSSP.Decremental.naturalConstant ins)
(@OfNat.ofNat.{0} Nat (nat_lit 4) (instOfNatNat (nat_lit 4))))
width →
@Eq.{1} Nat
(@List.length.{0} DecrAlmostLinearSSSP.Decremental.Instruction
(DecrAlmostLinearSSSP.Decremental.shadowBlock width offset returnPC pc ins))
width) ∧ ((∀ (code : List.{0} DecrAlmostLinearSSSP.Decremental.Instruction) (ins : DecrAlmostLinearSSSP.Decremental.Instruction),
@Membership.mem.{0, 0} DecrAlmostLinearSSSP.Decremental.Instruction
(List.{0} DecrAlmostLinearSSSP.Decremental.Instruction)
(@List.instMembership.{0} DecrAlmostLinearSSSP.Decremental.Instruction) code ins →
@LE.le.{0} Nat instLENat
(@HAdd.hAdd.{0, 0, 0} Nat Nat Nat (@instHAdd.{0} Nat instAddNat)
(DecrAlmostLinearSSSP.Decremental.naturalConstant ins)
(@OfNat.ofNat.{0} Nat (nat_lit 4) (instOfNatNat (nat_lit 4))))
(DecrAlmostLinearSSSP.Decremental.shadowWidth code)) ∧ (∀ (code : List.{0} DecrAlmostLinearSSSP.Decremental.Instruction),
@LE.le.{0} Nat instLENat (@OfNat.ofNat.{0} Nat (nat_lit 8) (instOfNatNat (nat_lit 8)))
(DecrAlmostLinearSSSP.Decremental.shadowWidth code)))))) ∧ ((((∀ (width offset returnPC start : Nat) (code : List.{0} DecrAlmostLinearSSSP.Decremental.Instruction),
@LE.le.{0} Nat instLENat (@OfNat.ofNat.{0} Nat (nat_lit 8) (instOfNatNat (nat_lit 8))) width →
(∀ (ins : DecrAlmostLinearSSSP.Decremental.Instruction),
@Membership.mem.{0, 0} DecrAlmostLinearSSSP.Decremental.Instruction
(List.{0} DecrAlmostLinearSSSP.Decremental.Instruction)
(@List.instMembership.{0} DecrAlmostLinearSSSP.Decremental.Instruction) code ins →
@LE.le.{0} Nat instLENat
(@HAdd.hAdd.{0, 0, 0} Nat Nat Nat (@instHAdd.{0} Nat instAddNat)
(DecrAlmostLinearSSSP.Decremental.naturalConstant ins)
(@OfNat.ofNat.{0} Nat (nat_lit 4) (instOfNatNat (nat_lit 4))))
width) →
@Eq.{1} Nat
(@List.length.{0} DecrAlmostLinearSSSP.Decremental.Instruction
(DecrAlmostLinearSSSP.Decremental.shadowCodeAux width offset returnPC start code))
(@HMul.hMul.{0, 0, 0} Nat Nat Nat (@instHMul.{0} Nat instMulNat) width
(@List.length.{0} DecrAlmostLinearSSSP.Decremental.Instruction code))) ∧ (∀ (offset returnPC : Nat) (code : List.{0} DecrAlmostLinearSSSP.Decremental.Instruction),
@Eq.{1} Nat
(@List.length.{0} DecrAlmostLinearSSSP.Decremental.Instruction
(DecrAlmostLinearSSSP.Decremental.shadowCode offset returnPC code))
(@HMul.hMul.{0, 0, 0} Nat Nat Nat (@instHMul.{0} Nat instMulNat) (DecrAlmostLinearSSSP.Decremental.shadowWidth code)
(@List.length.{0} DecrAlmostLinearSSSP.Decremental.Instruction code)))) ∧ ((∀ {base F : Nat} {c g : DecrAlmostLinearSSSP.Decremental.Machine},
DecrAlmostLinearSSSP.Decremental.ShadowRep base F c g →
∀ (host : DecrAlmostLinearSSSP.Decremental.Program),
@Eq.{1} Bool c.halted Bool.false →
@Eq.{1} Nat (c.natReg (@OfNat.ofNat.{0} Nat (nat_lit 1) (instOfNatNat (nat_lit 1))))
(@OfNat.ofNat.{0} Nat (nat_lit 1) (instOfNatNat (nat_lit 1))) →
@Eq.{1} (Option.{0} DecrAlmostLinearSSSP.Decremental.Instruction)
(@GetElem?.getElem?.{0, 0, 0} (List.{0} DecrAlmostLinearSSSP.Decremental.Instruction) Nat
DecrAlmostLinearSSSP.Decremental.Instruction
(fun as i =>
@LT.lt.{0} Nat instLTNat i (@List.length.{0} DecrAlmostLinearSSSP.Decremental.Instruction as))
(@List.instGetElem?NatLtLength.{0} DecrAlmostLinearSSSP.Decremental.Instruction) host.code c.pc)
(@Option.some.{0} DecrAlmostLinearSSSP.Decremental.Instruction
(DecrAlmostLinearSSSP.Decremental.Instruction.natural
(@OfNat.ofNat.{0} Nat (nat_lit 2) (instOfNatNat (nat_lit 2)))
(@HAdd.hAdd.{0, 0, 0} Nat Nat Nat (@instHAdd.{0} Nat instAddNat) g.pc
(@OfNat.ofNat.{0} Nat (nat_lit 1) (instOfNatNat (nat_lit 1)))))) →
@Eq.{1} (Option.{0} DecrAlmostLinearSSSP.Decremental.Instruction)
(@GetElem?.getElem?.{0, 0, 0} (List.{0} DecrAlmostLinearSSSP.Decremental.Instruction) Nat
DecrAlmostLinearSSSP.Decremental.Instruction
(fun as i =>
@LT.lt.{0} Nat instLTNat i (@List.length.{0} DecrAlmostLinearSSSP.Decremental.Instruction as))
(@List.instGetElem?NatLtLength.{0} DecrAlmostLinearSSSP.Decremental.Instruction) host.code
(@HAdd.hAdd.{0, 0, 0} Nat Nat Nat (@instHAdd.{0} Nat instAddNat) c.pc
(@OfNat.ofNat.{0} Nat (nat_lit 1) (instOfNatNat (nat_lit 1)))))
(@Option.some.{0} DecrAlmostLinearSSSP.Decremental.Instruction
(DecrAlmostLinearSSSP.Decremental.Instruction.nadd
(@OfNat.ofNat.{0} Nat (nat_lit 3) (instOfNatNat (nat_lit 3)))
(@OfNat.ofNat.{0} Nat (nat_lit 3) (instOfNatNat (nat_lit 3)))
(@OfNat.ofNat.{0} Nat (nat_lit 1) (instOfNatNat (nat_lit 1))))) →
DecrAlmostLinearSSSP.Decremental.ShadowRep base F
(DecrAlmostLinearSSSP.Decremental.execute host c
(@OfNat.ofNat.{0} Nat (nat_lit 2) (instOfNatNat (nat_lit 2))))
{
pc :=
@HAdd.hAdd.{0, 0, 0} Nat Nat Nat (@instHAdd.{0} Nat instAddNat) g.pc
(@OfNat.ofNat.{0} Nat (nat_lit 1) (instOfNatNat (nat_lit 1))),
realReg := g.realReg, natReg := g.natReg, realMem := g.realMem, natMem := g.natMem,
halted := g.halted, fault := g.fault,
work :=
@HAdd.hAdd.{0, 0, 0} Nat Nat Nat (@instHAdd.{0} Nat instAddNat) g.work
(@OfNat.ofNat.{0} Nat (nat_lit 1) (instOfNatNat (nat_lit 1))) }) ∧ ((∀ {base F : Nat} {c g : DecrAlmostLinearSSSP.Decremental.Machine},
DecrAlmostLinearSSSP.Decremental.ShadowRep base F c g →
∀ (host : DecrAlmostLinearSSSP.Decremental.Program) (ins tr : DecrAlmostLinearSSSP.Decremental.Instruction),
@Eq.{1} (Option.{0} DecrAlmostLinearSSSP.Decremental.Instruction)
(DecrAlmostLinearSSSP.Decremental.shadowScalarTranslation ins)
(@Option.some.{0} DecrAlmostLinearSSSP.Decremental.Instruction tr) →
@Eq.{1} Bool c.halted Bool.false →
@Eq.{1} (Option.{0} DecrAlmostLinearSSSP.Decremental.Instruction)
(@GetElem?.getElem?.{0, 0, 0} (List.{0} DecrAlmostLinearSSSP.Decremental.Instruction) Nat
DecrAlmostLinearSSSP.Decremental.Instruction
(fun as i =>
@LT.lt.{0} Nat instLTNat i (@List.length.{0} DecrAlmostLinearSSSP.Decremental.Instruction as))
(@List.instGetElem?NatLtLength.{0} DecrAlmostLinearSSSP.Decremental.Instruction) host.code c.pc)
(@Option.some.{0} DecrAlmostLinearSSSP.Decremental.Instruction tr) →
DecrAlmostLinearSSSP.Decremental.ShadowRep base F (DecrAlmostLinearSSSP.Decremental.step host c)
(DecrAlmostLinearSSSP.Decremental.instructionEffect ins g)) ∧ (∀ {base F : Nat} {c g : DecrAlmostLinearSSSP.Decremental.Machine},
DecrAlmostLinearSSSP.Decremental.ShadowRep base F c g →
∀ (host : DecrAlmostLinearSSSP.Decremental.Program) (target : Nat),
@Eq.{1} Bool c.halted Bool.false →
@Eq.{1} (Option.{0} DecrAlmostLinearSSSP.Decremental.Instruction)
(@GetElem?.getElem?.{0, 0, 0} (List.{0} DecrAlmostLinearSSSP.Decremental.Instruction) Nat
DecrAlmostLinearSSSP.Decremental.Instruction
(fun as i =>
@LT.lt.{0} Nat instLTNat i (@List.length.{0} DecrAlmostLinearSSSP.Decremental.Instruction as))
(@List.instGetElem?NatLtLength.{0} DecrAlmostLinearSSSP.Decremental.Instruction) host.code c.pc)
(@Option.some.{0} DecrAlmostLinearSSSP.Decremental.Instruction
(DecrAlmostLinearSSSP.Decremental.Instruction.jump target)) →
DecrAlmostLinearSSSP.Decremental.ShadowRep base F (DecrAlmostLinearSSSP.Decremental.step host c) g)))) ∧ (((∀ {base F : Nat} {c g : DecrAlmostLinearSSSP.Decremental.Machine},
DecrAlmostLinearSSSP.Decremental.ShadowRep base F c g →
∀ (host : DecrAlmostLinearSSSP.Decremental.Program) (d q : Nat),
@Eq.{1} Nat (c.natReg (@OfNat.ofNat.{0} Nat (nat_lit 7) (instOfNatNat (nat_lit 7)))) F →
@Eq.{1} Bool c.halted Bool.false →
@Eq.{1} (Option.{0} DecrAlmostLinearSSSP.Decremental.Instruction)
(@GetElem?.getElem?.{0, 0, 0} (List.{0} DecrAlmostLinearSSSP.Decremental.Instruction) Nat
DecrAlmostLinearSSSP.Decremental.Instruction
(fun as i =>
@LT.lt.{0} Nat instLTNat i (@List.length.{0} DecrAlmostLinearSSSP.Decremental.Instruction as))
(@List.instGetElem?NatLtLength.{0} DecrAlmostLinearSSSP.Decremental.Instruction) host.code c.pc)
(@Option.some.{0} DecrAlmostLinearSSSP.Decremental.Instruction
(DecrAlmostLinearSSSP.Decremental.Instruction.natural (DecrAlmostLinearSSSP.Decremental.shadowReg d)
(@OfNat.ofNat.{0} Nat (nat_lit 0) (instOfNatNat (nat_lit 0))))) →
(∀ (j : Nat),
@LT.lt.{0} Nat instLTNat j q →
@Eq.{1} (Option.{0} DecrAlmostLinearSSSP.Decremental.Instruction)
(@GetElem?.getElem?.{0, 0, 0} (List.{0} DecrAlmostLinearSSSP.Decremental.Instruction) Nat
DecrAlmostLinearSSSP.Decremental.Instruction
(fun as i =>
@LT.lt.{0} Nat instLTNat i (@List.length.{0} DecrAlmostLinearSSSP.Decremental.Instruction as))
(@List.instGetElem?NatLtLength.{0} DecrAlmostLinearSSSP.Decremental.Instruction) host.code
(@HAdd.hAdd.{0, 0, 0} Nat Nat Nat (@instHAdd.{0} Nat instAddNat)
(@HAdd.hAdd.{0, 0, 0} Nat Nat Nat (@instHAdd.{0} Nat instAddNat) c.pc
(@OfNat.ofNat.{0} Nat (nat_lit 1) (instOfNatNat (nat_lit 1))))
j))
(@Option.some.{0} DecrAlmostLinearSSSP.Decremental.Instruction
(DecrAlmostLinearSSSP.Decremental.Instruction.nadd (DecrAlmostLinearSSSP.Decremental.shadowReg d)
(DecrAlmostLinearSSSP.Decremental.shadowReg d)
(@OfNat.ofNat.{0} Nat (nat_lit 7) (instOfNatNat (nat_lit 7)))))) →
DecrAlmostLinearSSSP.Decremental.ShadowRep base F
(DecrAlmostLinearSSSP.Decremental.execute host c
(@HAdd.hAdd.{0, 0, 0} Nat Nat Nat (@instHAdd.{0} Nat instAddNat) q
(@OfNat.ofNat.{0} Nat (nat_lit 1) (instOfNatNat (nat_lit 1)))))
(DecrAlmostLinearSSSP.Decremental.instructionEffect
(DecrAlmostLinearSSSP.Decremental.Instruction.natural d q) g)) ∧ (∀ (width offset returnPC pc : Nat) (ins tr : DecrAlmostLinearSSSP.Decremental.Instruction),
@Membership.mem.{0, 0} DecrAlmostLinearSSSP.Decremental.Instruction
(List.{0} DecrAlmostLinearSSSP.Decremental.Instruction)
(@List.instMembership.{0} DecrAlmostLinearSSSP.Decremental.Instruction)
(DecrAlmostLinearSSSP.Decremental.shadowBlock width offset returnPC pc ins) tr →
DecrAlmostLinearSSSP.Decremental.ReservedSafe tr)) ∧ ((∀ (width offset returnPC start : Nat) (code : List.{0} DecrAlmostLinearSSSP.Decremental.Instruction)
(tr : DecrAlmostLinearSSSP.Decremental.Instruction),
@Membership.mem.{0, 0} DecrAlmostLinearSSSP.Decremental.Instruction
(List.{0} DecrAlmostLinearSSSP.Decremental.Instruction)
(@List.instMembership.{0} DecrAlmostLinearSSSP.Decremental.Instruction)
(DecrAlmostLinearSSSP.Decremental.shadowCodeAux width offset returnPC start code) tr →
DecrAlmostLinearSSSP.Decremental.ReservedSafe tr) ∧ ((∀ {α : Type} (mem : Nat → α) (base j k a b : Nat) (value : α),
@Ne.{1} Nat j k →
@Eq.{1} α
(@Function.update.{1, 1} Nat (fun a => α) instDecidableEqNat mem
(DecrAlmostLinearSSSP.Decremental.bankAddress base j a) value
(DecrAlmostLinearSSSP.Decremental.bankAddress base k b))
(mem (DecrAlmostLinearSSSP.Decremental.bankAddress base k b))) ∧ (∀ {α : Type} (mem : Nat → α) (base j a b : Nat) (value : α),
@Eq.{1} α
(@Function.update.{1, 1} Nat (fun a => α) instDecidableEqNat mem
(DecrAlmostLinearSSSP.Decremental.bankAddress base j a) value
(@HAdd.hAdd.{0, 0, 0} Nat Nat Nat (@instHAdd.{0} Nat instAddNat) base
(@HAdd.hAdd.{0, 0, 0} Nat Nat Nat (@instHAdd.{0} Nat instAddNat)
(@HMul.hMul.{0, 0, 0} Nat Nat Nat (@instHMul.{0} Nat instMulNat)
(@OfNat.ofNat.{0} Nat (nat_lit 2) (instOfNatNat (nat_lit 2))) b)
(@OfNat.ofNat.{0} Nat (nat_lit 1) (instOfNatNat (nat_lit 1))))))
(mem
(@HAdd.hAdd.{0, 0, 0} Nat Nat Nat (@instHAdd.{0} Nat instAddNat) base
(@HAdd.hAdd.{0, 0, 0} Nat Nat Nat (@instHAdd.{0} Nat instAddNat)
(@HMul.hMul.{0, 0, 0} Nat Nat Nat (@instHMul.{0} Nat instMulNat)
(@OfNat.ofNat.{0} Nat (nat_lit 2) (instOfNatNat (nat_lit 2))) b)
(@OfNat.ofNat.{0} Nat (nat_lit 1) (instOfNatNat (nat_lit 1))))))))))))) ∧ ((((((∀ {α : Type} (mem : Nat → α) (base j a b : Nat) (value : α),
@LE.le.{0} Nat instLENat b base →
@Eq.{1} α
(@Function.update.{1, 1} Nat (fun a => α) instDecidableEqNat mem
(DecrAlmostLinearSSSP.Decremental.bankAddress base j a) value b)
(mem b)) ∧ (∀ (ins tr : DecrAlmostLinearSSSP.Decremental.Instruction),
@Eq.{1} (Option.{0} DecrAlmostLinearSSSP.Decremental.Instruction)
(DecrAlmostLinearSSSP.Decremental.shadowScalarTranslation ins)
(@Option.some.{0} DecrAlmostLinearSSSP.Decremental.Instruction tr) →
DecrAlmostLinearSSSP.Decremental.ReservedSafe tr)) ∧ ((∀ {base F : Nat} {c g : DecrAlmostLinearSSSP.Decremental.Machine},
DecrAlmostLinearSSSP.Decremental.ShadowRep base F c g →
∀ (host : DecrAlmostLinearSSSP.Decremental.Program) (ins tr : DecrAlmostLinearSSSP.Decremental.Instruction),
@Eq.{1} (Option.{0} DecrAlmostLinearSSSP.Decremental.Instruction)
(DecrAlmostLinearSSSP.Decremental.shadowScalarTranslation ins)
(@Option.some.{0} DecrAlmostLinearSSSP.Decremental.Instruction tr) →
@Eq.{1} Bool c.halted Bool.false →
@Eq.{1} (Option.{0} DecrAlmostLinearSSSP.Decremental.Instruction)
(@GetElem?.getElem?.{0, 0, 0} (List.{0} DecrAlmostLinearSSSP.Decremental.Instruction) Nat
DecrAlmostLinearSSSP.Decremental.Instruction
(fun as i =>
@LT.lt.{0} Nat instLTNat i (@List.length.{0} DecrAlmostLinearSSSP.Decremental.Instruction as))
(@List.instGetElem?NatLtLength.{0} DecrAlmostLinearSSSP.Decremental.Instruction) host.code c.pc)
(@Option.some.{0} DecrAlmostLinearSSSP.Decremental.Instruction tr) →
And
(DecrAlmostLinearSSSP.Decremental.ShadowRep base F
(DecrAlmostLinearSSSP.Decremental.execute host c
(@OfNat.ofNat.{0} Nat (nat_lit 1) (instOfNatNat (nat_lit 1))))
(DecrAlmostLinearSSSP.Decremental.instructionEffect ins g))
(And
(@Eq.{1} Nat
(DecrAlmostLinearSSSP.Decremental.execute host c
(@OfNat.ofNat.{0} Nat (nat_lit 1) (instOfNatNat (nat_lit 1)))).pc
(@HAdd.hAdd.{0, 0, 0} Nat Nat Nat (@instHAdd.{0} Nat instAddNat) c.pc
(@OfNat.ofNat.{0} Nat (nat_lit 1) (instOfNatNat (nat_lit 1)))))
(And
(@Eq.{1} Nat
(DecrAlmostLinearSSSP.Decremental.execute host c
(@OfNat.ofNat.{0} Nat (nat_lit 1) (instOfNatNat (nat_lit 1)))).work
(@HAdd.hAdd.{0, 0, 0} Nat Nat Nat (@instHAdd.{0} Nat instAddNat) c.work
(@OfNat.ofNat.{0} Nat (nat_lit 1) (instOfNatNat (nat_lit 1)))))
(And
(@Eq.{1} Bool
(DecrAlmostLinearSSSP.Decremental.execute host c
(@OfNat.ofNat.{0} Nat (nat_lit 1) (instOfNatNat (nat_lit 1)))).halted
Bool.false)
(And
(@Eq.{1} Nat
((DecrAlmostLinearSSSP.Decremental.execute host c
(@OfNat.ofNat.{0} Nat (nat_lit 1) (instOfNatNat (nat_lit 1)))).natReg
(@OfNat.ofNat.{0} Nat (nat_lit 0) (instOfNatNat (nat_lit 0))))
(c.natReg (@OfNat.ofNat.{0} Nat (nat_lit 0) (instOfNatNat (nat_lit 0)))))
(And
(@Eq.{1} Nat
((DecrAlmostLinearSSSP.Decremental.execute host c
(@OfNat.ofNat.{0} Nat (nat_lit 1) (instOfNatNat (nat_lit 1)))).natReg
(@OfNat.ofNat.{0} Nat (nat_lit 1) (instOfNatNat (nat_lit 1))))
(c.natReg (@OfNat.ofNat.{0} Nat (nat_lit 1) (instOfNatNat (nat_lit 1)))))
(And
(@Eq.{1} Nat
((DecrAlmostLinearSSSP.Decremental.execute host c
(@OfNat.ofNat.{0} Nat (nat_lit 1) (instOfNatNat (nat_lit 1)))).natReg
(@OfNat.ofNat.{0} Nat (nat_lit 7) (instOfNatNat (nat_lit 7))))
(c.natReg (@OfNat.ofNat.{0} Nat (nat_lit 7) (instOfNatNat (nat_lit 7)))))
(@Eq.{1} Real
((DecrAlmostLinearSSSP.Decremental.execute host c
(@OfNat.ofNat.{0} Nat (nat_lit 1) (instOfNatNat (nat_lit 1)))).realReg
(@OfNat.ofNat.{0} Nat (nat_lit 7) (instOfNatNat (nat_lit 7))))
(c.realReg (@OfNat.ofNat.{0} Nat (nat_lit 7) (instOfNatNat (nat_lit 7)))))))))))) ∧ (∀ {base F : Nat} {c g : DecrAlmostLinearSSSP.Decremental.Machine},
DecrAlmostLinearSSSP.Decremental.ShadowRep base F c g →
∀ (host : DecrAlmostLinearSSSP.Decremental.Program) (width offset : Nat)
(ins tr : DecrAlmostLinearSSSP.Decremental.Instruction),
@Eq.{1} (Option.{0} DecrAlmostLinearSSSP.Decremental.Instruction)
(DecrAlmostLinearSSSP.Decremental.shadowScalarTranslation ins)
(@Option.some.{0} DecrAlmostLinearSSSP.Decremental.Instruction tr) →
@Eq.{1} Bool c.halted Bool.false →
@Eq.{1} Nat (c.natReg (@OfNat.ofNat.{0} Nat (nat_lit 1) (instOfNatNat (nat_lit 1))))
(@OfNat.ofNat.{0} Nat (nat_lit 1) (instOfNatNat (nat_lit 1))) →
@Eq.{1} (Option.{0} DecrAlmostLinearSSSP.Decremental.Instruction)
(@GetElem?.getElem?.{0, 0, 0} (List.{0} DecrAlmostLinearSSSP.Decremental.Instruction) Nat
DecrAlmostLinearSSSP.Decremental.Instruction
(fun as i =>
@LT.lt.{0} Nat instLTNat i (@List.length.{0} DecrAlmostLinearSSSP.Decremental.Instruction as))
(@List.instGetElem?NatLtLength.{0} DecrAlmostLinearSSSP.Decremental.Instruction) host.code c.pc)
(@Option.some.{0} DecrAlmostLinearSSSP.Decremental.Instruction
(DecrAlmostLinearSSSP.Decremental.Instruction.natural
(@OfNat.ofNat.{0} Nat (nat_lit 2) (instOfNatNat (nat_lit 2)))
(@HAdd.hAdd.{0, 0, 0} Nat Nat Nat (@instHAdd.{0} Nat instAddNat) g.pc
(@OfNat.ofNat.{0} Nat (nat_lit 1) (instOfNatNat (nat_lit 1)))))) →
@Eq.{1} (Option.{0} DecrAlmostLinearSSSP.Decremental.Instruction)
(@GetElem?.getElem?.{0, 0, 0} (List.{0} DecrAlmostLinearSSSP.Decremental.Instruction) Nat
DecrAlmostLinearSSSP.Decremental.Instruction
(fun as i =>
@LT.lt.{0} Nat instLTNat i (@List.length.{0} DecrAlmostLinearSSSP.Decremental.Instruction as))
(@List.instGetElem?NatLtLength.{0} DecrAlmostLinearSSSP.Decremental.Instruction) host.code
(@HAdd.hAdd.{0, 0, 0} Nat Nat Nat (@instHAdd.{0} Nat instAddNat) c.pc
(@OfNat.ofNat.{0} Nat (nat_lit 1) (instOfNatNat (nat_lit 1)))))
(@Option.some.{0} DecrAlmostLinearSSSP.Decremental.Instruction
(DecrAlmostLinearSSSP.Decremental.Instruction.nadd
(@OfNat.ofNat.{0} Nat (nat_lit 3) (instOfNatNat (nat_lit 3)))
(@OfNat.ofNat.{0} Nat (nat_lit 3) (instOfNatNat (nat_lit 3)))
(@OfNat.ofNat.{0} Nat (nat_lit 1) (instOfNatNat (nat_lit 1))))) →
@Eq.{1} (Option.{0} DecrAlmostLinearSSSP.Decremental.Instruction)
(@GetElem?.getElem?.{0, 0, 0} (List.{0} DecrAlmostLinearSSSP.Decremental.Instruction) Nat
DecrAlmostLinearSSSP.Decremental.Instruction
(fun as i =>
@LT.lt.{0} Nat instLTNat i (@List.length.{0} DecrAlmostLinearSSSP.Decremental.Instruction as))
(@List.instGetElem?NatLtLength.{0} DecrAlmostLinearSSSP.Decremental.Instruction) host.code
(@HAdd.hAdd.{0, 0, 0} Nat Nat Nat (@instHAdd.{0} Nat instAddNat) c.pc
(@OfNat.ofNat.{0} Nat (nat_lit 2) (instOfNatNat (nat_lit 2)))))
(@Option.some.{0} DecrAlmostLinearSSSP.Decremental.Instruction tr) →
@Eq.{1} (Option.{0} DecrAlmostLinearSSSP.Decremental.Instruction)
(@GetElem?.getElem?.{0, 0, 0} (List.{0} DecrAlmostLinearSSSP.Decremental.Instruction) Nat
DecrAlmostLinearSSSP.Decremental.Instruction
(fun as i =>
@LT.lt.{0} Nat instLTNat i (@List.length.{0} DecrAlmostLinearSSSP.Decremental.Instruction as))
(@List.instGetElem?NatLtLength.{0} DecrAlmostLinearSSSP.Decremental.Instruction) host.code
(@HAdd.hAdd.{0, 0, 0} Nat Nat Nat (@instHAdd.{0} Nat instAddNat) c.pc
(@OfNat.ofNat.{0} Nat (nat_lit 3) (instOfNatNat (nat_lit 3)))))
(@Option.some.{0} DecrAlmostLinearSSSP.Decremental.Instruction
(DecrAlmostLinearSSSP.Decremental.Instruction.jump
(@HAdd.hAdd.{0, 0, 0} Nat Nat Nat (@instHAdd.{0} Nat instAddNat) offset
(@HMul.hMul.{0, 0, 0} Nat Nat Nat (@instHMul.{0} Nat instMulNat) width
(@HAdd.hAdd.{0, 0, 0} Nat Nat Nat (@instHAdd.{0} Nat instAddNat) g.pc
(@OfNat.ofNat.{0} Nat (nat_lit 1) (instOfNatNat (nat_lit 1)))))))) →
∃ d,
And
(@Eq.{1} DecrAlmostLinearSSSP.Decremental.Machine
(DecrAlmostLinearSSSP.Decremental.execute host c
(@OfNat.ofNat.{0} Nat (nat_lit 4) (instOfNatNat (nat_lit 4))))
d)
(And
(DecrAlmostLinearSSSP.Decremental.ShadowRep base F d
(DecrAlmostLinearSSSP.Decremental.instructionEffect ins
{
pc :=
@HAdd.hAdd.{0, 0, 0} Nat Nat Nat (@instHAdd.{0} Nat instAddNat) g.pc
(@OfNat.ofNat.{0} Nat (nat_lit 1) (instOfNatNat (nat_lit 1))),
realReg := g.realReg, natReg := g.natReg, realMem := g.realMem, natMem := g.natMem,
halted := g.halted, fault := g.fault,
work :=
@HAdd.hAdd.{0, 0, 0} Nat Nat Nat (@instHAdd.{0} Nat instAddNat) g.work
(@OfNat.ofNat.{0} Nat (nat_lit 1) (instOfNatNat (nat_lit 1))) }))
(And
(@Eq.{1} Nat d.pc
(@HAdd.hAdd.{0, 0, 0} Nat Nat Nat (@instHAdd.{0} Nat instAddNat) offset
(@HMul.hMul.{0, 0, 0} Nat Nat Nat (@instHMul.{0} Nat instMulNat) width
(@HAdd.hAdd.{0, 0, 0} Nat Nat Nat (@instHAdd.{0} Nat instAddNat) g.pc
(@OfNat.ofNat.{0} Nat (nat_lit 1) (instOfNatNat (nat_lit 1)))))))
(And
(@Eq.{1} Nat d.work
(@HAdd.hAdd.{0, 0, 0} Nat Nat Nat (@instHAdd.{0} Nat instAddNat) c.work
(@OfNat.ofNat.{0} Nat (nat_lit 4) (instOfNatNat (nat_lit 4)))))
(And (@Eq.{1} Bool d.halted Bool.false)
(And
(@Eq.{1} Nat (d.natReg (@OfNat.ofNat.{0} Nat (nat_lit 0) (instOfNatNat (nat_lit 0))))
(c.natReg (@OfNat.ofNat.{0} Nat (nat_lit 0) (instOfNatNat (nat_lit 0)))))
(And
(@Eq.{1} Nat
(d.natReg (@OfNat.ofNat.{0} Nat (nat_lit 1) (instOfNatNat (nat_lit 1))))
(c.natReg (@OfNat.ofNat.{0} Nat (nat_lit 1) (instOfNatNat (nat_lit 1)))))
(And
(@Eq.{1} Nat
(d.natReg (@OfNat.ofNat.{0} Nat (nat_lit 7) (instOfNatNat (nat_lit 7))))
(c.natReg (@OfNat.ofNat.{0} Nat (nat_lit 7) (instOfNatNat (nat_lit 7)))))
(@Eq.{1} Real
(d.realReg (@OfNat.ofNat.{0} Nat (nat_lit 7) (instOfNatNat (nat_lit 7))))
(c.realReg
(@OfNat.ofNat.{0} Nat (nat_lit 7) (instOfNatNat (nat_lit 7))))))))))))))) ∧ (((∀ {base F : Nat} {c g : DecrAlmostLinearSSSP.Decremental.Machine},
DecrAlmostLinearSSSP.Decremental.ShadowRep base F c g →
∀ (host : DecrAlmostLinearSSSP.Decremental.Program) (width offset target : Nat),
@Eq.{1} Bool c.halted Bool.false →
@Eq.{1} Nat (c.natReg (@OfNat.ofNat.{0} Nat (nat_lit 1) (instOfNatNat (nat_lit 1))))
(@OfNat.ofNat.{0} Nat (nat_lit 1) (instOfNatNat (nat_lit 1))) →
@Eq.{1} (Option.{0} DecrAlmostLinearSSSP.Decremental.Instruction)
(@GetElem?.getElem?.{0, 0, 0} (List.{0} DecrAlmostLinearSSSP.Decremental.Instruction) Nat
DecrAlmostLinearSSSP.Decremental.Instruction
(fun as i =>
@LT.lt.{0} Nat instLTNat i (@List.length.{0} DecrAlmostLinearSSSP.Decremental.Instruction as))
(@List.instGetElem?NatLtLength.{0} DecrAlmostLinearSSSP.Decremental.Instruction) host.code c.pc)
(@Option.some.{0} DecrAlmostLinearSSSP.Decremental.Instruction
(DecrAlmostLinearSSSP.Decremental.Instruction.natural
(@OfNat.ofNat.{0} Nat (nat_lit 2) (instOfNatNat (nat_lit 2)))
(@HAdd.hAdd.{0, 0, 0} Nat Nat Nat (@instHAdd.{0} Nat instAddNat) g.pc
(@OfNat.ofNat.{0} Nat (nat_lit 1) (instOfNatNat (nat_lit 1)))))) →
@Eq.{1} (Option.{0} DecrAlmostLinearSSSP.Decremental.Instruction)
(@GetElem?.getElem?.{0, 0, 0} (List.{0} DecrAlmostLinearSSSP.Decremental.Instruction) Nat
DecrAlmostLinearSSSP.Decremental.Instruction
(fun as i =>
@LT.lt.{0} Nat instLTNat i (@List.length.{0} DecrAlmostLinearSSSP.Decremental.Instruction as))
(@List.instGetElem?NatLtLength.{0} DecrAlmostLinearSSSP.Decremental.Instruction) host.code
(@HAdd.hAdd.{0, 0, 0} Nat Nat Nat (@instHAdd.{0} Nat instAddNat) c.pc
(@OfNat.ofNat.{0} Nat (nat_lit 1) (instOfNatNat (nat_lit 1)))))
(@Option.some.{0} DecrAlmostLinearSSSP.Decremental.Instruction
(DecrAlmostLinearSSSP.Decremental.Instruction.nadd
(@OfNat.ofNat.{0} Nat (nat_lit 3) (instOfNatNat (nat_lit 3)))
(@OfNat.ofNat.{0} Nat (nat_lit 3) (instOfNatNat (nat_lit 3)))
(@OfNat.ofNat.{0} Nat (nat_lit 1) (instOfNatNat (nat_lit 1))))) →
@Eq.{1} (Option.{0} DecrAlmostLinearSSSP.Decremental.Instruction)
(@GetElem?.getElem?.{0, 0, 0} (List.{0} DecrAlmostLinearSSSP.Decremental.Instruction) Nat
DecrAlmostLinearSSSP.Decremental.Instruction
(fun as i =>
@LT.lt.{0} Nat instLTNat i (@List.length.{0} DecrAlmostLinearSSSP.Decremental.Instruction as))
(@List.instGetElem?NatLtLength.{0} DecrAlmostLinearSSSP.Decremental.Instruction) host.code
(@HAdd.hAdd.{0, 0, 0} Nat Nat Nat (@instHAdd.{0} Nat instAddNat) c.pc
(@OfNat.ofNat.{0} Nat (nat_lit 2) (instOfNatNat (nat_lit 2)))))
(@Option.some.{0} DecrAlmostLinearSSSP.Decremental.Instruction
(DecrAlmostLinearSSSP.Decremental.Instruction.natural
(@OfNat.ofNat.{0} Nat (nat_lit 2) (instOfNatNat (nat_lit 2))) target)) →
@Eq.{1} (Option.{0} DecrAlmostLinearSSSP.Decremental.Instruction)
(@GetElem?.getElem?.{0, 0, 0} (List.{0} DecrAlmostLinearSSSP.Decremental.Instruction) Nat
DecrAlmostLinearSSSP.Decremental.Instruction
(fun as i =>
@LT.lt.{0} Nat instLTNat i (@List.length.{0} DecrAlmostLinearSSSP.Decremental.Instruction as))
(@List.instGetElem?NatLtLength.{0} DecrAlmostLinearSSSP.Decremental.Instruction) host.code
(@HAdd.hAdd.{0, 0, 0} Nat Nat Nat (@instHAdd.{0} Nat instAddNat) c.pc
(@OfNat.ofNat.{0} Nat (nat_lit 3) (instOfNatNat (nat_lit 3)))))
(@Option.some.{0} DecrAlmostLinearSSSP.Decremental.Instruction
(DecrAlmostLinearSSSP.Decremental.Instruction.jump
(@HAdd.hAdd.{0, 0, 0} Nat Nat Nat (@instHAdd.{0} Nat instAddNat) offset
(@HMul.hMul.{0, 0, 0} Nat Nat Nat (@instHMul.{0} Nat instMulNat) width target)))) →
∃ d,
And
(@Eq.{1} DecrAlmostLinearSSSP.Decremental.Machine
(DecrAlmostLinearSSSP.Decremental.execute host c
(@OfNat.ofNat.{0} Nat (nat_lit 4) (instOfNatNat (nat_lit 4))))
d)
(And
(DecrAlmostLinearSSSP.Decremental.ShadowRep base F d
(DecrAlmostLinearSSSP.Decremental.instructionEffect
(DecrAlmostLinearSSSP.Decremental.Instruction.jump target)
{
pc :=
@HAdd.hAdd.{0, 0, 0} Nat Nat Nat (@instHAdd.{0} Nat instAddNat) g.pc
(@OfNat.ofNat.{0} Nat (nat_lit 1) (instOfNatNat (nat_lit 1))),
realReg := g.realReg, natReg := g.natReg, realMem := g.realMem, natMem := g.natMem,
halted := g.halted, fault := g.fault,
work :=
@HAdd.hAdd.{0, 0, 0} Nat Nat Nat (@instHAdd.{0} Nat instAddNat) g.work
(@OfNat.ofNat.{0} Nat (nat_lit 1) (instOfNatNat (nat_lit 1))) }))
(And
(@Eq.{1} Nat d.pc
(@HAdd.hAdd.{0, 0, 0} Nat Nat Nat (@instHAdd.{0} Nat instAddNat) offset
(@HMul.hMul.{0, 0, 0} Nat Nat Nat (@instHMul.{0} Nat instMulNat) width target)))
(And
(@Eq.{1} Nat d.work
(@HAdd.hAdd.{0, 0, 0} Nat Nat Nat (@instHAdd.{0} Nat instAddNat) c.work
(@OfNat.ofNat.{0} Nat (nat_lit 4) (instOfNatNat (nat_lit 4)))))
(And (@Eq.{1} Bool d.halted Bool.false)
(And
(@Eq.{1} Nat (d.natReg (@OfNat.ofNat.{0} Nat (nat_lit 0) (instOfNatNat (nat_lit 0))))
(c.natReg (@OfNat.ofNat.{0} Nat (nat_lit 0) (instOfNatNat (nat_lit 0)))))
(And
(@Eq.{1} Nat (d.natReg (@OfNat.ofNat.{0} Nat (nat_lit 1) (instOfNatNat (nat_lit 1))))
(c.natReg (@OfNat.ofNat.{0} Nat (nat_lit 1) (instOfNatNat (nat_lit 1)))))
(And
(@Eq.{1} Nat
(d.natReg (@OfNat.ofNat.{0} Nat (nat_lit 7) (instOfNatNat (nat_lit 7))))
(c.natReg (@OfNat.ofNat.{0} Nat (nat_lit 7) (instOfNatNat (nat_lit 7)))))
(@Eq.{1} Real
(d.realReg (@OfNat.ofNat.{0} Nat (nat_lit 7) (instOfNatNat (nat_lit 7))))
(c.realReg (@OfNat.ofNat.{0} Nat (nat_lit 7) (instOfNatNat (nat_lit 7))))))))))))) ∧ (∀ {base F : Nat} {c g : DecrAlmostLinearSSSP.Decremental.Machine},
DecrAlmostLinearSSSP.Decremental.ShadowRep base F c g →
∀ (host : DecrAlmostLinearSSSP.Decremental.Program) (returnPC : Nat),
@Eq.{1} Bool c.halted Bool.false →
@Eq.{1} Nat (c.natReg (@OfNat.ofNat.{0} Nat (nat_lit 1) (instOfNatNat (nat_lit 1))))
(@OfNat.ofNat.{0} Nat (nat_lit 1) (instOfNatNat (nat_lit 1))) →
@Eq.{1} (Option.{0} DecrAlmostLinearSSSP.Decremental.Instruction)
(@GetElem?.getElem?.{0, 0, 0} (List.{0} DecrAlmostLinearSSSP.Decremental.Instruction) Nat
DecrAlmostLinearSSSP.Decremental.Instruction
(fun as i =>
@LT.lt.{0} Nat instLTNat i (@List.length.{0} DecrAlmostLinearSSSP.Decremental.Instruction as))
(@List.instGetElem?NatLtLength.{0} DecrAlmostLinearSSSP.Decremental.Instruction) host.code c.pc)
(@Option.some.{0} DecrAlmostLinearSSSP.Decremental.Instruction
(DecrAlmostLinearSSSP.Decremental.Instruction.natural
(@OfNat.ofNat.{0} Nat (nat_lit 2) (instOfNatNat (nat_lit 2)))
(@HAdd.hAdd.{0, 0, 0} Nat Nat Nat (@instHAdd.{0} Nat instAddNat) g.pc
(@OfNat.ofNat.{0} Nat (nat_lit 1) (instOfNatNat (nat_lit 1)))))) →
@Eq.{1} (Option.{0} DecrAlmostLinearSSSP.Decremental.Instruction)
(@GetElem?.getElem?.{0, 0, 0} (List.{0} DecrAlmostLinearSSSP.Decremental.Instruction) Nat
DecrAlmostLinearSSSP.Decremental.Instruction
(fun as i =>
@LT.lt.{0} Nat instLTNat i (@List.length.{0} DecrAlmostLinearSSSP.Decremental.Instruction as))
(@List.instGetElem?NatLtLength.{0} DecrAlmostLinearSSSP.Decremental.Instruction) host.code
(@HAdd.hAdd.{0, 0, 0} Nat Nat Nat (@instHAdd.{0} Nat instAddNat) c.pc
(@OfNat.ofNat.{0} Nat (nat_lit 1) (instOfNatNat (nat_lit 1)))))
(@Option.some.{0} DecrAlmostLinearSSSP.Decremental.Instruction
(DecrAlmostLinearSSSP.Decremental.Instruction.nadd
(@OfNat.ofNat.{0} Nat (nat_lit 3) (instOfNatNat (nat_lit 3)))
(@OfNat.ofNat.{0} Nat (nat_lit 3) (instOfNatNat (nat_lit 3)))
(@OfNat.ofNat.{0} Nat (nat_lit 1) (instOfNatNat (nat_lit 1))))) →
@Eq.{1} (Option.{0} DecrAlmostLinearSSSP.Decremental.Instruction)
(@GetElem?.getElem?.{0, 0, 0} (List.{0} DecrAlmostLinearSSSP.Decremental.Instruction) Nat
DecrAlmostLinearSSSP.Decremental.Instruction
(fun as i =>
@LT.lt.{0} Nat instLTNat i (@List.length.{0} DecrAlmostLinearSSSP.Decremental.Instruction as))
(@List.instGetElem?NatLtLength.{0} DecrAlmostLinearSSSP.Decremental.Instruction) host.code
(@HAdd.hAdd.{0, 0, 0} Nat Nat Nat (@instHAdd.{0} Nat instAddNat) c.pc
(@OfNat.ofNat.{0} Nat (nat_lit 2) (instOfNatNat (nat_lit 2)))))
(@Option.some.{0} DecrAlmostLinearSSSP.Decremental.Instruction
(DecrAlmostLinearSSSP.Decremental.Instruction.natural
(@OfNat.ofNat.{0} Nat (nat_lit 4) (instOfNatNat (nat_lit 4)))
(@OfNat.ofNat.{0} Nat (nat_lit 1) (instOfNatNat (nat_lit 1))))) →
@Eq.{1} (Option.{0} DecrAlmostLinearSSSP.Decremental.Instruction)
(@GetElem?.getElem?.{0, 0, 0} (List.{0} DecrAlmostLinearSSSP.Decremental.Instruction) Nat
DecrAlmostLinearSSSP.Decremental.Instruction
(fun as i =>
@LT.lt.{0} Nat instLTNat i (@List.length.{0} DecrAlmostLinearSSSP.Decremental.Instruction as))
(@List.instGetElem?NatLtLength.{0} DecrAlmostLinearSSSP.Decremental.Instruction) host.code
(@HAdd.hAdd.{0, 0, 0} Nat Nat Nat (@instHAdd.{0} Nat instAddNat) c.pc
(@OfNat.ofNat.{0} Nat (nat_lit 3) (instOfNatNat (nat_lit 3)))))
(@Option.some.{0} DecrAlmostLinearSSSP.Decremental.Instruction
(DecrAlmostLinearSSSP.Decremental.Instruction.jump returnPC)) →
∃ d,
And
(@Eq.{1} DecrAlmostLinearSSSP.Decremental.Machine
(DecrAlmostLinearSSSP.Decremental.execute host c
(@OfNat.ofNat.{0} Nat (nat_lit 4) (instOfNatNat (nat_lit 4))))
d)
(And
(DecrAlmostLinearSSSP.Decremental.ShadowRep base F d
(DecrAlmostLinearSSSP.Decremental.instructionEffect
DecrAlmostLinearSSSP.Decremental.Instruction.halt
{
pc :=
@HAdd.hAdd.{0, 0, 0} Nat Nat Nat (@instHAdd.{0} Nat instAddNat) g.pc
(@OfNat.ofNat.{0} Nat (nat_lit 1) (instOfNatNat (nat_lit 1))),
realReg := g.realReg, natReg := g.natReg, realMem := g.realMem, natMem := g.natMem,
halted := g.halted, fault := g.fault,
work :=
@HAdd.hAdd.{0, 0, 0} Nat Nat Nat (@instHAdd.{0} Nat instAddNat) g.work
(@OfNat.ofNat.{0} Nat (nat_lit 1) (instOfNatNat (nat_lit 1))) }))
(And (@Eq.{1} Nat d.pc returnPC)
(And
(@Eq.{1} Nat d.work
(@HAdd.hAdd.{0, 0, 0} Nat Nat Nat (@instHAdd.{0} Nat instAddNat) c.work
(@OfNat.ofNat.{0} Nat (nat_lit 4) (instOfNatNat (nat_lit 4)))))
(And (@Eq.{1} Bool d.halted Bool.false)
(And
(@Eq.{1} Nat (d.natReg (@OfNat.ofNat.{0} Nat (nat_lit 0) (instOfNatNat (nat_lit 0))))
(c.natReg (@OfNat.ofNat.{0} Nat (nat_lit 0) (instOfNatNat (nat_lit 0)))))
(And
(@Eq.{1} Nat (d.natReg (@OfNat.ofNat.{0} Nat (nat_lit 1) (instOfNatNat (nat_lit 1))))
(c.natReg (@OfNat.ofNat.{0} Nat (nat_lit 1) (instOfNatNat (nat_lit 1)))))
(And
(@Eq.{1} Nat
(d.natReg (@OfNat.ofNat.{0} Nat (nat_lit 7) (instOfNatNat (nat_lit 7))))
(c.natReg (@OfNat.ofNat.{0} Nat (nat_lit 7) (instOfNatNat (nat_lit 7)))))
(@Eq.{1} Real
(d.realReg (@OfNat.ofNat.{0} Nat (nat_lit 7) (instOfNatNat (nat_lit 7))))
(c.realReg (@OfNat.ofNat.{0} Nat (nat_lit 7) (instOfNatNat (nat_lit 7)))))))))))))) ∧ ((∀ {base F : Nat} {c g : DecrAlmostLinearSSSP.Decremental.Machine},
DecrAlmostLinearSSSP.Decremental.ShadowRep base F c g →
∀ (host : DecrAlmostLinearSSSP.Decremental.Program),
@LT.lt.{0} Nat instLTNat (@OfNat.ofNat.{0} Nat (nat_lit 0) (instOfNatNat (nat_lit 0))) F →
∀ (natural : Bool) (a b target : Nat),
@Eq.{1} Bool c.halted Bool.false →
@Eq.{1} (Option.{0} DecrAlmostLinearSSSP.Decremental.Instruction)
(@GetElem?.getElem?.{0, 0, 0} (List.{0} DecrAlmostLinearSSSP.Decremental.Instruction) Nat
DecrAlmostLinearSSSP.Decremental.Instruction
(fun as i =>
@LT.lt.{0} Nat instLTNat i (@List.length.{0} DecrAlmostLinearSSSP.Decremental.Instruction as))
(@List.instGetElem?NatLtLength.{0} DecrAlmostLinearSSSP.Decremental.Instruction) host.code c.pc)
(@Option.some.{0} DecrAlmostLinearSSSP.Decremental.Instruction
(DecrAlmostLinearSSSP.Decremental.branchInstruction natural
(DecrAlmostLinearSSSP.Decremental.shadowReg a) (DecrAlmostLinearSSSP.Decremental.shadowReg b)
target)) →
@Eq.{1} DecrAlmostLinearSSSP.Decremental.Machine
(DecrAlmostLinearSSSP.Decremental.execute host c
(@OfNat.ofNat.{0} Nat (nat_lit 1) (instOfNatNat (nat_lit 1))))
{
pc :=
@ite.{1} Nat (DecrAlmostLinearSSSP.Decremental.branchTest natural g a b)
(Classical.propDecidable (DecrAlmostLinearSSSP.Decremental.branchTest natural g a b)) target
(@HAdd.hAdd.{0, 0, 0} Nat Nat Nat (@instHAdd.{0} Nat instAddNat) c.pc
(@OfNat.ofNat.{0} Nat (nat_lit 1) (instOfNatNat (nat_lit 1)))),
realReg := c.realReg, natReg := c.natReg, realMem := c.realMem, natMem := c.natMem,
halted := c.halted, fault := c.fault,
work :=
@HAdd.hAdd.{0, 0, 0} Nat Nat Nat (@instHAdd.{0} Nat instAddNat) c.work
(@OfNat.ofNat.{0} Nat (nat_lit 1) (instOfNatNat (nat_lit 1))) }) ∧ ((∀ {base F : Nat} {c g : DecrAlmostLinearSSSP.Decremental.Machine},
DecrAlmostLinearSSSP.Decremental.ShadowRep base F c g →
∀ (host : DecrAlmostLinearSSSP.Decremental.Program) (width offset target : Nat),
@LT.lt.{0} Nat instLTNat (@OfNat.ofNat.{0} Nat (nat_lit 0) (instOfNatNat (nat_lit 0))) F →
∀ (natural : Bool) (a b : Nat),
@Eq.{1} Bool c.halted Bool.false →
@Eq.{1} Nat (c.natReg (@OfNat.ofNat.{0} Nat (nat_lit 1) (instOfNatNat (nat_lit 1))))
(@OfNat.ofNat.{0} Nat (nat_lit 1) (instOfNatNat (nat_lit 1))) →
@Eq.{1} (Option.{0} DecrAlmostLinearSSSP.Decremental.Instruction)
(@GetElem?.getElem?.{0, 0, 0} (List.{0} DecrAlmostLinearSSSP.Decremental.Instruction) Nat
DecrAlmostLinearSSSP.Decremental.Instruction
(fun as i =>
@LT.lt.{0} Nat instLTNat i (@List.length.{0} DecrAlmostLinearSSSP.Decremental.Instruction as))
(@List.instGetElem?NatLtLength.{0} DecrAlmostLinearSSSP.Decremental.Instruction) host.code c.pc)
(@Option.some.{0} DecrAlmostLinearSSSP.Decremental.Instruction
(DecrAlmostLinearSSSP.Decremental.Instruction.natural
(@OfNat.ofNat.{0} Nat (nat_lit 2) (instOfNatNat (nat_lit 2)))
(@HAdd.hAdd.{0, 0, 0} Nat Nat Nat (@instHAdd.{0} Nat instAddNat) g.pc
(@OfNat.ofNat.{0} Nat (nat_lit 1) (instOfNatNat (nat_lit 1)))))) →
@Eq.{1} (Option.{0} DecrAlmostLinearSSSP.Decremental.Instruction)
(@GetElem?.getElem?.{0, 0, 0} (List.{0} DecrAlmostLinearSSSP.Decremental.Instruction) Nat
DecrAlmostLinearSSSP.Decremental.Instruction
(fun as i =>
@LT.lt.{0} Nat instLTNat i (@List.length.{0} DecrAlmostLinearSSSP.Decremental.Instruction as))
(@List.instGetElem?NatLtLength.{0} DecrAlmostLinearSSSP.Decremental.Instruction) host.code
(@HAdd.hAdd.{0, 0, 0} Nat Nat Nat (@instHAdd.{0} Nat instAddNat) c.pc
(@OfNat.ofNat.{0} Nat (nat_lit 1) (instOfNatNat (nat_lit 1)))))
(@Option.some.{0} DecrAlmostLinearSSSP.Decremental.Instruction
(DecrAlmostLinearSSSP.Decremental.Instruction.nadd
(@OfNat.ofNat.{0} Nat (nat_lit 3) (instOfNatNat (nat_lit 3)))
(@OfNat.ofNat.{0} Nat (nat_lit 3) (instOfNatNat (nat_lit 3)))
(@OfNat.ofNat.{0} Nat (nat_lit 1) (instOfNatNat (nat_lit 1))))) →
@Eq.{1} (Option.{0} DecrAlmostLinearSSSP.Decremental.Instruction)
(@GetElem?.getElem?.{0, 0, 0} (List.{0} DecrAlmostLinearSSSP.Decremental.Instruction) Nat
DecrAlmostLinearSSSP.Decremental.Instruction
(fun as i =>
@LT.lt.{0} Nat instLTNat i (@List.length.{0} DecrAlmostLinearSSSP.Decremental.Instruction as))
(@List.instGetElem?NatLtLength.{0} DecrAlmostLinearSSSP.Decremental.Instruction) host.code
(@HAdd.hAdd.{0, 0, 0} Nat Nat Nat (@instHAdd.{0} Nat instAddNat) c.pc
(@OfNat.ofNat.{0} Nat (nat_lit 2) (instOfNatNat (nat_lit 2)))))
(@Option.some.{0} DecrAlmostLinearSSSP.Decremental.Instruction
(DecrAlmostLinearSSSP.Decremental.branchInstruction natural
(DecrAlmostLinearSSSP.Decremental.shadowReg a) (DecrAlmostLinearSSSP.Decremental.shadowReg b)
(@HAdd.hAdd.{0, 0, 0} Nat Nat Nat (@instHAdd.{0} Nat instAddNat) c.pc
(@OfNat.ofNat.{0} Nat (nat_lit 5) (instOfNatNat (nat_lit 5)))))) →
@Eq.{1} (Option.{0} DecrAlmostLinearSSSP.Decremental.Instruction)
(@GetElem?.getElem?.{0, 0, 0} (List.{0} DecrAlmostLinearSSSP.Decremental.Instruction) Nat
DecrAlmostLinearSSSP.Decremental.Instruction
(fun as i =>
@LT.lt.{0} Nat instLTNat i
(@List.length.{0} DecrAlmostLinearSSSP.Decremental.Instruction as))
(@List.instGetElem?NatLtLength.{0} DecrAlmostLinearSSSP.Decremental.Instruction) host.code
(@HAdd.hAdd.{0, 0, 0} Nat Nat Nat (@instHAdd.{0} Nat instAddNat) c.pc
(@OfNat.ofNat.{0} Nat (nat_lit 3) (instOfNatNat (nat_lit 3)))))
(@Option.some.{0} DecrAlmostLinearSSSP.Decremental.Instruction
(DecrAlmostLinearSSSP.Decremental.Instruction.jump
(@HAdd.hAdd.{0, 0, 0} Nat Nat Nat (@instHAdd.{0} Nat instAddNat) offset
(@HMul.hMul.{0, 0, 0} Nat Nat Nat (@instHMul.{0} Nat instMulNat) width
(@HAdd.hAdd.{0, 0, 0} Nat Nat Nat (@instHAdd.{0} Nat instAddNat) g.pc
(@OfNat.ofNat.{0} Nat (nat_lit 1) (instOfNatNat (nat_lit 1)))))))) →
@Eq.{1} (Option.{0} DecrAlmostLinearSSSP.Decremental.Instruction)
(@GetElem?.getElem?.{0, 0, 0} (List.{0} DecrAlmostLinearSSSP.Decremental.Instruction) Nat
DecrAlmostLinearSSSP.Decremental.Instruction
(fun as i =>
@LT.lt.{0} Nat instLTNat i
(@List.length.{0} DecrAlmostLinearSSSP.Decremental.Instruction as))
(@List.instGetElem?NatLtLength.{0} DecrAlmostLinearSSSP.Decremental.Instruction) host.code
(@HAdd.hAdd.{0, 0, 0} Nat Nat Nat (@instHAdd.{0} Nat instAddNat) c.pc
(@OfNat.ofNat.{0} Nat (nat_lit 5) (instOfNatNat (nat_lit 5)))))
(@Option.some.{0} DecrAlmostLinearSSSP.Decremental.Instruction
(DecrAlmostLinearSSSP.Decremental.Instruction.natural
(@OfNat.ofNat.{0} Nat (nat_lit 2) (instOfNatNat (nat_lit 2))) target)) →
@Eq.{1} (Option.{0} DecrAlmostLinearSSSP.Decremental.Instruction)
(@GetElem?.getElem?.{0, 0, 0} (List.{0} DecrAlmostLinearSSSP.Decremental.Instruction) Nat
DecrAlmostLinearSSSP.Decremental.Instruction
(fun as i =>
@LT.lt.{0} Nat instLTNat i
(@List.length.{0} DecrAlmostLinearSSSP.Decremental.Instruction as))
(@List.instGetElem?NatLtLength.{0} DecrAlmostLinearSSSP.Decremental.Instruction) host.code
(@HAdd.hAdd.{0, 0, 0} Nat Nat Nat (@instHAdd.{0} Nat instAddNat) c.pc
(@OfNat.ofNat.{0} Nat (nat_lit 6) (instOfNatNat (nat_lit 6)))))
(@Option.some.{0} DecrAlmostLinearSSSP.Decremental.Instruction
(DecrAlmostLinearSSSP.Decremental.Instruction.jump
(@HAdd.hAdd.{0, 0, 0} Nat Nat Nat (@instHAdd.{0} Nat instAddNat) offset
(@HMul.hMul.{0, 0, 0} Nat Nat Nat (@instHMul.{0} Nat instMulNat) width target)))) →
∃ steps d,
And
(@LE.le.{0} Nat instLENat steps
(@OfNat.ofNat.{0} Nat (nat_lit 5) (instOfNatNat (nat_lit 5))))
(And
(@Eq.{1} DecrAlmostLinearSSSP.Decremental.Machine
(DecrAlmostLinearSSSP.Decremental.execute host c steps) d)
(And
(DecrAlmostLinearSSSP.Decremental.ShadowRep base F d
(DecrAlmostLinearSSSP.Decremental.instructionEffect
(DecrAlmostLinearSSSP.Decremental.branchInstruction natural a b target)
{
pc :=
@HAdd.hAdd.{0, 0, 0} Nat Nat Nat (@instHAdd.{0} Nat instAddNat) g.pc
(@OfNat.ofNat.{0} Nat (nat_lit 1) (instOfNatNat (nat_lit 1))),
realReg := g.realReg, natReg := g.natReg, realMem := g.realMem,
natMem := g.natMem, halted := g.halted, fault := g.fault,
work :=
@HAdd.hAdd.{0, 0, 0} Nat Nat Nat (@instHAdd.{0} Nat instAddNat) g.work
(@OfNat.ofNat.{0} Nat (nat_lit 1) (instOfNatNat (nat_lit 1))) }))
(And
(@Eq.{1} Nat d.pc
(@ite.{1} Nat (DecrAlmostLinearSSSP.Decremental.branchTest natural g a b)
(Classical.propDecidable
(DecrAlmostLinearSSSP.Decremental.branchTest natural g a b))
(@HAdd.hAdd.{0, 0, 0} Nat Nat Nat (@instHAdd.{0} Nat instAddNat) offset
(@HMul.hMul.{0, 0, 0} Nat Nat Nat (@instHMul.{0} Nat instMulNat) width
target))
(@HAdd.hAdd.{0, 0, 0} Nat Nat Nat (@instHAdd.{0} Nat instAddNat) offset
(@HMul.hMul.{0, 0, 0} Nat Nat Nat (@instHMul.{0} Nat instMulNat) width
(@HAdd.hAdd.{0, 0, 0} Nat Nat Nat (@instHAdd.{0} Nat instAddNat) g.pc
(@OfNat.ofNat.{0} Nat (nat_lit 1) (instOfNatNat (nat_lit 1))))))))
(And
(@Eq.{1} Nat d.work
(@HAdd.hAdd.{0, 0, 0} Nat Nat Nat (@instHAdd.{0} Nat instAddNat) c.work steps))
(And (@Eq.{1} Bool d.halted Bool.false)
(And
(@Eq.{1} Nat
(d.natReg (@OfNat.ofNat.{0} Nat (nat_lit 0) (instOfNatNat (nat_lit 0))))
(c.natReg (@OfNat.ofNat.{0} Nat (nat_lit 0) (instOfNatNat (nat_lit 0)))))
(And
(@Eq.{1} Nat
(d.natReg (@OfNat.ofNat.{0} Nat (nat_lit 1) (instOfNatNat (nat_lit 1))))
(c.natReg (@OfNat.ofNat.{0} Nat (nat_lit 1) (instOfNatNat (nat_lit 1)))))
(And
(@Eq.{1} Nat
(d.natReg (@OfNat.ofNat.{0} Nat (nat_lit 7) (instOfNatNat (nat_lit 7))))
(c.natReg
(@OfNat.ofNat.{0} Nat (nat_lit 7) (instOfNatNat (nat_lit 7)))))
(And
(@Eq.{1} Real
(d.realReg
(@OfNat.ofNat.{0} Nat (nat_lit 7) (instOfNatNat (nat_lit 7))))
(c.realReg
(@OfNat.ofNat.{0} Nat (nat_lit 7) (instOfNatNat (nat_lit 7)))))
(@Eq.{1} Nat steps
(@ite.{1} Nat
(DecrAlmostLinearSSSP.Decremental.branchTest natural g a b)
(Classical.propDecidable
(DecrAlmostLinearSSSP.Decremental.branchTest natural g a b))
(@OfNat.ofNat.{0} Nat (nat_lit 5) (instOfNatNat (nat_lit 5)))
(@OfNat.ofNat.{0} Nat (nat_lit 4)
(instOfNatNat (nat_lit 4))))))))))))))) ∧ (∀ {base F : Nat} {c g : DecrAlmostLinearSSSP.Decremental.Machine},
DecrAlmostLinearSSSP.Decremental.ShadowRep base F c g →
∀ (host : DecrAlmostLinearSSSP.Decremental.Program) (width offset d q : Nat),
@Eq.{1} Bool c.halted Bool.false →
@Eq.{1} Nat (c.natReg (@OfNat.ofNat.{0} Nat (nat_lit 1) (instOfNatNat (nat_lit 1))))
(@OfNat.ofNat.{0} Nat (nat_lit 1) (instOfNatNat (nat_lit 1))) →
@Eq.{1} Nat (c.natReg (@OfNat.ofNat.{0} Nat (nat_lit 7) (instOfNatNat (nat_lit 7)))) F →
@Eq.{1} (Option.{0} DecrAlmostLinearSSSP.Decremental.Instruction)
(@GetElem?.getElem?.{0, 0, 0} (List.{0} DecrAlmostLinearSSSP.Decremental.Instruction) Nat
DecrAlmostLinearSSSP.Decremental.Instruction
(fun as i =>
@LT.lt.{0} Nat instLTNat i (@List.length.{0} DecrAlmostLinearSSSP.Decremental.Instruction as))
(@List.instGetElem?NatLtLength.{0} DecrAlmostLinearSSSP.Decremental.Instruction) host.code c.pc)
(@Option.some.{0} DecrAlmostLinearSSSP.Decremental.Instruction
(DecrAlmostLinearSSSP.Decremental.Instruction.natural
(@OfNat.ofNat.{0} Nat (nat_lit 2) (instOfNatNat (nat_lit 2)))
(@HAdd.hAdd.{0, 0, 0} Nat Nat Nat (@instHAdd.{0} Nat instAddNat) g.pc
(@OfNat.ofNat.{0} Nat (nat_lit 1) (instOfNatNat (nat_lit 1)))))) →
@Eq.{1} (Option.{0} DecrAlmostLinearSSSP.Decremental.Instruction)
(@GetElem?.getElem?.{0, 0, 0} (List.{0} DecrAlmostLinearSSSP.Decremental.Instruction) Nat
DecrAlmostLinearSSSP.Decremental.Instruction
(fun as i =>
@LT.lt.{0} Nat instLTNat i (@List.length.{0} DecrAlmostLinearSSSP.Decremental.Instruction as))
(@List.instGetElem?NatLtLength.{0} DecrAlmostLinearSSSP.Decremental.Instruction) host.code
(@HAdd.hAdd.{0, 0, 0} Nat Nat Nat (@instHAdd.{0} Nat instAddNat) c.pc
(@OfNat.ofNat.{0} Nat (nat_lit 1) (instOfNatNat (nat_lit 1)))))
(@Option.some.{0} DecrAlmostLinearSSSP.Decremental.Instruction
(DecrAlmostLinearSSSP.Decremental.Instruction.nadd
(@OfNat.ofNat.{0} Nat (nat_lit 3) (instOfNatNat (nat_lit 3)))
(@OfNat.ofNat.{0} Nat (nat_lit 3) (instOfNatNat (nat_lit 3)))
(@OfNat.ofNat.{0} Nat (nat_lit 1) (instOfNatNat (nat_lit 1))))) →
@Eq.{1} (Option.{0} DecrAlmostLinearSSSP.Decremental.Instruction)
(@GetElem?.getElem?.{0, 0, 0} (List.{0} DecrAlmostLinearSSSP.Decremental.Instruction) Nat
DecrAlmostLinearSSSP.Decremental.Instruction
(fun as i =>
@LT.lt.{0} Nat instLTNat i (@List.length.{0} DecrAlmostLinearSSSP.Decremental.Instruction as))
(@List.instGetElem?NatLtLength.{0} DecrAlmostLinearSSSP.Decremental.Instruction) host.code
(@HAdd.hAdd.{0, 0, 0} Nat Nat Nat (@instHAdd.{0} Nat instAddNat) c.pc
(@OfNat.ofNat.{0} Nat (nat_lit 2) (instOfNatNat (nat_lit 2)))))
(@Option.some.{0} DecrAlmostLinearSSSP.Decremental.Instruction
(DecrAlmostLinearSSSP.Decremental.Instruction.natural
(DecrAlmostLinearSSSP.Decremental.shadowReg d)
(@OfNat.ofNat.{0} Nat (nat_lit 0) (instOfNatNat (nat_lit 0))))) →
(∀ (j : Nat),
@LT.lt.{0} Nat instLTNat j q →
@Eq.{1} (Option.{0} DecrAlmostLinearSSSP.Decremental.Instruction)
(@GetElem?.getElem?.{0, 0, 0} (List.{0} DecrAlmostLinearSSSP.Decremental.Instruction) Nat
DecrAlmostLinearSSSP.Decremental.Instruction
(fun as i =>
@LT.lt.{0} Nat instLTNat i
(@List.length.{0} DecrAlmostLinearSSSP.Decremental.Instruction as))
(@List.instGetElem?NatLtLength.{0} DecrAlmostLinearSSSP.Decremental.Instruction) host.code
(@HAdd.hAdd.{0, 0, 0} Nat Nat Nat (@instHAdd.{0} Nat instAddNat)
(@HAdd.hAdd.{0, 0, 0} Nat Nat Nat (@instHAdd.{0} Nat instAddNat) c.pc
(@OfNat.ofNat.{0} Nat (nat_lit 3) (instOfNatNat (nat_lit 3))))
j))
(@Option.some.{0} DecrAlmostLinearSSSP.Decremental.Instruction
(DecrAlmostLinearSSSP.Decremental.Instruction.nadd
(DecrAlmostLinearSSSP.Decremental.shadowReg d)
(DecrAlmostLinearSSSP.Decremental.shadowReg d)
(@OfNat.ofNat.{0} Nat (nat_lit 7) (instOfNatNat (nat_lit 7)))))) →
@Eq.{1} (Option.{0} DecrAlmostLinearSSSP.Decremental.Instruction)
(@GetElem?.getElem?.{0, 0, 0} (List.{0} DecrAlmostLinearSSSP.Decremental.Instruction) Nat
DecrAlmostLinearSSSP.Decremental.Instruction
(fun as i =>
@LT.lt.{0} Nat instLTNat i
(@List.length.{0} DecrAlmostLinearSSSP.Decremental.Instruction as))
(@List.instGetElem?NatLtLength.{0} DecrAlmostLinearSSSP.Decremental.Instruction) host.code
(@HAdd.hAdd.{0, 0, 0} Nat Nat Nat (@instHAdd.{0} Nat instAddNat) c.pc
(@HAdd.hAdd.{0, 0, 0} Nat Nat Nat (@instHAdd.{0} Nat instAddNat) q
(@OfNat.ofNat.{0} Nat (nat_lit 3) (instOfNatNat (nat_lit 3))))))
(@Option.some.{0} DecrAlmostLinearSSSP.Decremental.Instruction
(DecrAlmostLinearSSSP.Decremental.Instruction.jump
(@HAdd.hAdd.{0, 0, 0} Nat Nat Nat (@instHAdd.{0} Nat instAddNat) offset
(@HMul.hMul.{0, 0, 0} Nat Nat Nat (@instHMul.{0} Nat instMulNat) width
(@HAdd.hAdd.{0, 0, 0} Nat Nat Nat (@instHAdd.{0} Nat instAddNat) g.pc
(@OfNat.ofNat.{0} Nat (nat_lit 1) (instOfNatNat (nat_lit 1)))))))) →
∃ finish,
And
(@Eq.{1} DecrAlmostLinearSSSP.Decremental.Machine
(DecrAlmostLinearSSSP.Decremental.execute host c
(@HAdd.hAdd.{0, 0, 0} Nat Nat Nat (@instHAdd.{0} Nat instAddNat) q
(@OfNat.ofNat.{0} Nat (nat_lit 4) (instOfNatNat (nat_lit 4)))))
finish)
(And
(DecrAlmostLinearSSSP.Decremental.ShadowRep base F finish
(DecrAlmostLinearSSSP.Decremental.instructionEffect
(DecrAlmostLinearSSSP.Decremental.Instruction.natural d q)
{
pc :=
@HAdd.hAdd.{0, 0, 0} Nat Nat Nat (@instHAdd.{0} Nat instAddNat) g.pc
(@OfNat.ofNat.{0} Nat (nat_lit 1) (instOfNatNat (nat_lit 1))),
realReg := g.realReg, natReg := g.natReg, realMem := g.realMem, natMem := g.natMem,
halted := g.halted, fault := g.fault,
work :=
@HAdd.hAdd.{0, 0, 0} Nat Nat Nat (@instHAdd.{0} Nat instAddNat) g.work
(@OfNat.ofNat.{0} Nat (nat_lit 1) (instOfNatNat (nat_lit 1))) }))
(And
(@Eq.{1} Nat finish.pc
(@HAdd.hAdd.{0, 0, 0} Nat Nat Nat (@instHAdd.{0} Nat instAddNat) offset
(@HMul.hMul.{0, 0, 0} Nat Nat Nat (@instHMul.{0} Nat instMulNat) width
(@HAdd.hAdd.{0, 0, 0} Nat Nat Nat (@instHAdd.{0} Nat instAddNat) g.pc
(@OfNat.ofNat.{0} Nat (nat_lit 1) (instOfNatNat (nat_lit 1)))))))
(And
(@Eq.{1} Nat finish.work
(@HAdd.hAdd.{0, 0, 0} Nat Nat Nat (@instHAdd.{0} Nat instAddNat) c.work
(@HAdd.hAdd.{0, 0, 0} Nat Nat Nat (@instHAdd.{0} Nat instAddNat) q
(@OfNat.ofNat.{0} Nat (nat_lit 4) (instOfNatNat (nat_lit 4))))))
(And (@Eq.{1} Bool finish.halted Bool.false)
(And
(@Eq.{1} Nat
(finish.natReg (@OfNat.ofNat.{0} Nat (nat_lit 0) (instOfNatNat (nat_lit 0))))
(c.natReg (@OfNat.ofNat.{0} Nat (nat_lit 0) (instOfNatNat (nat_lit 0)))))
(And
(@Eq.{1} Nat
(finish.natReg (@OfNat.ofNat.{0} Nat (nat_lit 1) (instOfNatNat (nat_lit 1))))
(c.natReg (@OfNat.ofNat.{0} Nat (nat_lit 1) (instOfNatNat (nat_lit 1)))))
(And
(@Eq.{1} Nat
(finish.natReg (@OfNat.ofNat.{0} Nat (nat_lit 7) (instOfNatNat (nat_lit 7))))
(c.natReg (@OfNat.ofNat.{0} Nat (nat_lit 7) (instOfNatNat (nat_lit 7)))))
(@Eq.{1} Real
(finish.realReg (@OfNat.ofNat.{0} Nat (nat_lit 7) (instOfNatNat (nat_lit 7))))
(c.realReg
(@OfNat.ofNat.{0} Nat (nat_lit 7) (instOfNatNat (nat_lit 7))))))))))))))))) ∧ ((((∀ {base F : Nat} {c g : DecrAlmostLinearSSSP.Decremental.Machine},
DecrAlmostLinearSSSP.Decremental.ShadowRep base F c g →
∀ (host : DecrAlmostLinearSSSP.Decremental.Program),
@LT.lt.{0} Nat instLTNat (@OfNat.ofNat.{0} Nat (nat_lit 0) (instOfNatNat (nat_lit 0))) F →
∀ (d a : Nat),
@Eq.{1} Bool c.halted Bool.false →
@Eq.{1} Real (c.realReg (@OfNat.ofNat.{0} Nat (nat_lit 7) (instOfNatNat (nat_lit 7))))
(@Nat.cast.{0} Real Real.instNatCast F) →
@Eq.{1} (Option.{0} DecrAlmostLinearSSSP.Decremental.Instruction)
(@GetElem?.getElem?.{0, 0, 0} (List.{0} DecrAlmostLinearSSSP.Decremental.Instruction) Nat
DecrAlmostLinearSSSP.Decremental.Instruction
(fun as i =>
@LT.lt.{0} Nat instLTNat i (@List.length.{0} DecrAlmostLinearSSSP.Decremental.Instruction as))
(@List.instGetElem?NatLtLength.{0} DecrAlmostLinearSSSP.Decremental.Instruction) host.code c.pc)
(@Option.some.{0} DecrAlmostLinearSSSP.Decremental.Instruction
(DecrAlmostLinearSSSP.Decremental.Instruction.cast (DecrAlmostLinearSSSP.Decremental.shadowReg d)
(DecrAlmostLinearSSSP.Decremental.shadowReg a))) →
@Eq.{1} (Option.{0} DecrAlmostLinearSSSP.Decremental.Instruction)
(@GetElem?.getElem?.{0, 0, 0} (List.{0} DecrAlmostLinearSSSP.Decremental.Instruction) Nat
DecrAlmostLinearSSSP.Decremental.Instruction
(fun as i =>
@LT.lt.{0} Nat instLTNat i (@List.length.{0} DecrAlmostLinearSSSP.Decremental.Instruction as))
(@List.instGetElem?NatLtLength.{0} DecrAlmostLinearSSSP.Decremental.Instruction) host.code
(@HAdd.hAdd.{0, 0, 0} Nat Nat Nat (@instHAdd.{0} Nat instAddNat) c.pc
(@OfNat.ofNat.{0} Nat (nat_lit 1) (instOfNatNat (nat_lit 1)))))
(@Option.some.{0} DecrAlmostLinearSSSP.Decremental.Instruction
(DecrAlmostLinearSSSP.Decremental.Instruction.div (DecrAlmostLinearSSSP.Decremental.shadowReg d)
(DecrAlmostLinearSSSP.Decremental.shadowReg d)
(@OfNat.ofNat.{0} Nat (nat_lit 7) (instOfNatNat (nat_lit 7))))) →
∃ finish,
And
(@Eq.{1} DecrAlmostLinearSSSP.Decremental.Machine
(DecrAlmostLinearSSSP.Decremental.execute host c
(@OfNat.ofNat.{0} Nat (nat_lit 2) (instOfNatNat (nat_lit 2))))
finish)
(And
(DecrAlmostLinearSSSP.Decremental.ShadowRep base F finish
(DecrAlmostLinearSSSP.Decremental.instructionEffect
(DecrAlmostLinearSSSP.Decremental.Instruction.cast d a) g))
(And
(@Eq.{1} Nat finish.pc
(@HAdd.hAdd.{0, 0, 0} Nat Nat Nat (@instHAdd.{0} Nat instAddNat) c.pc
(@OfNat.ofNat.{0} Nat (nat_lit 2) (instOfNatNat (nat_lit 2)))))
(And
(@Eq.{1} Nat finish.work
(@HAdd.hAdd.{0, 0, 0} Nat Nat Nat (@instHAdd.{0} Nat instAddNat) c.work
(@OfNat.ofNat.{0} Nat (nat_lit 2) (instOfNatNat (nat_lit 2)))))
(And (@Eq.{1} Bool finish.halted Bool.false)
(And (@Eq.{1} (Nat → Nat) finish.natReg c.natReg)
(@Eq.{1} Real
(finish.realReg (@OfNat.ofNat.{0} Nat (nat_lit 7) (instOfNatNat (nat_lit 7))))
(c.realReg (@OfNat.ofNat.{0} Nat (nat_lit 7) (instOfNatNat (nat_lit 7))))))))))) ∧ (∀ {base F : Nat} {c g : DecrAlmostLinearSSSP.Decremental.Machine},
DecrAlmostLinearSSSP.Decremental.ShadowRep base F c g →
∀ (host : DecrAlmostLinearSSSP.Decremental.Program) (width offset : Nat),
@LT.lt.{0} Nat instLTNat (@OfNat.ofNat.{0} Nat (nat_lit 0) (instOfNatNat (nat_lit 0))) F →
∀ (d a : Nat),
@Eq.{1} Bool c.halted Bool.false →
@Eq.{1} Nat (c.natReg (@OfNat.ofNat.{0} Nat (nat_lit 1) (instOfNatNat (nat_lit 1))))
(@OfNat.ofNat.{0} Nat (nat_lit 1) (instOfNatNat (nat_lit 1))) →
@Eq.{1} Real (c.realReg (@OfNat.ofNat.{0} Nat (nat_lit 7) (instOfNatNat (nat_lit 7))))
(@Nat.cast.{0} Real Real.instNatCast F) →
@Eq.{1} (Option.{0} DecrAlmostLinearSSSP.Decremental.Instruction)
(@GetElem?.getElem?.{0, 0, 0} (List.{0} DecrAlmostLinearSSSP.Decremental.Instruction) Nat
DecrAlmostLinearSSSP.Decremental.Instruction
(fun as i =>
@LT.lt.{0} Nat instLTNat i (@List.length.{0} DecrAlmostLinearSSSP.Decremental.Instruction as))
(@List.instGetElem?NatLtLength.{0} DecrAlmostLinearSSSP.Decremental.Instruction) host.code c.pc)
(@Option.some.{0} DecrAlmostLinearSSSP.Decremental.Instruction
(DecrAlmostLinearSSSP.Decremental.Instruction.natural
(@OfNat.ofNat.{0} Nat (nat_lit 2) (instOfNatNat (nat_lit 2)))
(@HAdd.hAdd.{0, 0, 0} Nat Nat Nat (@instHAdd.{0} Nat instAddNat) g.pc
(@OfNat.ofNat.{0} Nat (nat_lit 1) (instOfNatNat (nat_lit 1)))))) →
@Eq.{1} (Option.{0} DecrAlmostLinearSSSP.Decremental.Instruction)
(@GetElem?.getElem?.{0, 0, 0} (List.{0} DecrAlmostLinearSSSP.Decremental.Instruction) Nat
DecrAlmostLinearSSSP.Decremental.Instruction
(fun as i =>
@LT.lt.{0} Nat instLTNat i (@List.length.{0} DecrAlmostLinearSSSP.Decremental.Instruction as))
(@List.instGetElem?NatLtLength.{0} DecrAlmostLinearSSSP.Decremental.Instruction) host.code
(@HAdd.hAdd.{0, 0, 0} Nat Nat Nat (@instHAdd.{0} Nat instAddNat) c.pc
(@OfNat.ofNat.{0} Nat (nat_lit 1) (instOfNatNat (nat_lit 1)))))
(@Option.some.{0} DecrAlmostLinearSSSP.Decremental.Instruction
(DecrAlmostLinearSSSP.Decremental.Instruction.nadd
(@OfNat.ofNat.{0} Nat (nat_lit 3) (instOfNatNat (nat_lit 3)))
(@OfNat.ofNat.{0} Nat (nat_lit 3) (instOfNatNat (nat_lit 3)))
(@OfNat.ofNat.{0} Nat (nat_lit 1) (instOfNatNat (nat_lit 1))))) →
@Eq.{1} (Option.{0} DecrAlmostLinearSSSP.Decremental.Instruction)
(@GetElem?.getElem?.{0, 0, 0} (List.{0} DecrAlmostLinearSSSP.Decremental.Instruction) Nat
DecrAlmostLinearSSSP.Decremental.Instruction
(fun as i =>
@LT.lt.{0} Nat instLTNat i
(@List.length.{0} DecrAlmostLinearSSSP.Decremental.Instruction as))
(@List.instGetElem?NatLtLength.{0} DecrAlmostLinearSSSP.Decremental.Instruction) host.code
(@HAdd.hAdd.{0, 0, 0} Nat Nat Nat (@instHAdd.{0} Nat instAddNat) c.pc
(@OfNat.ofNat.{0} Nat (nat_lit 2) (instOfNatNat (nat_lit 2)))))
(@Option.some.{0} DecrAlmostLinearSSSP.Decremental.Instruction
(DecrAlmostLinearSSSP.Decremental.Instruction.cast
(DecrAlmostLinearSSSP.Decremental.shadowReg d)
(DecrAlmostLinearSSSP.Decremental.shadowReg a))) →
@Eq.{1} (Option.{0} DecrAlmostLinearSSSP.Decremental.Instruction)
(@GetElem?.getElem?.{0, 0, 0} (List.{0} DecrAlmostLinearSSSP.Decremental.Instruction) Nat
DecrAlmostLinearSSSP.Decremental.Instruction
(fun as i =>
@LT.lt.{0} Nat instLTNat i
(@List.length.{0} DecrAlmostLinearSSSP.Decremental.Instruction as))
(@List.instGetElem?NatLtLength.{0} DecrAlmostLinearSSSP.Decremental.Instruction) host.code
(@HAdd.hAdd.{0, 0, 0} Nat Nat Nat (@instHAdd.{0} Nat instAddNat) c.pc
(@OfNat.ofNat.{0} Nat (nat_lit 3) (instOfNatNat (nat_lit 3)))))
(@Option.some.{0} DecrAlmostLinearSSSP.Decremental.Instruction
(DecrAlmostLinearSSSP.Decremental.Instruction.div
(DecrAlmostLinearSSSP.Decremental.shadowReg d)
(DecrAlmostLinearSSSP.Decremental.shadowReg d)
(@OfNat.ofNat.{0} Nat (nat_lit 7) (instOfNatNat (nat_lit 7))))) →
@Eq.{1} (Option.{0} DecrAlmostLinearSSSP.Decremental.Instruction)
(@GetElem?.getElem?.{0, 0, 0} (List.{0} DecrAlmostLinearSSSP.Decremental.Instruction) Nat
DecrAlmostLinearSSSP.Decremental.Instruction
(fun as i =>
@LT.lt.{0} Nat instLTNat i
(@List.length.{0} DecrAlmostLinearSSSP.Decremental.Instruction as))
(@List.instGetElem?NatLtLength.{0} DecrAlmostLinearSSSP.Decremental.Instruction) host.code
(@HAdd.hAdd.{0, 0, 0} Nat Nat Nat (@instHAdd.{0} Nat instAddNat) c.pc
(@OfNat.ofNat.{0} Nat (nat_lit 4) (instOfNatNat (nat_lit 4)))))
(@Option.some.{0} DecrAlmostLinearSSSP.Decremental.Instruction
(DecrAlmostLinearSSSP.Decremental.Instruction.jump
(@HAdd.hAdd.{0, 0, 0} Nat Nat Nat (@instHAdd.{0} Nat instAddNat) offset
(@HMul.hMul.{0, 0, 0} Nat Nat Nat (@instHMul.{0} Nat instMulNat) width
(@HAdd.hAdd.{0, 0, 0} Nat Nat Nat (@instHAdd.{0} Nat instAddNat) g.pc
(@OfNat.ofNat.{0} Nat (nat_lit 1) (instOfNatNat (nat_lit 1)))))))) →
∃ finish,
And
(@Eq.{1} DecrAlmostLinearSSSP.Decremental.Machine
(DecrAlmostLinearSSSP.Decremental.execute host c
(@OfNat.ofNat.{0} Nat (nat_lit 5) (instOfNatNat (nat_lit 5))))
finish)
(And
(DecrAlmostLinearSSSP.Decremental.ShadowRep base F finish
(DecrAlmostLinearSSSP.Decremental.instructionEffect
(DecrAlmostLinearSSSP.Decremental.Instruction.cast d a)
{
pc :=
@HAdd.hAdd.{0, 0, 0} Nat Nat Nat (@instHAdd.{0} Nat instAddNat) g.pc
(@OfNat.ofNat.{0} Nat (nat_lit 1) (instOfNatNat (nat_lit 1))),
realReg := g.realReg, natReg := g.natReg, realMem := g.realMem,
natMem := g.natMem, halted := g.halted, fault := g.fault,
work :=
@HAdd.hAdd.{0, 0, 0} Nat Nat Nat (@instHAdd.{0} Nat instAddNat) g.work
(@OfNat.ofNat.{0} Nat (nat_lit 1) (instOfNatNat (nat_lit 1))) }))
(And
(@Eq.{1} Nat finish.pc
(@HAdd.hAdd.{0, 0, 0} Nat Nat Nat (@instHAdd.{0} Nat instAddNat) offset
(@HMul.hMul.{0, 0, 0} Nat Nat Nat (@instHMul.{0} Nat instMulNat) width
(@HAdd.hAdd.{0, 0, 0} Nat Nat Nat (@instHAdd.{0} Nat instAddNat) g.pc
(@OfNat.ofNat.{0} Nat (nat_lit 1) (instOfNatNat (nat_lit 1)))))))
(And
(@Eq.{1} Nat finish.work
(@HAdd.hAdd.{0, 0, 0} Nat Nat Nat (@instHAdd.{0} Nat instAddNat) c.work
(@OfNat.ofNat.{0} Nat (nat_lit 5) (instOfNatNat (nat_lit 5)))))
(And (@Eq.{1} Bool finish.halted Bool.false)
(And
(@Eq.{1} Nat
(finish.natReg (@OfNat.ofNat.{0} Nat (nat_lit 0) (instOfNatNat (nat_lit 0))))
(c.natReg (@OfNat.ofNat.{0} Nat (nat_lit 0) (instOfNatNat (nat_lit 0)))))
(And
(@Eq.{1} Nat
(finish.natReg
(@OfNat.ofNat.{0} Nat (nat_lit 1) (instOfNatNat (nat_lit 1))))
(c.natReg (@OfNat.ofNat.{0} Nat (nat_lit 1) (instOfNatNat (nat_lit 1)))))
(And
(@Eq.{1} Nat
(finish.natReg
(@OfNat.ofNat.{0} Nat (nat_lit 7) (instOfNatNat (nat_lit 7))))
(c.natReg (@OfNat.ofNat.{0} Nat (nat_lit 7) (instOfNatNat (nat_lit 7)))))
(@Eq.{1} Real
(finish.realReg
(@OfNat.ofNat.{0} Nat (nat_lit 7) (instOfNatNat (nat_lit 7))))
(c.realReg
(@OfNat.ofNat.{0} Nat (nat_lit 7) (instOfNatNat (nat_lit 7)))))))))))))) ∧ ((∀ {base F : Nat} {c g : DecrAlmostLinearSSSP.Decremental.Machine},
DecrAlmostLinearSSSP.Decremental.ShadowRep base F c g →
∀ (host : DecrAlmostLinearSSSP.Decremental.Program) (a : Nat),
@Eq.{1} Bool c.halted Bool.false →
@Eq.{1} Nat (c.natReg (@OfNat.ofNat.{0} Nat (nat_lit 0) (instOfNatNat (nat_lit 0)))) base →
@Eq.{1} Nat (c.natReg (@OfNat.ofNat.{0} Nat (nat_lit 7) (instOfNatNat (nat_lit 7)))) F →
@Eq.{1} (Option.{0} DecrAlmostLinearSSSP.Decremental.Instruction)
(@GetElem?.getElem?.{0, 0, 0} (List.{0} DecrAlmostLinearSSSP.Decremental.Instruction) Nat
DecrAlmostLinearSSSP.Decremental.Instruction
(fun as i =>
@LT.lt.{0} Nat instLTNat i (@List.length.{0} DecrAlmostLinearSSSP.Decremental.Instruction as))
(@List.instGetElem?NatLtLength.{0} DecrAlmostLinearSSSP.Decremental.Instruction) host.code c.pc)
(@Option.some.{0} DecrAlmostLinearSSSP.Decremental.Instruction
(DecrAlmostLinearSSSP.Decremental.Instruction.nadd
(@OfNat.ofNat.{0} Nat (nat_lit 6) (instOfNatNat (nat_lit 6)))
(DecrAlmostLinearSSSP.Decremental.shadowReg a) (DecrAlmostLinearSSSP.Decremental.shadowReg a))) →
@Eq.{1} (Option.{0} DecrAlmostLinearSSSP.Decremental.Instruction)
(@GetElem?.getElem?.{0, 0, 0} (List.{0} DecrAlmostLinearSSSP.Decremental.Instruction) Nat
DecrAlmostLinearSSSP.Decremental.Instruction
(fun as i =>
@LT.lt.{0} Nat instLTNat i (@List.length.{0} DecrAlmostLinearSSSP.Decremental.Instruction as))
(@List.instGetElem?NatLtLength.{0} DecrAlmostLinearSSSP.Decremental.Instruction) host.code
(@HAdd.hAdd.{0, 0, 0} Nat Nat Nat (@instHAdd.{0} Nat instAddNat) c.pc
(@OfNat.ofNat.{0} Nat (nat_lit 1) (instOfNatNat (nat_lit 1)))))
(@Option.some.{0} DecrAlmostLinearSSSP.Decremental.Instruction
(DecrAlmostLinearSSSP.Decremental.Instruction.nadd
(@OfNat.ofNat.{0} Nat (nat_lit 6) (instOfNatNat (nat_lit 6)))
(@OfNat.ofNat.{0} Nat (nat_lit 6) (instOfNatNat (nat_lit 6)))
(@OfNat.ofNat.{0} Nat (nat_lit 0) (instOfNatNat (nat_lit 0))))) →
@Eq.{1} (Option.{0} DecrAlmostLinearSSSP.Decremental.Instruction)
(@GetElem?.getElem?.{0, 0, 0} (List.{0} DecrAlmostLinearSSSP.Decremental.Instruction) Nat
DecrAlmostLinearSSSP.Decremental.Instruction
(fun as i =>
@LT.lt.{0} Nat instLTNat i (@List.length.{0} DecrAlmostLinearSSSP.Decremental.Instruction as))
(@List.instGetElem?NatLtLength.{0} DecrAlmostLinearSSSP.Decremental.Instruction) host.code
(@HAdd.hAdd.{0, 0, 0} Nat Nat Nat (@instHAdd.{0} Nat instAddNat) c.pc
(@OfNat.ofNat.{0} Nat (nat_lit 2) (instOfNatNat (nat_lit 2)))))
(@Option.some.{0} DecrAlmostLinearSSSP.Decremental.Instruction
(DecrAlmostLinearSSSP.Decremental.Instruction.nadd
(@OfNat.ofNat.{0} Nat (nat_lit 6) (instOfNatNat (nat_lit 6)))
(@OfNat.ofNat.{0} Nat (nat_lit 6) (instOfNatNat (nat_lit 6)))
(@OfNat.ofNat.{0} Nat (nat_lit 7) (instOfNatNat (nat_lit 7))))) →
∃ d,
And
(@Eq.{1} DecrAlmostLinearSSSP.Decremental.Machine
(DecrAlmostLinearSSSP.Decremental.execute host c
(@OfNat.ofNat.{0} Nat (nat_lit 3) (instOfNatNat (nat_lit 3))))
d)
(And (DecrAlmostLinearSSSP.Decremental.ShadowRep base F d g)
(And
(@Eq.{1} Nat (d.natReg (@OfNat.ofNat.{0} Nat (nat_lit 6) (instOfNatNat (nat_lit 6))))
(@HAdd.hAdd.{0, 0, 0} Nat Nat Nat (@instHAdd.{0} Nat instAddNat) base
(@HMul.hMul.{0, 0, 0} Nat Nat Nat (@instHMul.{0} Nat instMulNat) F
(@HAdd.hAdd.{0, 0, 0} Nat Nat Nat (@instHAdd.{0} Nat instAddNat)
(@HMul.hMul.{0, 0, 0} Nat Nat Nat (@instHMul.{0} Nat instMulNat)
(@OfNat.ofNat.{0} Nat (nat_lit 2) (instOfNatNat (nat_lit 2))) (g.natReg a))
(@OfNat.ofNat.{0} Nat (nat_lit 1) (instOfNatNat (nat_lit 1)))))))
(And
(@Eq.{1} Nat d.pc
(@HAdd.hAdd.{0, 0, 0} Nat Nat Nat (@instHAdd.{0} Nat instAddNat) c.pc
(@OfNat.ofNat.{0} Nat (nat_lit 3) (instOfNatNat (nat_lit 3)))))
(And
(@Eq.{1} Nat d.work
(@HAdd.hAdd.{0, 0, 0} Nat Nat Nat (@instHAdd.{0} Nat instAddNat) c.work
(@OfNat.ofNat.{0} Nat (nat_lit 3) (instOfNatNat (nat_lit 3)))))
(And (@Eq.{1} Bool d.halted Bool.false)
(And
(@Eq.{1} Nat (d.natReg (@OfNat.ofNat.{0} Nat (nat_lit 0) (instOfNatNat (nat_lit 0))))
(c.natReg (@OfNat.ofNat.{0} Nat (nat_lit 0) (instOfNatNat (nat_lit 0)))))
(And
(@Eq.{1} Nat
(d.natReg (@OfNat.ofNat.{0} Nat (nat_lit 1) (instOfNatNat (nat_lit 1))))
(c.natReg (@OfNat.ofNat.{0} Nat (nat_lit 1) (instOfNatNat (nat_lit 1)))))
(And
(@Eq.{1} Nat
(d.natReg (@OfNat.ofNat.{0} Nat (nat_lit 7) (instOfNatNat (nat_lit 7))))
(c.natReg (@OfNat.ofNat.{0} Nat (nat_lit 7) (instOfNatNat (nat_lit 7)))))
(@Eq.{1} Real
(d.realReg (@OfNat.ofNat.{0} Nat (nat_lit 7) (instOfNatNat (nat_lit 7))))
(c.realReg
(@OfNat.ofNat.{0} Nat (nat_lit 7) (instOfNatNat (nat_lit 7)))))))))))))) ∧ ((∀ (ins tr : DecrAlmostLinearSSSP.Decremental.Instruction) (a : Nat),
@Eq.{1} (Option.{0} (Prod.{0, 0} DecrAlmostLinearSSSP.Decremental.Instruction Nat))
(DecrAlmostLinearSSSP.Decremental.shadowMemoryTranslation ins)
(@Option.some.{0} (Prod.{0, 0} DecrAlmostLinearSSSP.Decremental.Instruction Nat)
(@Prod.mk.{0, 0} DecrAlmostLinearSSSP.Decremental.Instruction Nat tr a)) →
DecrAlmostLinearSSSP.Decremental.ReservedSafe tr) ∧ (∀ {base F : Nat} {c g : DecrAlmostLinearSSSP.Decremental.Machine},
DecrAlmostLinearSSSP.Decremental.ShadowRep base F c g →
∀ (host : DecrAlmostLinearSSSP.Decremental.Program),
@LT.lt.{0} Nat instLTNat (@OfNat.ofNat.{0} Nat (nat_lit 0) (instOfNatNat (nat_lit 0))) F →
∀ (ins tr : DecrAlmostLinearSSSP.Decremental.Instruction) (a : Nat),
@Eq.{1} (Option.{0} (Prod.{0, 0} DecrAlmostLinearSSSP.Decremental.Instruction Nat))
(DecrAlmostLinearSSSP.Decremental.shadowMemoryTranslation ins)
(@Option.some.{0} (Prod.{0, 0} DecrAlmostLinearSSSP.Decremental.Instruction Nat)
(@Prod.mk.{0, 0} DecrAlmostLinearSSSP.Decremental.Instruction Nat tr a)) →
@Eq.{1} Nat (c.natReg (@OfNat.ofNat.{0} Nat (nat_lit 6) (instOfNatNat (nat_lit 6))))
(@HAdd.hAdd.{0, 0, 0} Nat Nat Nat (@instHAdd.{0} Nat instAddNat) base
(@HMul.hMul.{0, 0, 0} Nat Nat Nat (@instHMul.{0} Nat instMulNat) F
(@HAdd.hAdd.{0, 0, 0} Nat Nat Nat (@instHAdd.{0} Nat instAddNat)
(@HMul.hMul.{0, 0, 0} Nat Nat Nat (@instHMul.{0} Nat instMulNat)
(@OfNat.ofNat.{0} Nat (nat_lit 2) (instOfNatNat (nat_lit 2))) (g.natReg a))
(@OfNat.ofNat.{0} Nat (nat_lit 1) (instOfNatNat (nat_lit 1)))))) →
@Eq.{1} Bool c.halted Bool.false →
@Eq.{1} (Option.{0} DecrAlmostLinearSSSP.Decremental.Instruction)
(@GetElem?.getElem?.{0, 0, 0} (List.{0} DecrAlmostLinearSSSP.Decremental.Instruction) Nat
DecrAlmostLinearSSSP.Decremental.Instruction
(fun as i =>
@LT.lt.{0} Nat instLTNat i (@List.length.{0} DecrAlmostLinearSSSP.Decremental.Instruction as))
(@List.instGetElem?NatLtLength.{0} DecrAlmostLinearSSSP.Decremental.Instruction) host.code c.pc)
(@Option.some.{0} DecrAlmostLinearSSSP.Decremental.Instruction tr) →
And
(DecrAlmostLinearSSSP.Decremental.ShadowRep base F
(DecrAlmostLinearSSSP.Decremental.execute host c
(@OfNat.ofNat.{0} Nat (nat_lit 1) (instOfNatNat (nat_lit 1))))
(DecrAlmostLinearSSSP.Decremental.instructionEffect ins g))
(And
(@Eq.{1} Nat
(DecrAlmostLinearSSSP.Decremental.execute host c
(@OfNat.ofNat.{0} Nat (nat_lit 1) (instOfNatNat (nat_lit 1)))).pc
(@HAdd.hAdd.{0, 0, 0} Nat Nat Nat (@instHAdd.{0} Nat instAddNat) c.pc
(@OfNat.ofNat.{0} Nat (nat_lit 1) (instOfNatNat (nat_lit 1)))))
(And
(@Eq.{1} Nat
(DecrAlmostLinearSSSP.Decremental.execute host c
(@OfNat.ofNat.{0} Nat (nat_lit 1) (instOfNatNat (nat_lit 1)))).work
(@HAdd.hAdd.{0, 0, 0} Nat Nat Nat (@instHAdd.{0} Nat instAddNat) c.work
(@OfNat.ofNat.{0} Nat (nat_lit 1) (instOfNatNat (nat_lit 1)))))
(And
(@Eq.{1} Bool
(DecrAlmostLinearSSSP.Decremental.execute host c
(@OfNat.ofNat.{0} Nat (nat_lit 1) (instOfNatNat (nat_lit 1)))).halted
Bool.false)
(And
(@Eq.{1} Nat
((DecrAlmostLinearSSSP.Decremental.execute host c
(@OfNat.ofNat.{0} Nat (nat_lit 1) (instOfNatNat (nat_lit 1)))).natReg
(@OfNat.ofNat.{0} Nat (nat_lit 0) (instOfNatNat (nat_lit 0))))
(c.natReg (@OfNat.ofNat.{0} Nat (nat_lit 0) (instOfNatNat (nat_lit 0)))))
(And
(@Eq.{1} Nat
((DecrAlmostLinearSSSP.Decremental.execute host c
(@OfNat.ofNat.{0} Nat (nat_lit 1) (instOfNatNat (nat_lit 1)))).natReg
(@OfNat.ofNat.{0} Nat (nat_lit 1) (instOfNatNat (nat_lit 1))))
(c.natReg (@OfNat.ofNat.{0} Nat (nat_lit 1) (instOfNatNat (nat_lit 1)))))
(And
(@Eq.{1} Nat
((DecrAlmostLinearSSSP.Decremental.execute host c
(@OfNat.ofNat.{0} Nat (nat_lit 1) (instOfNatNat (nat_lit 1)))).natReg
(@OfNat.ofNat.{0} Nat (nat_lit 7) (instOfNatNat (nat_lit 7))))
(c.natReg (@OfNat.ofNat.{0} Nat (nat_lit 7) (instOfNatNat (nat_lit 7)))))
(@Eq.{1} Real
((DecrAlmostLinearSSSP.Decremental.execute host c
(@OfNat.ofNat.{0} Nat (nat_lit 1) (instOfNatNat (nat_lit 1)))).realReg
(@OfNat.ofNat.{0} Nat (nat_lit 7) (instOfNatNat (nat_lit 7))))
(c.realReg (@OfNat.ofNat.{0} Nat (nat_lit 7) (instOfNatNat (nat_lit 7))))))))))))))) ∧ (((∀ {base F : Nat} {c g : DecrAlmostLinearSSSP.Decremental.Machine},
DecrAlmostLinearSSSP.Decremental.ShadowRep base F c g →
∀ (host : DecrAlmostLinearSSSP.Decremental.Program) (width offset : Nat),
@LT.lt.{0} Nat instLTNat (@OfNat.ofNat.{0} Nat (nat_lit 0) (instOfNatNat (nat_lit 0))) F →
∀ (ins tr : DecrAlmostLinearSSSP.Decremental.Instruction) (a : Nat),
@Eq.{1} (Option.{0} (Prod.{0, 0} DecrAlmostLinearSSSP.Decremental.Instruction Nat))
(DecrAlmostLinearSSSP.Decremental.shadowMemoryTranslation ins)
(@Option.some.{0} (Prod.{0, 0} DecrAlmostLinearSSSP.Decremental.Instruction Nat)
(@Prod.mk.{0, 0} DecrAlmostLinearSSSP.Decremental.Instruction Nat tr a)) →
@Eq.{1} Bool c.halted Bool.false →
@Eq.{1} Nat (c.natReg (@OfNat.ofNat.{0} Nat (nat_lit 1) (instOfNatNat (nat_lit 1))))
(@OfNat.ofNat.{0} Nat (nat_lit 1) (instOfNatNat (nat_lit 1))) →
@Eq.{1} Nat (c.natReg (@OfNat.ofNat.{0} Nat (nat_lit 0) (instOfNatNat (nat_lit 0)))) base →
@Eq.{1} Nat (c.natReg (@OfNat.ofNat.{0} Nat (nat_lit 7) (instOfNatNat (nat_lit 7)))) F →
@Eq.{1} (Option.{0} DecrAlmostLinearSSSP.Decremental.Instruction)
(@GetElem?.getElem?.{0, 0, 0} (List.{0} DecrAlmostLinearSSSP.Decremental.Instruction) Nat
DecrAlmostLinearSSSP.Decremental.Instruction
(fun as i =>
@LT.lt.{0} Nat instLTNat i
(@List.length.{0} DecrAlmostLinearSSSP.Decremental.Instruction as))
(@List.instGetElem?NatLtLength.{0} DecrAlmostLinearSSSP.Decremental.Instruction) host.code
c.pc)
(@Option.some.{0} DecrAlmostLinearSSSP.Decremental.Instruction
(DecrAlmostLinearSSSP.Decremental.Instruction.natural
(@OfNat.ofNat.{0} Nat (nat_lit 2) (instOfNatNat (nat_lit 2)))
(@HAdd.hAdd.{0, 0, 0} Nat Nat Nat (@instHAdd.{0} Nat instAddNat) g.pc
(@OfNat.ofNat.{0} Nat (nat_lit 1) (instOfNatNat (nat_lit 1)))))) →
@Eq.{1} (Option.{0} DecrAlmostLinearSSSP.Decremental.Instruction)
(@GetElem?.getElem?.{0, 0, 0} (List.{0} DecrAlmostLinearSSSP.Decremental.Instruction) Nat
DecrAlmostLinearSSSP.Decremental.Instruction
(fun as i =>
@LT.lt.{0} Nat instLTNat i
(@List.length.{0} DecrAlmostLinearSSSP.Decremental.Instruction as))
(@List.instGetElem?NatLtLength.{0} DecrAlmostLinearSSSP.Decremental.Instruction) host.code
(@HAdd.hAdd.{0, 0, 0} Nat Nat Nat (@instHAdd.{0} Nat instAddNat) c.pc
(@OfNat.ofNat.{0} Nat (nat_lit 1) (instOfNatNat (nat_lit 1)))))
(@Option.some.{0} DecrAlmostLinearSSSP.Decremental.Instruction
(DecrAlmostLinearSSSP.Decremental.Instruction.nadd
(@OfNat.ofNat.{0} Nat (nat_lit 3) (instOfNatNat (nat_lit 3)))
(@OfNat.ofNat.{0} Nat (nat_lit 3) (instOfNatNat (nat_lit 3)))
(@OfNat.ofNat.{0} Nat (nat_lit 1) (instOfNatNat (nat_lit 1))))) →
@Eq.{1} (Option.{0} DecrAlmostLinearSSSP.Decremental.Instruction)
(@GetElem?.getElem?.{0, 0, 0} (List.{0} DecrAlmostLinearSSSP.Decremental.Instruction) Nat
DecrAlmostLinearSSSP.Decremental.Instruction
(fun as i =>
@LT.lt.{0} Nat instLTNat i
(@List.length.{0} DecrAlmostLinearSSSP.Decremental.Instruction as))
(@List.instGetElem?NatLtLength.{0} DecrAlmostLinearSSSP.Decremental.Instruction) host.code
(@HAdd.hAdd.{0, 0, 0} Nat Nat Nat (@instHAdd.{0} Nat instAddNat) c.pc
(@OfNat.ofNat.{0} Nat (nat_lit 2) (instOfNatNat (nat_lit 2)))))
(@Option.some.{0} DecrAlmostLinearSSSP.Decremental.Instruction
(DecrAlmostLinearSSSP.Decremental.Instruction.nadd
(@OfNat.ofNat.{0} Nat (nat_lit 6) (instOfNatNat (nat_lit 6)))
(DecrAlmostLinearSSSP.Decremental.shadowReg a)
(DecrAlmostLinearSSSP.Decremental.shadowReg a))) →
@Eq.{1} (Option.{0} DecrAlmostLinearSSSP.Decremental.Instruction)
(@GetElem?.getElem?.{0, 0, 0} (List.{0} DecrAlmostLinearSSSP.Decremental.Instruction) Nat
DecrAlmostLinearSSSP.Decremental.Instruction
(fun as i =>
@LT.lt.{0} Nat instLTNat i
(@List.length.{0} DecrAlmostLinearSSSP.Decremental.Instruction as))
(@List.instGetElem?NatLtLength.{0} DecrAlmostLinearSSSP.Decremental.Instruction)
host.code
(@HAdd.hAdd.{0, 0, 0} Nat Nat Nat (@instHAdd.{0} Nat instAddNat) c.pc
(@OfNat.ofNat.{0} Nat (nat_lit 3) (instOfNatNat (nat_lit 3)))))
(@Option.some.{0} DecrAlmostLinearSSSP.Decremental.Instruction
(DecrAlmostLinearSSSP.Decremental.Instruction.nadd
(@OfNat.ofNat.{0} Nat (nat_lit 6) (instOfNatNat (nat_lit 6)))
(@OfNat.ofNat.{0} Nat (nat_lit 6) (instOfNatNat (nat_lit 6)))
(@OfNat.ofNat.{0} Nat (nat_lit 0) (instOfNatNat (nat_lit 0))))) →
@Eq.{1} (Option.{0} DecrAlmostLinearSSSP.Decremental.Instruction)
(@GetElem?.getElem?.{0, 0, 0} (List.{0} DecrAlmostLinearSSSP.Decremental.Instruction)
Nat DecrAlmostLinearSSSP.Decremental.Instruction
(fun as i =>
@LT.lt.{0} Nat instLTNat i
(@List.length.{0} DecrAlmostLinearSSSP.Decremental.Instruction as))
(@List.instGetElem?NatLtLength.{0} DecrAlmostLinearSSSP.Decremental.Instruction)
host.code
(@HAdd.hAdd.{0, 0, 0} Nat Nat Nat (@instHAdd.{0} Nat instAddNat) c.pc
(@OfNat.ofNat.{0} Nat (nat_lit 4) (instOfNatNat (nat_lit 4)))))
(@Option.some.{0} DecrAlmostLinearSSSP.Decremental.Instruction
(DecrAlmostLinearSSSP.Decremental.Instruction.nadd
(@OfNat.ofNat.{0} Nat (nat_lit 6) (instOfNatNat (nat_lit 6)))
(@OfNat.ofNat.{0} Nat (nat_lit 6) (instOfNatNat (nat_lit 6)))
(@OfNat.ofNat.{0} Nat (nat_lit 7) (instOfNatNat (nat_lit 7))))) →
@Eq.{1} (Option.{0} DecrAlmostLinearSSSP.Decremental.Instruction)
(@GetElem?.getElem?.{0, 0, 0} (List.{0} DecrAlmostLinearSSSP.Decremental.Instruction)
Nat DecrAlmostLinearSSSP.Decremental.Instruction
(fun as i =>
@LT.lt.{0} Nat instLTNat i
(@List.length.{0} DecrAlmostLinearSSSP.Decremental.Instruction as))
(@List.instGetElem?NatLtLength.{0} DecrAlmostLinearSSSP.Decremental.Instruction)
host.code
(@HAdd.hAdd.{0, 0, 0} Nat Nat Nat (@instHAdd.{0} Nat instAddNat) c.pc
(@OfNat.ofNat.{0} Nat (nat_lit 5) (instOfNatNat (nat_lit 5)))))
(@Option.some.{0} DecrAlmostLinearSSSP.Decremental.Instruction tr) →
@Eq.{1} (Option.{0} DecrAlmostLinearSSSP.Decremental.Instruction)
(@GetElem?.getElem?.{0, 0, 0}
(List.{0} DecrAlmostLinearSSSP.Decremental.Instruction) Nat
DecrAlmostLinearSSSP.Decremental.Instruction
(fun as i =>
@LT.lt.{0} Nat instLTNat i
(@List.length.{0} DecrAlmostLinearSSSP.Decremental.Instruction as))
(@List.instGetElem?NatLtLength.{0} DecrAlmostLinearSSSP.Decremental.Instruction)
host.code
(@HAdd.hAdd.{0, 0, 0} Nat Nat Nat (@instHAdd.{0} Nat instAddNat) c.pc
(@OfNat.ofNat.{0} Nat (nat_lit 6) (instOfNatNat (nat_lit 6)))))
(@Option.some.{0} DecrAlmostLinearSSSP.Decremental.Instruction
(DecrAlmostLinearSSSP.Decremental.Instruction.jump
(@HAdd.hAdd.{0, 0, 0} Nat Nat Nat (@instHAdd.{0} Nat instAddNat) offset
(@HMul.hMul.{0, 0, 0} Nat Nat Nat (@instHMul.{0} Nat instMulNat) width
(@HAdd.hAdd.{0, 0, 0} Nat Nat Nat (@instHAdd.{0} Nat instAddNat) g.pc
(@OfNat.ofNat.{0} Nat (nat_lit 1) (instOfNatNat (nat_lit 1)))))))) →
∃ d,
And
(@Eq.{1} DecrAlmostLinearSSSP.Decremental.Machine
(DecrAlmostLinearSSSP.Decremental.execute host c
(@OfNat.ofNat.{0} Nat (nat_lit 7) (instOfNatNat (nat_lit 7))))
d)
(And
(DecrAlmostLinearSSSP.Decremental.ShadowRep base F d
(DecrAlmostLinearSSSP.Decremental.instructionEffect ins
{
pc :=
@HAdd.hAdd.{0, 0, 0} Nat Nat Nat (@instHAdd.{0} Nat instAddNat) g.pc
(@OfNat.ofNat.{0} Nat (nat_lit 1) (instOfNatNat (nat_lit 1))),
realReg := g.realReg, natReg := g.natReg, realMem := g.realMem,
natMem := g.natMem, halted := g.halted, fault := g.fault,
work :=
@HAdd.hAdd.{0, 0, 0} Nat Nat Nat (@instHAdd.{0} Nat instAddNat) g.work
(@OfNat.ofNat.{0} Nat (nat_lit 1) (instOfNatNat (nat_lit 1))) }))
(And
(@Eq.{1} Nat d.pc
(@HAdd.hAdd.{0, 0, 0} Nat Nat Nat (@instHAdd.{0} Nat instAddNat) offset
(@HMul.hMul.{0, 0, 0} Nat Nat Nat (@instHMul.{0} Nat instMulNat) width
(@HAdd.hAdd.{0, 0, 0} Nat Nat Nat (@instHAdd.{0} Nat instAddNat) g.pc
(@OfNat.ofNat.{0} Nat (nat_lit 1) (instOfNatNat (nat_lit 1)))))))
(And
(@Eq.{1} Nat d.work
(@HAdd.hAdd.{0, 0, 0} Nat Nat Nat (@instHAdd.{0} Nat instAddNat) c.work
(@OfNat.ofNat.{0} Nat (nat_lit 7) (instOfNatNat (nat_lit 7)))))
(And (@Eq.{1} Bool d.halted Bool.false)
(And
(@Eq.{1} Nat
(d.natReg
(@OfNat.ofNat.{0} Nat (nat_lit 0) (instOfNatNat (nat_lit 0))))
(c.natReg
(@OfNat.ofNat.{0} Nat (nat_lit 0) (instOfNatNat (nat_lit 0)))))
(And
(@Eq.{1} Nat
(d.natReg
(@OfNat.ofNat.{0} Nat (nat_lit 1) (instOfNatNat (nat_lit 1))))
(c.natReg
(@OfNat.ofNat.{0} Nat (nat_lit 1) (instOfNatNat (nat_lit 1)))))
(And
(@Eq.{1} Nat
(d.natReg
(@OfNat.ofNat.{0} Nat (nat_lit 7) (instOfNatNat (nat_lit 7))))
(c.natReg
(@OfNat.ofNat.{0} Nat (nat_lit 7) (instOfNatNat (nat_lit 7)))))
(@Eq.{1} Real
(d.realReg
(@OfNat.ofNat.{0} Nat (nat_lit 7) (instOfNatNat (nat_lit 7))))
(c.realReg
(@OfNat.ofNat.{0} Nat (nat_lit 7)
(instOfNatNat (nat_lit 7))))))))))))) ∧ (∀ (width offset returnPC start : Nat) (code : List.{0} DecrAlmostLinearSSSP.Decremental.Instruction),
@LE.le.{0} Nat instLENat (@OfNat.ofNat.{0} Nat (nat_lit 8) (instOfNatNat (nat_lit 8))) width →
(∀ (ins : DecrAlmostLinearSSSP.Decremental.Instruction),
@Membership.mem.{0, 0} DecrAlmostLinearSSSP.Decremental.Instruction
(List.{0} DecrAlmostLinearSSSP.Decremental.Instruction)
(@List.instMembership.{0} DecrAlmostLinearSSSP.Decremental.Instruction) code ins →
@LE.le.{0} Nat instLENat
(@HAdd.hAdd.{0, 0, 0} Nat Nat Nat (@instHAdd.{0} Nat instAddNat)
(DecrAlmostLinearSSSP.Decremental.naturalConstant ins)
(@OfNat.ofNat.{0} Nat (nat_lit 4) (instOfNatNat (nat_lit 4))))
width) →
∀ (pc slot : Nat) (ins : DecrAlmostLinearSSSP.Decremental.Instruction),
@LT.lt.{0} Nat instLTNat slot width →
@Eq.{1} (Option.{0} DecrAlmostLinearSSSP.Decremental.Instruction)
(@GetElem?.getElem?.{0, 0, 0} (List.{0} DecrAlmostLinearSSSP.Decremental.Instruction) Nat
DecrAlmostLinearSSSP.Decremental.Instruction
(fun as i =>
@LT.lt.{0} Nat instLTNat i (@List.length.{0} DecrAlmostLinearSSSP.Decremental.Instruction as))
(@List.instGetElem?NatLtLength.{0} DecrAlmostLinearSSSP.Decremental.Instruction) code pc)
(@Option.some.{0} DecrAlmostLinearSSSP.Decremental.Instruction ins) →
@Eq.{1} (Option.{0} DecrAlmostLinearSSSP.Decremental.Instruction)
(@GetElem?.getElem?.{0, 0, 0} (List.{0} DecrAlmostLinearSSSP.Decremental.Instruction) Nat
DecrAlmostLinearSSSP.Decremental.Instruction
(fun as i =>
@LT.lt.{0} Nat instLTNat i (@List.length.{0} DecrAlmostLinearSSSP.Decremental.Instruction as))
(@List.instGetElem?NatLtLength.{0} DecrAlmostLinearSSSP.Decremental.Instruction)
(DecrAlmostLinearSSSP.Decremental.shadowCodeAux width offset returnPC start code)
(@HAdd.hAdd.{0, 0, 0} Nat Nat Nat (@instHAdd.{0} Nat instAddNat)
(@HMul.hMul.{0, 0, 0} Nat Nat Nat (@instHMul.{0} Nat instMulNat) width pc) slot))
(@GetElem?.getElem?.{0, 0, 0} (List.{0} DecrAlmostLinearSSSP.Decremental.Instruction) Nat
DecrAlmostLinearSSSP.Decremental.Instruction
(fun as i =>
@LT.lt.{0} Nat instLTNat i (@List.length.{0} DecrAlmostLinearSSSP.Decremental.Instruction as))
(@List.instGetElem?NatLtLength.{0} DecrAlmostLinearSSSP.Decremental.Instruction)
(DecrAlmostLinearSSSP.Decremental.shadowBlock width offset returnPC
(@HAdd.hAdd.{0, 0, 0} Nat Nat Nat (@instHAdd.{0} Nat instAddNat) start pc) ins)
slot))) ∧ ((∀ (offset returnPC : Nat) (code : List.{0} DecrAlmostLinearSSSP.Decremental.Instruction) (pc slot : Nat)
(ins : DecrAlmostLinearSSSP.Decremental.Instruction),
@LT.lt.{0} Nat instLTNat slot (DecrAlmostLinearSSSP.Decremental.shadowWidth code) →
@Eq.{1} (Option.{0} DecrAlmostLinearSSSP.Decremental.Instruction)
(@GetElem?.getElem?.{0, 0, 0} (List.{0} DecrAlmostLinearSSSP.Decremental.Instruction) Nat
DecrAlmostLinearSSSP.Decremental.Instruction
(fun as i => @LT.lt.{0} Nat instLTNat i (@List.length.{0} DecrAlmostLinearSSSP.Decremental.Instruction as))
(@List.instGetElem?NatLtLength.{0} DecrAlmostLinearSSSP.Decremental.Instruction) code pc)
(@Option.some.{0} DecrAlmostLinearSSSP.Decremental.Instruction ins) →
@Eq.{1} (Option.{0} DecrAlmostLinearSSSP.Decremental.Instruction)
(@GetElem?.getElem?.{0, 0, 0} (List.{0} DecrAlmostLinearSSSP.Decremental.Instruction) Nat
DecrAlmostLinearSSSP.Decremental.Instruction
(fun as i => @LT.lt.{0} Nat instLTNat i (@List.length.{0} DecrAlmostLinearSSSP.Decremental.Instruction as))
(@List.instGetElem?NatLtLength.{0} DecrAlmostLinearSSSP.Decremental.Instruction)
(DecrAlmostLinearSSSP.Decremental.shadowCode offset returnPC code)
(@HAdd.hAdd.{0, 0, 0} Nat Nat Nat (@instHAdd.{0} Nat instAddNat)
(@HMul.hMul.{0, 0, 0} Nat Nat Nat (@instHMul.{0} Nat instMulNat)
(DecrAlmostLinearSSSP.Decremental.shadowWidth code) pc)
slot))
(@GetElem?.getElem?.{0, 0, 0} (List.{0} DecrAlmostLinearSSSP.Decremental.Instruction) Nat
DecrAlmostLinearSSSP.Decremental.Instruction
(fun as i => @LT.lt.{0} Nat instLTNat i (@List.length.{0} DecrAlmostLinearSSSP.Decremental.Instruction as))
(@List.instGetElem?NatLtLength.{0} DecrAlmostLinearSSSP.Decremental.Instruction)
(DecrAlmostLinearSSSP.Decremental.shadowBlock (DecrAlmostLinearSSSP.Decremental.shadowWidth code) offset
returnPC pc ins)
slot)) ∧ ((∀ (width offset returnPC pc : Nat) (ins : DecrAlmostLinearSSSP.Decremental.Instruction),
And
(@Eq.{1} (Option.{0} DecrAlmostLinearSSSP.Decremental.Instruction)
(@GetElem?.getElem?.{0, 0, 0} (List.{0} DecrAlmostLinearSSSP.Decremental.Instruction) Nat
DecrAlmostLinearSSSP.Decremental.Instruction
(fun as i => @LT.lt.{0} Nat instLTNat i (@List.length.{0} DecrAlmostLinearSSSP.Decremental.Instruction as))
(@List.instGetElem?NatLtLength.{0} DecrAlmostLinearSSSP.Decremental.Instruction)
(DecrAlmostLinearSSSP.Decremental.shadowBlock width offset returnPC pc ins)
(@OfNat.ofNat.{0} Nat (nat_lit 0) (instOfNatNat (nat_lit 0))))
(@Option.some.{0} DecrAlmostLinearSSSP.Decremental.Instruction
(DecrAlmostLinearSSSP.Decremental.Instruction.natural
(@OfNat.ofNat.{0} Nat (nat_lit 2) (instOfNatNat (nat_lit 2)))
(@HAdd.hAdd.{0, 0, 0} Nat Nat Nat (@instHAdd.{0} Nat instAddNat) pc
(@OfNat.ofNat.{0} Nat (nat_lit 1) (instOfNatNat (nat_lit 1)))))))
(@Eq.{1} (Option.{0} DecrAlmostLinearSSSP.Decremental.Instruction)
(@GetElem?.getElem?.{0, 0, 0} (List.{0} DecrAlmostLinearSSSP.Decremental.Instruction) Nat
DecrAlmostLinearSSSP.Decremental.Instruction
(fun as i => @LT.lt.{0} Nat instLTNat i (@List.length.{0} DecrAlmostLinearSSSP.Decremental.Instruction as))
(@List.instGetElem?NatLtLength.{0} DecrAlmostLinearSSSP.Decremental.Instruction)
(DecrAlmostLinearSSSP.Decremental.shadowBlock width offset returnPC pc ins)
(@OfNat.ofNat.{0} Nat (nat_lit 1) (instOfNatNat (nat_lit 1))))
(@Option.some.{0} DecrAlmostLinearSSSP.Decremental.Instruction
(DecrAlmostLinearSSSP.Decremental.Instruction.nadd (@OfNat.ofNat.{0} Nat (nat_lit 3) (instOfNatNat (nat_lit 3)))
(@OfNat.ofNat.{0} Nat (nat_lit 3) (instOfNatNat (nat_lit 3)))
(@OfNat.ofNat.{0} Nat (nat_lit 1) (instOfNatNat (nat_lit 1))))))) ∧ (∀ (width offset returnPC pc d q j : Nat),
@LT.lt.{0} Nat instLTNat j q →
@Eq.{1} (Option.{0} DecrAlmostLinearSSSP.Decremental.Instruction)
(@GetElem?.getElem?.{0, 0, 0} (List.{0} DecrAlmostLinearSSSP.Decremental.Instruction) Nat
DecrAlmostLinearSSSP.Decremental.Instruction
(fun as i => @LT.lt.{0} Nat instLTNat i (@List.length.{0} DecrAlmostLinearSSSP.Decremental.Instruction as))
(@List.instGetElem?NatLtLength.{0} DecrAlmostLinearSSSP.Decremental.Instruction)
(DecrAlmostLinearSSSP.Decremental.shadowBlock width offset returnPC pc
(DecrAlmostLinearSSSP.Decremental.Instruction.natural d q))
(@HAdd.hAdd.{0, 0, 0} Nat Nat Nat (@instHAdd.{0} Nat instAddNat)
(@OfNat.ofNat.{0} Nat (nat_lit 3) (instOfNatNat (nat_lit 3))) j))
(@Option.some.{0} DecrAlmostLinearSSSP.Decremental.Instruction
(DecrAlmostLinearSSSP.Decremental.Instruction.nadd (DecrAlmostLinearSSSP.Decremental.shadowReg d)
(DecrAlmostLinearSSSP.Decremental.shadowReg d) (@OfNat.ofNat.{0} Nat (nat_lit 7) (instOfNatNat (nat_lit 7))))))))))) ∧ (((((∀ (width offset returnPC pc d q : Nat),
@Eq.{1} (Option.{0} DecrAlmostLinearSSSP.Decremental.Instruction)
(@GetElem?.getElem?.{0, 0, 0} (List.{0} DecrAlmostLinearSSSP.Decremental.Instruction) Nat
DecrAlmostLinearSSSP.Decremental.Instruction
(fun as i => @LT.lt.{0} Nat instLTNat i (@List.length.{0} DecrAlmostLinearSSSP.Decremental.Instruction as))
(@List.instGetElem?NatLtLength.{0} DecrAlmostLinearSSSP.Decremental.Instruction)
(DecrAlmostLinearSSSP.Decremental.shadowBlock width offset returnPC pc
(DecrAlmostLinearSSSP.Decremental.Instruction.natural d q))
(@HAdd.hAdd.{0, 0, 0} Nat Nat Nat (@instHAdd.{0} Nat instAddNat) q
(@OfNat.ofNat.{0} Nat (nat_lit 3) (instOfNatNat (nat_lit 3)))))
(@Option.some.{0} DecrAlmostLinearSSSP.Decremental.Instruction
(DecrAlmostLinearSSSP.Decremental.Instruction.jump
(@HAdd.hAdd.{0, 0, 0} Nat Nat Nat (@instHAdd.{0} Nat instAddNat) offset
(@HMul.hMul.{0, 0, 0} Nat Nat Nat (@instHMul.{0} Nat instMulNat) width
(@HAdd.hAdd.{0, 0, 0} Nat Nat Nat (@instHAdd.{0} Nat instAddNat) pc
(@OfNat.ofNat.{0} Nat (nat_lit 1) (instOfNatNat (nat_lit 1))))))))) ∧ (∀ (ins tr : DecrAlmostLinearSSSP.Decremental.Instruction),
@Eq.{1} (Option.{0} DecrAlmostLinearSSSP.Decremental.Instruction)
(DecrAlmostLinearSSSP.Decremental.shadowScalarTranslation ins)
(@Option.some.{0} DecrAlmostLinearSSSP.Decremental.Instruction tr) →
∀ (g : DecrAlmostLinearSSSP.Decremental.Machine),
And (@Eq.{1} Nat (DecrAlmostLinearSSSP.Decremental.instructionEffect ins g).pc g.pc)
(@Eq.{1} Bool (DecrAlmostLinearSSSP.Decremental.instructionEffect ins g).halted g.halted))) ∧ ((∀ (ins tr : DecrAlmostLinearSSSP.Decremental.Instruction) (a : Nat),
@Eq.{1} (Option.{0} (Prod.{0, 0} DecrAlmostLinearSSSP.Decremental.Instruction Nat))
(DecrAlmostLinearSSSP.Decremental.shadowMemoryTranslation ins)
(@Option.some.{0} (Prod.{0, 0} DecrAlmostLinearSSSP.Decremental.Instruction Nat)
(@Prod.mk.{0, 0} DecrAlmostLinearSSSP.Decremental.Instruction Nat tr a)) →
∀ (g : DecrAlmostLinearSSSP.Decremental.Machine),
And (@Eq.{1} Nat (DecrAlmostLinearSSSP.Decremental.instructionEffect ins g).pc g.pc)
(@Eq.{1} Bool (DecrAlmostLinearSSSP.Decremental.instructionEffect ins g).halted g.halted)) ∧ (∀ {base F : Nat} {c g : DecrAlmostLinearSSSP.Decremental.Machine},
DecrAlmostLinearSSSP.Decremental.ShadowRep base F c g →
∀ (host : DecrAlmostLinearSSSP.Decremental.Program) (width offset returnPC : Nat),
@LE.le.{0} Nat instLENat (@OfNat.ofNat.{0} Nat (nat_lit 8) (instOfNatNat (nat_lit 8))) width →
@LT.lt.{0} Nat instLTNat (@OfNat.ofNat.{0} Nat (nat_lit 0) (instOfNatNat (nat_lit 0))) F →
∀ (ins : DecrAlmostLinearSSSP.Decremental.Instruction),
@LE.le.{0} Nat instLENat
(@HAdd.hAdd.{0, 0, 0} Nat Nat Nat (@instHAdd.{0} Nat instAddNat)
(DecrAlmostLinearSSSP.Decremental.naturalConstant ins)
(@OfNat.ofNat.{0} Nat (nat_lit 4) (instOfNatNat (nat_lit 4))))
width →
@Eq.{1} Bool c.halted Bool.false →
@Eq.{1} Nat (c.natReg (@OfNat.ofNat.{0} Nat (nat_lit 1) (instOfNatNat (nat_lit 1))))
(@OfNat.ofNat.{0} Nat (nat_lit 1) (instOfNatNat (nat_lit 1))) →
@Eq.{1} Bool g.halted Bool.false →
@Eq.{1} Nat (c.natReg (@OfNat.ofNat.{0} Nat (nat_lit 0) (instOfNatNat (nat_lit 0)))) base →
@Eq.{1} Nat (c.natReg (@OfNat.ofNat.{0} Nat (nat_lit 7) (instOfNatNat (nat_lit 7)))) F →
@Eq.{1} Real (c.realReg (@OfNat.ofNat.{0} Nat (nat_lit 7) (instOfNatNat (nat_lit 7))))
(@Nat.cast.{0} Real Real.instNatCast F) →
@Eq.{1} Nat c.pc
(@HAdd.hAdd.{0, 0, 0} Nat Nat Nat (@instHAdd.{0} Nat instAddNat) offset
(@HMul.hMul.{0, 0, 0} Nat Nat Nat (@instHMul.{0} Nat instMulNat) width g.pc)) →
(∀ (slot : Nat),
@LT.lt.{0} Nat instLTNat slot width →
@Eq.{1} (Option.{0} DecrAlmostLinearSSSP.Decremental.Instruction)
(@GetElem?.getElem?.{0, 0, 0}
(List.{0} DecrAlmostLinearSSSP.Decremental.Instruction) Nat
DecrAlmostLinearSSSP.Decremental.Instruction
(fun as i =>
@LT.lt.{0} Nat instLTNat i
(@List.length.{0} DecrAlmostLinearSSSP.Decremental.Instruction as))
(@List.instGetElem?NatLtLength.{0} DecrAlmostLinearSSSP.Decremental.Instruction)
host.code
(@HAdd.hAdd.{0, 0, 0} Nat Nat Nat (@instHAdd.{0} Nat instAddNat) c.pc slot))
(@GetElem?.getElem?.{0, 0, 0}
(List.{0} DecrAlmostLinearSSSP.Decremental.Instruction) Nat
DecrAlmostLinearSSSP.Decremental.Instruction
(fun as i =>
@LT.lt.{0} Nat instLTNat i
(@List.length.{0} DecrAlmostLinearSSSP.Decremental.Instruction as))
(@List.instGetElem?NatLtLength.{0} DecrAlmostLinearSSSP.Decremental.Instruction)
(DecrAlmostLinearSSSP.Decremental.shadowBlock width offset returnPC g.pc ins)
slot)) →
∃ steps d,
And (@LE.le.{0} Nat instLENat steps width)
(And
(@Eq.{1} DecrAlmostLinearSSSP.Decremental.Machine
(DecrAlmostLinearSSSP.Decremental.execute host c steps) d)
(And
(DecrAlmostLinearSSSP.Decremental.ShadowRep base F d
(DecrAlmostLinearSSSP.Decremental.instructionEffect ins
{
pc :=
@HAdd.hAdd.{0, 0, 0} Nat Nat Nat (@instHAdd.{0} Nat instAddNat) g.pc
(@OfNat.ofNat.{0} Nat (nat_lit 1) (instOfNatNat (nat_lit 1))),
realReg := g.realReg, natReg := g.natReg, realMem := g.realMem,
natMem := g.natMem, halted := g.halted, fault := g.fault,
work :=
@HAdd.hAdd.{0, 0, 0} Nat Nat Nat (@instHAdd.{0} Nat instAddNat) g.work
(@OfNat.ofNat.{0} Nat (nat_lit 1) (instOfNatNat (nat_lit 1))) }))
(And
(@Eq.{1} Nat d.pc
(DecrAlmostLinearSSSP.Decremental.shadowDestination width offset returnPC
(DecrAlmostLinearSSSP.Decremental.instructionEffect ins
{
pc :=
@HAdd.hAdd.{0, 0, 0} Nat Nat Nat (@instHAdd.{0} Nat instAddNat) g.pc
(@OfNat.ofNat.{0} Nat (nat_lit 1) (instOfNatNat (nat_lit 1))),
realReg := g.realReg, natReg := g.natReg, realMem := g.realMem,
natMem := g.natMem, halted := g.halted, fault := g.fault,
work :=
@HAdd.hAdd.{0, 0, 0} Nat Nat Nat (@instHAdd.{0} Nat instAddNat) g.work
(@OfNat.ofNat.{0} Nat (nat_lit 1) (instOfNatNat (nat_lit 1))) })))
(And
(@Eq.{1} Nat d.work
(@HAdd.hAdd.{0, 0, 0} Nat Nat Nat (@instHAdd.{0} Nat instAddNat) c.work
steps))
(And (@Eq.{1} Bool d.halted Bool.false)
(And
(@Eq.{1} Nat
(d.natReg (@OfNat.ofNat.{0} Nat (nat_lit 0) (instOfNatNat (nat_lit 0))))
(c.natReg
(@OfNat.ofNat.{0} Nat (nat_lit 0) (instOfNatNat (nat_lit 0)))))
(And
(@Eq.{1} Nat
(d.natReg
(@OfNat.ofNat.{0} Nat (nat_lit 1) (instOfNatNat (nat_lit 1))))
(c.natReg
(@OfNat.ofNat.{0} Nat (nat_lit 1) (instOfNatNat (nat_lit 1)))))
(And
(@Eq.{1} Nat
(d.natReg
(@OfNat.ofNat.{0} Nat (nat_lit 7) (instOfNatNat (nat_lit 7))))
(c.natReg
(@OfNat.ofNat.{0} Nat (nat_lit 7) (instOfNatNat (nat_lit 7)))))
(And
(@Eq.{1} Real
(d.realReg
(@OfNat.ofNat.{0} Nat (nat_lit 7) (instOfNatNat (nat_lit 7))))
(c.realReg
(@OfNat.ofNat.{0} Nat (nat_lit 7) (instOfNatNat (nat_lit 7)))))
(@Eq.{1} Nat steps
(DecrAlmostLinearSSSP.Decremental.shadowSteps ins g)))))))))))))) ∧ (((∀ {base F : Nat} {c g : DecrAlmostLinearSSSP.Decremental.Machine},
DecrAlmostLinearSSSP.Decremental.ShadowRep base F c g →
∀ (host guest : DecrAlmostLinearSSSP.Decremental.Program) (width offset returnPC : Nat),
@LE.le.{0} Nat instLENat (@OfNat.ofNat.{0} Nat (nat_lit 8) (instOfNatNat (nat_lit 8))) width →
(∀ (ins : DecrAlmostLinearSSSP.Decremental.Instruction),
@Membership.mem.{0, 0} DecrAlmostLinearSSSP.Decremental.Instruction
(List.{0} DecrAlmostLinearSSSP.Decremental.Instruction)
(@List.instMembership.{0} DecrAlmostLinearSSSP.Decremental.Instruction) guest.code ins →
@LE.le.{0} Nat instLENat
(@HAdd.hAdd.{0, 0, 0} Nat Nat Nat (@instHAdd.{0} Nat instAddNat)
(DecrAlmostLinearSSSP.Decremental.naturalConstant ins)
(@OfNat.ofNat.{0} Nat (nat_lit 4) (instOfNatNat (nat_lit 4))))
width) →
DecrAlmostLinearSSSP.Decremental.ShadowEmbedsCode host guest width offset returnPC →
@LT.lt.{0} Nat instLTNat (@OfNat.ofNat.{0} Nat (nat_lit 0) (instOfNatNat (nat_lit 0))) F →
@Eq.{1} Bool c.halted Bool.false →
@Eq.{1} Nat (c.natReg (@OfNat.ofNat.{0} Nat (nat_lit 1) (instOfNatNat (nat_lit 1))))
(@OfNat.ofNat.{0} Nat (nat_lit 1) (instOfNatNat (nat_lit 1))) →
@Eq.{1} Bool g.halted Bool.false →
@Eq.{1} Nat (c.natReg (@OfNat.ofNat.{0} Nat (nat_lit 0) (instOfNatNat (nat_lit 0)))) base →
@Eq.{1} Nat (c.natReg (@OfNat.ofNat.{0} Nat (nat_lit 7) (instOfNatNat (nat_lit 7)))) F →
@Eq.{1} Real (c.realReg (@OfNat.ofNat.{0} Nat (nat_lit 7) (instOfNatNat (nat_lit 7))))
(@Nat.cast.{0} Real Real.instNatCast F) →
@Eq.{1} Nat c.pc
(DecrAlmostLinearSSSP.Decremental.shadowDestination width offset returnPC g) →
∀ (ins : DecrAlmostLinearSSSP.Decremental.Instruction),
@Eq.{1} (Option.{0} DecrAlmostLinearSSSP.Decremental.Instruction)
(@GetElem?.getElem?.{0, 0, 0} (List.{0} DecrAlmostLinearSSSP.Decremental.Instruction)
Nat DecrAlmostLinearSSSP.Decremental.Instruction
(fun as i =>
@LT.lt.{0} Nat instLTNat i
(@List.length.{0} DecrAlmostLinearSSSP.Decremental.Instruction as))
(@List.instGetElem?NatLtLength.{0} DecrAlmostLinearSSSP.Decremental.Instruction)
guest.code g.pc)
(@Option.some.{0} DecrAlmostLinearSSSP.Decremental.Instruction ins) →
∃ steps d,
And (@LE.le.{0} Nat instLENat steps width)
(And
(@Eq.{1} DecrAlmostLinearSSSP.Decremental.Machine
(DecrAlmostLinearSSSP.Decremental.execute host c steps) d)
(And
(DecrAlmostLinearSSSP.Decremental.ShadowRep base F d
(DecrAlmostLinearSSSP.Decremental.step guest g))
(And
(@Eq.{1} Nat d.pc
(DecrAlmostLinearSSSP.Decremental.shadowDestination width offset returnPC
(DecrAlmostLinearSSSP.Decremental.step guest g)))
(And
(@Eq.{1} Nat d.work
(@HAdd.hAdd.{0, 0, 0} Nat Nat Nat (@instHAdd.{0} Nat instAddNat) c.work
steps))
(And (@Eq.{1} Bool d.halted Bool.false)
(And
(@Eq.{1} Nat
(d.natReg
(@OfNat.ofNat.{0} Nat (nat_lit 0) (instOfNatNat (nat_lit 0))))
(c.natReg
(@OfNat.ofNat.{0} Nat (nat_lit 0) (instOfNatNat (nat_lit 0)))))
(And
(@Eq.{1} Nat
(d.natReg
(@OfNat.ofNat.{0} Nat (nat_lit 1) (instOfNatNat (nat_lit 1))))
(c.natReg
(@OfNat.ofNat.{0} Nat (nat_lit 1) (instOfNatNat (nat_lit 1)))))
(And
(@Eq.{1} Nat
(d.natReg
(@OfNat.ofNat.{0} Nat (nat_lit 7) (instOfNatNat (nat_lit 7))))
(c.natReg
(@OfNat.ofNat.{0} Nat (nat_lit 7) (instOfNatNat (nat_lit 7)))))
(@Eq.{1} Real
(d.realReg
(@OfNat.ofNat.{0} Nat (nat_lit 7) (instOfNatNat (nat_lit 7))))
(c.realReg
(@OfNat.ofNat.{0} Nat (nat_lit 7)
(instOfNatNat (nat_lit 7)))))))))))))) ∧ (∀ (host guest : DecrAlmostLinearSSSP.Decremental.Program) (width offset returnPC : Nat),
@LE.le.{0} Nat instLENat (@OfNat.ofNat.{0} Nat (nat_lit 8) (instOfNatNat (nat_lit 8))) width →
(∀ (ins : DecrAlmostLinearSSSP.Decremental.Instruction),
@Membership.mem.{0, 0} DecrAlmostLinearSSSP.Decremental.Instruction
(List.{0} DecrAlmostLinearSSSP.Decremental.Instruction)
(@List.instMembership.{0} DecrAlmostLinearSSSP.Decremental.Instruction) guest.code ins →
@LE.le.{0} Nat instLENat
(@HAdd.hAdd.{0, 0, 0} Nat Nat Nat (@instHAdd.{0} Nat instAddNat)
(DecrAlmostLinearSSSP.Decremental.naturalConstant ins)
(@OfNat.ofNat.{0} Nat (nat_lit 4) (instOfNatNat (nat_lit 4))))
width) →
DecrAlmostLinearSSSP.Decremental.ShadowEmbedsCode host guest width offset returnPC →
∀ (base F : Nat),
@LT.lt.{0} Nat instLTNat (@OfNat.ofNat.{0} Nat (nat_lit 0) (instOfNatNat (nat_lit 0))) F →
∀ (t : Nat) (c g : DecrAlmostLinearSSSP.Decremental.Machine),
DecrAlmostLinearSSSP.Decremental.ShadowRep base F c g →
@Eq.{1} Bool c.halted Bool.false →
@Eq.{1} Nat (c.natReg (@OfNat.ofNat.{0} Nat (nat_lit 1) (instOfNatNat (nat_lit 1))))
(@OfNat.ofNat.{0} Nat (nat_lit 1) (instOfNatNat (nat_lit 1))) →
@Eq.{1} Nat (c.natReg (@OfNat.ofNat.{0} Nat (nat_lit 0) (instOfNatNat (nat_lit 0)))) base →
@Eq.{1} Nat (c.natReg (@OfNat.ofNat.{0} Nat (nat_lit 7) (instOfNatNat (nat_lit 7)))) F →
@Eq.{1} Real (c.realReg (@OfNat.ofNat.{0} Nat (nat_lit 7) (instOfNatNat (nat_lit 7))))
(@Nat.cast.{0} Real Real.instNatCast F) →
@Eq.{1} Nat c.pc
(DecrAlmostLinearSSSP.Decremental.shadowDestination width offset returnPC g) →
(∀ (j : Nat),
@LT.lt.{0} Nat instLTNat j t →
@Eq.{1} Bool (DecrAlmostLinearSSSP.Decremental.execute guest g j).halted Bool.false →
∃ ins,
@Eq.{1} (Option.{0} DecrAlmostLinearSSSP.Decremental.Instruction)
(@GetElem?.getElem?.{0, 0, 0}
(List.{0} DecrAlmostLinearSSSP.Decremental.Instruction) Nat
DecrAlmostLinearSSSP.Decremental.Instruction
(fun as i =>
@LT.lt.{0} Nat instLTNat i
(@List.length.{0} DecrAlmostLinearSSSP.Decremental.Instruction as))
(@List.instGetElem?NatLtLength.{0}
DecrAlmostLinearSSSP.Decremental.Instruction)
guest.code (DecrAlmostLinearSSSP.Decremental.execute guest g j).pc)
(@Option.some.{0} DecrAlmostLinearSSSP.Decremental.Instruction ins)) →
∃ steps d,
And
(@LE.le.{0} Nat instLENat steps
(@HMul.hMul.{0, 0, 0} Nat Nat Nat (@instHMul.{0} Nat instMulNat) width t))
(And
(@Eq.{1} DecrAlmostLinearSSSP.Decremental.Machine
(DecrAlmostLinearSSSP.Decremental.execute host c steps) d)
(And
(DecrAlmostLinearSSSP.Decremental.ShadowRep base F d
(DecrAlmostLinearSSSP.Decremental.execute guest g t))
(And
(@Eq.{1} Nat d.pc
(DecrAlmostLinearSSSP.Decremental.shadowDestination width offset returnPC
(DecrAlmostLinearSSSP.Decremental.execute guest g t)))
(And
(@Eq.{1} Nat d.work
(@HAdd.hAdd.{0, 0, 0} Nat Nat Nat (@instHAdd.{0} Nat instAddNat) c.work
steps))
(And (@Eq.{1} Bool d.halted Bool.false)
(And
(@Eq.{1} Nat
(d.natReg (@OfNat.ofNat.{0} Nat (nat_lit 0) (instOfNatNat (nat_lit 0))))
(c.natReg
(@OfNat.ofNat.{0} Nat (nat_lit 0) (instOfNatNat (nat_lit 0)))))
(And
(@Eq.{1} Nat
(d.natReg
(@OfNat.ofNat.{0} Nat (nat_lit 1) (instOfNatNat (nat_lit 1))))
(c.natReg
(@OfNat.ofNat.{0} Nat (nat_lit 1) (instOfNatNat (nat_lit 1)))))
(And
(@Eq.{1} Nat
(d.natReg
(@OfNat.ofNat.{0} Nat (nat_lit 7) (instOfNatNat (nat_lit 7))))
(c.natReg
(@OfNat.ofNat.{0} Nat (nat_lit 7) (instOfNatNat (nat_lit 7)))))
(@Eq.{1} Real
(d.realReg
(@OfNat.ofNat.{0} Nat (nat_lit 7) (instOfNatNat (nat_lit 7))))
(c.realReg
(@OfNat.ofNat.{0} Nat (nat_lit 7)
(instOfNatNat (nat_lit 7))))))))))))))) ∧ ((∀ (host guest : DecrAlmostLinearSSSP.Decremental.Program) (offset returnPC : Nat),
DecrAlmostLinearSSSP.Decremental.ShadowEmbedsCode host guest (DecrAlmostLinearSSSP.Decremental.shadowWidth guest.code)
offset returnPC →
∀ (base F : Nat),
@LT.lt.{0} Nat instLTNat (@OfNat.ofNat.{0} Nat (nat_lit 0) (instOfNatNat (nat_lit 0))) F →
∀ (c g final : DecrAlmostLinearSSSP.Decremental.Machine),
DecrAlmostLinearSSSP.Decremental.ShadowRep base F c g →
@Eq.{1} Bool c.halted Bool.false →
@Eq.{1} Nat (c.natReg (@OfNat.ofNat.{0} Nat (nat_lit 1) (instOfNatNat (nat_lit 1))))
(@OfNat.ofNat.{0} Nat (nat_lit 1) (instOfNatNat (nat_lit 1))) →
@Eq.{1} Nat (c.natReg (@OfNat.ofNat.{0} Nat (nat_lit 0) (instOfNatNat (nat_lit 0)))) base →
@Eq.{1} Nat (c.natReg (@OfNat.ofNat.{0} Nat (nat_lit 7) (instOfNatNat (nat_lit 7)))) F →
@Eq.{1} Real (c.realReg (@OfNat.ofNat.{0} Nat (nat_lit 7) (instOfNatNat (nat_lit 7))))
(@Nat.cast.{0} Real Real.instNatCast F) →
@Eq.{1} Nat c.pc
(DecrAlmostLinearSSSP.Decremental.shadowDestination
(DecrAlmostLinearSSSP.Decremental.shadowWidth guest.code) offset returnPC g) →
DecrAlmostLinearSSSP.Decremental.Ends guest g final →
∃ steps d,
And
(@Eq.{1} DecrAlmostLinearSSSP.Decremental.Machine
(DecrAlmostLinearSSSP.Decremental.execute host c steps) d)
(And (DecrAlmostLinearSSSP.Decremental.ShadowRep base F d final)
(And (@Eq.{1} Nat d.pc returnPC)
(And
(@LE.le.{0} Nat instLENat d.work
(@HAdd.hAdd.{0, 0, 0} Nat Nat Nat (@instHAdd.{0} Nat instAddNat) c.work
(@HMul.hMul.{0, 0, 0} Nat Nat Nat (@instHMul.{0} Nat instMulNat)
(DecrAlmostLinearSSSP.Decremental.shadowWidth guest.code)
(@HSub.hSub.{0, 0, 0} Nat Nat Nat (@instHSub.{0} Nat instSubNat) final.work
g.work))))
(And (@Eq.{1} Bool d.halted Bool.false)
(And
(@Eq.{1} Nat
(d.natReg (@OfNat.ofNat.{0} Nat (nat_lit 0) (instOfNatNat (nat_lit 0))))
(c.natReg (@OfNat.ofNat.{0} Nat (nat_lit 0) (instOfNatNat (nat_lit 0)))))
(And
(@Eq.{1} Nat
(d.natReg (@OfNat.ofNat.{0} Nat (nat_lit 1) (instOfNatNat (nat_lit 1))))
(c.natReg (@OfNat.ofNat.{0} Nat (nat_lit 1) (instOfNatNat (nat_lit 1)))))
(And
(@Eq.{1} Nat
(d.natReg (@OfNat.ofNat.{0} Nat (nat_lit 7) (instOfNatNat (nat_lit 7))))
(c.natReg (@OfNat.ofNat.{0} Nat (nat_lit 7) (instOfNatNat (nat_lit 7)))))
(@Eq.{1} Real
(d.realReg (@OfNat.ofNat.{0} Nat (nat_lit 7) (instOfNatNat (nat_lit 7))))
(c.realReg
(@OfNat.ofNat.{0} Nat (nat_lit 7) (instOfNatNat (nat_lit 7))))))))))))) ∧ ((∀ (width : Nat) (ins : DecrAlmostLinearSSSP.Decremental.Instruction) (g : DecrAlmostLinearSSSP.Decremental.Machine),
@LE.le.{0} Nat instLENat (@OfNat.ofNat.{0} Nat (nat_lit 8) (instOfNatNat (nat_lit 8))) width →
@LE.le.{0} Nat instLENat
(@HAdd.hAdd.{0, 0, 0} Nat Nat Nat (@instHAdd.{0} Nat instAddNat)
(DecrAlmostLinearSSSP.Decremental.naturalConstant ins)
(@OfNat.ofNat.{0} Nat (nat_lit 4) (instOfNatNat (nat_lit 4))))
width →
@LE.le.{0} Nat instLENat (DecrAlmostLinearSSSP.Decremental.shadowSteps ins g) width) ∧ (∀ (width offset returnPC pc : Nat) (ins : DecrAlmostLinearSSSP.Decremental.Instruction)
(g : DecrAlmostLinearSSSP.Decremental.Machine),
Not (DecrAlmostLinearSSSP.Decremental.IsBranch ins) →
∀ (slot : Nat),
@LT.lt.{0} Nat instLTNat slot
(@HSub.hSub.{0, 0, 0} Nat Nat Nat (@instHSub.{0} Nat instSubNat)
(DecrAlmostLinearSSSP.Decremental.shadowSteps ins g)
(@OfNat.ofNat.{0} Nat (nat_lit 1) (instOfNatNat (nat_lit 1)))) →
∃ tr,
And
(@Eq.{1} (Option.{0} DecrAlmostLinearSSSP.Decremental.Instruction)
(@GetElem?.getElem?.{0, 0, 0} (List.{0} DecrAlmostLinearSSSP.Decremental.Instruction) Nat
DecrAlmostLinearSSSP.Decremental.Instruction
(fun as i =>
@LT.lt.{0} Nat instLTNat i (@List.length.{0} DecrAlmostLinearSSSP.Decremental.Instruction as))
(@List.instGetElem?NatLtLength.{0} DecrAlmostLinearSSSP.Decremental.Instruction)
(DecrAlmostLinearSSSP.Decremental.shadowBlock width offset returnPC pc ins) slot)
(@Option.some.{0} DecrAlmostLinearSSSP.Decremental.Instruction tr))
(DecrAlmostLinearSSSP.Decremental.Straight tr)))))) ∧ ((((∀ (host : DecrAlmostLinearSSSP.Decremental.Program) (c g : DecrAlmostLinearSSSP.Decremental.Machine)
(width offset returnPC : Nat) (ins : DecrAlmostLinearSSSP.Decremental.Instruction),
@LE.le.{0} Nat instLENat (@OfNat.ofNat.{0} Nat (nat_lit 8) (instOfNatNat (nat_lit 8))) width →
@LE.le.{0} Nat instLENat
(@HAdd.hAdd.{0, 0, 0} Nat Nat Nat (@instHAdd.{0} Nat instAddNat)
(DecrAlmostLinearSSSP.Decremental.naturalConstant ins)
(@OfNat.ofNat.{0} Nat (nat_lit 4) (instOfNatNat (nat_lit 4))))
width →
Not (DecrAlmostLinearSSSP.Decremental.IsBranch ins) →
@Eq.{1} Bool c.halted Bool.false →
(∀ (slot : Nat),
@LT.lt.{0} Nat instLTNat slot width →
@Eq.{1} (Option.{0} DecrAlmostLinearSSSP.Decremental.Instruction)
(@GetElem?.getElem?.{0, 0, 0} (List.{0} DecrAlmostLinearSSSP.Decremental.Instruction) Nat
DecrAlmostLinearSSSP.Decremental.Instruction
(fun as i =>
@LT.lt.{0} Nat instLTNat i (@List.length.{0} DecrAlmostLinearSSSP.Decremental.Instruction as))
(@List.instGetElem?NatLtLength.{0} DecrAlmostLinearSSSP.Decremental.Instruction) host.code
(@HAdd.hAdd.{0, 0, 0} Nat Nat Nat (@instHAdd.{0} Nat instAddNat) c.pc slot))
(@GetElem?.getElem?.{0, 0, 0} (List.{0} DecrAlmostLinearSSSP.Decremental.Instruction) Nat
DecrAlmostLinearSSSP.Decremental.Instruction
(fun as i =>
@LT.lt.{0} Nat instLTNat i (@List.length.{0} DecrAlmostLinearSSSP.Decremental.Instruction as))
(@List.instGetElem?NatLtLength.{0} DecrAlmostLinearSSSP.Decremental.Instruction)
(DecrAlmostLinearSSSP.Decremental.shadowBlock width offset returnPC g.pc ins) slot)) →
∀ (j : Nat),
@LT.lt.{0} Nat instLTNat j (DecrAlmostLinearSSSP.Decremental.shadowSteps ins g) →
And
(@Eq.{1} Nat (DecrAlmostLinearSSSP.Decremental.execute host c j).pc
(@HAdd.hAdd.{0, 0, 0} Nat Nat Nat (@instHAdd.{0} Nat instAddNat) c.pc j))
(And (@Eq.{1} Bool (DecrAlmostLinearSSSP.Decremental.execute host c j).halted Bool.false)
(@Eq.{1} Nat (DecrAlmostLinearSSSP.Decremental.execute host c j).work
(@HAdd.hAdd.{0, 0, 0} Nat Nat Nat (@instHAdd.{0} Nat instAddNat) c.work j)))) ∧ (∀ {base F : Nat} {c g : DecrAlmostLinearSSSP.Decremental.Machine},
DecrAlmostLinearSSSP.Decremental.ShadowRep base F c g →
∀ (host : DecrAlmostLinearSSSP.Decremental.Program) (width : Nat),
@LE.le.{0} Nat instLENat (@OfNat.ofNat.{0} Nat (nat_lit 8) (instOfNatNat (nat_lit 8))) width →
@LT.lt.{0} Nat instLTNat (@OfNat.ofNat.{0} Nat (nat_lit 0) (instOfNatNat (nat_lit 0))) F →
∀ (natural : Bool) (a b target : Nat),
@Eq.{1} Bool c.halted Bool.false →
@Eq.{1} Nat (c.natReg (@OfNat.ofNat.{0} Nat (nat_lit 1) (instOfNatNat (nat_lit 1))))
(@OfNat.ofNat.{0} Nat (nat_lit 1) (instOfNatNat (nat_lit 1))) →
@Eq.{1} (Option.{0} DecrAlmostLinearSSSP.Decremental.Instruction)
(@GetElem?.getElem?.{0, 0, 0} (List.{0} DecrAlmostLinearSSSP.Decremental.Instruction) Nat
DecrAlmostLinearSSSP.Decremental.Instruction
(fun as i =>
@LT.lt.{0} Nat instLTNat i (@List.length.{0} DecrAlmostLinearSSSP.Decremental.Instruction as))
(@List.instGetElem?NatLtLength.{0} DecrAlmostLinearSSSP.Decremental.Instruction) host.code c.pc)
(@Option.some.{0} DecrAlmostLinearSSSP.Decremental.Instruction
(DecrAlmostLinearSSSP.Decremental.Instruction.natural
(@OfNat.ofNat.{0} Nat (nat_lit 2) (instOfNatNat (nat_lit 2)))
(@HAdd.hAdd.{0, 0, 0} Nat Nat Nat (@instHAdd.{0} Nat instAddNat) g.pc
(@OfNat.ofNat.{0} Nat (nat_lit 1) (instOfNatNat (nat_lit 1)))))) →
@Eq.{1} (Option.{0} DecrAlmostLinearSSSP.Decremental.Instruction)
(@GetElem?.getElem?.{0, 0, 0} (List.{0} DecrAlmostLinearSSSP.Decremental.Instruction) Nat
DecrAlmostLinearSSSP.Decremental.Instruction
(fun as i =>
@LT.lt.{0} Nat instLTNat i (@List.length.{0} DecrAlmostLinearSSSP.Decremental.Instruction as))
(@List.instGetElem?NatLtLength.{0} DecrAlmostLinearSSSP.Decremental.Instruction) host.code
(@HAdd.hAdd.{0, 0, 0} Nat Nat Nat (@instHAdd.{0} Nat instAddNat) c.pc
(@OfNat.ofNat.{0} Nat (nat_lit 1) (instOfNatNat (nat_lit 1)))))
(@Option.some.{0} DecrAlmostLinearSSSP.Decremental.Instruction
(DecrAlmostLinearSSSP.Decremental.Instruction.nadd
(@OfNat.ofNat.{0} Nat (nat_lit 3) (instOfNatNat (nat_lit 3)))
(@OfNat.ofNat.{0} Nat (nat_lit 3) (instOfNatNat (nat_lit 3)))
(@OfNat.ofNat.{0} Nat (nat_lit 1) (instOfNatNat (nat_lit 1))))) →
@Eq.{1} (Option.{0} DecrAlmostLinearSSSP.Decremental.Instruction)
(@GetElem?.getElem?.{0, 0, 0} (List.{0} DecrAlmostLinearSSSP.Decremental.Instruction) Nat
DecrAlmostLinearSSSP.Decremental.Instruction
(fun as i =>
@LT.lt.{0} Nat instLTNat i
(@List.length.{0} DecrAlmostLinearSSSP.Decremental.Instruction as))
(@List.instGetElem?NatLtLength.{0} DecrAlmostLinearSSSP.Decremental.Instruction) host.code
(@HAdd.hAdd.{0, 0, 0} Nat Nat Nat (@instHAdd.{0} Nat instAddNat) c.pc
(@OfNat.ofNat.{0} Nat (nat_lit 2) (instOfNatNat (nat_lit 2)))))
(@Option.some.{0} DecrAlmostLinearSSSP.Decremental.Instruction
(DecrAlmostLinearSSSP.Decremental.branchInstruction natural
(DecrAlmostLinearSSSP.Decremental.shadowReg a)
(DecrAlmostLinearSSSP.Decremental.shadowReg b)
(@HAdd.hAdd.{0, 0, 0} Nat Nat Nat (@instHAdd.{0} Nat instAddNat) c.pc
(@OfNat.ofNat.{0} Nat (nat_lit 5) (instOfNatNat (nat_lit 5)))))) →
@Eq.{1} (Option.{0} DecrAlmostLinearSSSP.Decremental.Instruction)
(@GetElem?.getElem?.{0, 0, 0} (List.{0} DecrAlmostLinearSSSP.Decremental.Instruction) Nat
DecrAlmostLinearSSSP.Decremental.Instruction
(fun as i =>
@LT.lt.{0} Nat instLTNat i
(@List.length.{0} DecrAlmostLinearSSSP.Decremental.Instruction as))
(@List.instGetElem?NatLtLength.{0} DecrAlmostLinearSSSP.Decremental.Instruction) host.code
(@HAdd.hAdd.{0, 0, 0} Nat Nat Nat (@instHAdd.{0} Nat instAddNat) c.pc
(@OfNat.ofNat.{0} Nat (nat_lit 5) (instOfNatNat (nat_lit 5)))))
(@Option.some.{0} DecrAlmostLinearSSSP.Decremental.Instruction
(DecrAlmostLinearSSSP.Decremental.Instruction.natural
(@OfNat.ofNat.{0} Nat (nat_lit 2) (instOfNatNat (nat_lit 2))) target)) →
∀ (j : Nat),
@LT.lt.{0} Nat instLTNat j
(@ite.{1} Nat (DecrAlmostLinearSSSP.Decremental.branchTest natural g a b)
(Classical.propDecidable (DecrAlmostLinearSSSP.Decremental.branchTest natural g a b))
(@OfNat.ofNat.{0} Nat (nat_lit 5) (instOfNatNat (nat_lit 5)))
(@OfNat.ofNat.{0} Nat (nat_lit 4) (instOfNatNat (nat_lit 4)))) →
∃ slot,
And (@LT.lt.{0} Nat instLTNat slot width)
(@Eq.{1} Nat (DecrAlmostLinearSSSP.Decremental.execute host c j).pc
(@HAdd.hAdd.{0, 0, 0} Nat Nat Nat (@instHAdd.{0} Nat instAddNat) c.pc slot)))) ∧ ((∀ {base F : Nat} {c g : DecrAlmostLinearSSSP.Decremental.Machine},
DecrAlmostLinearSSSP.Decremental.ShadowRep base F c g →
∀ (host : DecrAlmostLinearSSSP.Decremental.Program) (width offset returnPC : Nat),
@LE.le.{0} Nat instLENat (@OfNat.ofNat.{0} Nat (nat_lit 8) (instOfNatNat (nat_lit 8))) width →
@LT.lt.{0} Nat instLTNat (@OfNat.ofNat.{0} Nat (nat_lit 0) (instOfNatNat (nat_lit 0))) F →
∀ (ins : DecrAlmostLinearSSSP.Decremental.Instruction),
@LE.le.{0} Nat instLENat
(@HAdd.hAdd.{0, 0, 0} Nat Nat Nat (@instHAdd.{0} Nat instAddNat)
(DecrAlmostLinearSSSP.Decremental.naturalConstant ins)
(@OfNat.ofNat.{0} Nat (nat_lit 4) (instOfNatNat (nat_lit 4))))
width →
@Eq.{1} Bool c.halted Bool.false →
@Eq.{1} Nat (c.natReg (@OfNat.ofNat.{0} Nat (nat_lit 1) (instOfNatNat (nat_lit 1))))
(@OfNat.ofNat.{0} Nat (nat_lit 1) (instOfNatNat (nat_lit 1))) →
@Eq.{1} Nat c.pc
(@HAdd.hAdd.{0, 0, 0} Nat Nat Nat (@instHAdd.{0} Nat instAddNat) offset
(@HMul.hMul.{0, 0, 0} Nat Nat Nat (@instHMul.{0} Nat instMulNat) width g.pc)) →
(∀ (slot : Nat),
@LT.lt.{0} Nat instLTNat slot width →
@Eq.{1} (Option.{0} DecrAlmostLinearSSSP.Decremental.Instruction)
(@GetElem?.getElem?.{0, 0, 0} (List.{0} DecrAlmostLinearSSSP.Decremental.Instruction) Nat
DecrAlmostLinearSSSP.Decremental.Instruction
(fun as i =>
@LT.lt.{0} Nat instLTNat i
(@List.length.{0} DecrAlmostLinearSSSP.Decremental.Instruction as))
(@List.instGetElem?NatLtLength.{0} DecrAlmostLinearSSSP.Decremental.Instruction) host.code
(@HAdd.hAdd.{0, 0, 0} Nat Nat Nat (@instHAdd.{0} Nat instAddNat) c.pc slot))
(@GetElem?.getElem?.{0, 0, 0} (List.{0} DecrAlmostLinearSSSP.Decremental.Instruction) Nat
DecrAlmostLinearSSSP.Decremental.Instruction
(fun as i =>
@LT.lt.{0} Nat instLTNat i
(@List.length.{0} DecrAlmostLinearSSSP.Decremental.Instruction as))
(@List.instGetElem?NatLtLength.{0} DecrAlmostLinearSSSP.Decremental.Instruction)
(DecrAlmostLinearSSSP.Decremental.shadowBlock width offset returnPC g.pc ins) slot)) →
∀ (j : Nat),
@LT.lt.{0} Nat instLTNat j (DecrAlmostLinearSSSP.Decremental.shadowSteps ins g) →
∃ slot,
And (@LT.lt.{0} Nat instLTNat slot width)
(@Eq.{1} Nat (DecrAlmostLinearSSSP.Decremental.execute host c j).pc
(@HAdd.hAdd.{0, 0, 0} Nat Nat Nat (@instHAdd.{0} Nat instAddNat) c.pc slot))) ∧ ((∀ (width offset returnPC pc : Nat) (ins tr : DecrAlmostLinearSSSP.Decremental.Instruction),
@Membership.mem.{0, 0} DecrAlmostLinearSSSP.Decremental.Instruction
(List.{0} DecrAlmostLinearSSSP.Decremental.Instruction)
(@List.instMembership.{0} DecrAlmostLinearSSSP.Decremental.Instruction)
(DecrAlmostLinearSSSP.Decremental.shadowBlock width offset returnPC pc ins) tr →
DecrAlmostLinearSSSP.Decremental.ModifiesMemory tr → DecrAlmostLinearSSSP.Decremental.ModifiesMemory ins) ∧ (∀ (width offset returnPC pc a d slot : Nat),
@LT.lt.{0} Nat instLTNat slot (@OfNat.ofNat.{0} Nat (nat_lit 7) (instOfNatNat (nat_lit 7))) →
∀ (tr : DecrAlmostLinearSSSP.Decremental.Instruction),
@Eq.{1} (Option.{0} DecrAlmostLinearSSSP.Decremental.Instruction)
(@GetElem?.getElem?.{0, 0, 0} (List.{0} DecrAlmostLinearSSSP.Decremental.Instruction) Nat
DecrAlmostLinearSSSP.Decremental.Instruction
(fun as i => @LT.lt.{0} Nat instLTNat i (@List.length.{0} DecrAlmostLinearSSSP.Decremental.Instruction as))
(@List.instGetElem?NatLtLength.{0} DecrAlmostLinearSSSP.Decremental.Instruction)
(DecrAlmostLinearSSSP.Decremental.shadowBlock width offset returnPC pc
(DecrAlmostLinearSSSP.Decremental.Instruction.store a d))
slot)
(@Option.some.{0} DecrAlmostLinearSSSP.Decremental.Instruction tr) →
DecrAlmostLinearSSSP.Decremental.ModifiesMemory tr →
And (@Eq.{1} Nat slot (@OfNat.ofNat.{0} Nat (nat_lit 5) (instOfNatNat (nat_lit 5))))
(@Eq.{1} DecrAlmostLinearSSSP.Decremental.Instruction tr
(DecrAlmostLinearSSSP.Decremental.Instruction.store
(@OfNat.ofNat.{0} Nat (nat_lit 6) (instOfNatNat (nat_lit 6)))
(DecrAlmostLinearSSSP.Decremental.shadowReg d))))))) ∧ (((∀ (width offset returnPC pc a d slot : Nat),
@LT.lt.{0} Nat instLTNat slot (@OfNat.ofNat.{0} Nat (nat_lit 7) (instOfNatNat (nat_lit 7))) →
∀ (tr : DecrAlmostLinearSSSP.Decremental.Instruction),
@Eq.{1} (Option.{0} DecrAlmostLinearSSSP.Decremental.Instruction)
(@GetElem?.getElem?.{0, 0, 0} (List.{0} DecrAlmostLinearSSSP.Decremental.Instruction) Nat
DecrAlmostLinearSSSP.Decremental.Instruction
(fun as i => @LT.lt.{0} Nat instLTNat i (@List.length.{0} DecrAlmostLinearSSSP.Decremental.Instruction as))
(@List.instGetElem?NatLtLength.{0} DecrAlmostLinearSSSP.Decremental.Instruction)
(DecrAlmostLinearSSSP.Decremental.shadowBlock width offset returnPC pc
(DecrAlmostLinearSSSP.Decremental.Instruction.storeN a d))
slot)
(@Option.some.{0} DecrAlmostLinearSSSP.Decremental.Instruction tr) →
DecrAlmostLinearSSSP.Decremental.ModifiesMemory tr →
And (@Eq.{1} Nat slot (@OfNat.ofNat.{0} Nat (nat_lit 5) (instOfNatNat (nat_lit 5))))
(@Eq.{1} DecrAlmostLinearSSSP.Decremental.Instruction tr
(DecrAlmostLinearSSSP.Decremental.Instruction.storeN
(@OfNat.ofNat.{0} Nat (nat_lit 6) (instOfNatNat (nat_lit 6)))
(DecrAlmostLinearSSSP.Decremental.shadowReg d)))) ∧ (∀ (ins : DecrAlmostLinearSSSP.Decremental.Instruction) (c : DecrAlmostLinearSSSP.Decremental.Machine) (address : Nat),
Not (DecrAlmostLinearSSSP.Decremental.ModifiesMemory ins) →
Not (DecrAlmostLinearSSSP.Decremental.WritesAddress ins c address))) ∧ ((∀ (p : DecrAlmostLinearSSSP.Decremental.Program) (c : DecrAlmostLinearSSSP.Decremental.Machine)
(ins : DecrAlmostLinearSSSP.Decremental.Instruction) (address : Nat),
@Eq.{1} Bool c.halted Bool.false →
@Eq.{1} (Option.{0} DecrAlmostLinearSSSP.Decremental.Instruction)
(@GetElem?.getElem?.{0, 0, 0} (List.{0} DecrAlmostLinearSSSP.Decremental.Instruction) Nat
DecrAlmostLinearSSSP.Decremental.Instruction
(fun as i => @LT.lt.{0} Nat instLTNat i (@List.length.{0} DecrAlmostLinearSSSP.Decremental.Instruction as))
(@List.instGetElem?NatLtLength.{0} DecrAlmostLinearSSSP.Decremental.Instruction) p.code c.pc)
(@Option.some.{0} DecrAlmostLinearSSSP.Decremental.Instruction ins) →
Not (DecrAlmostLinearSSSP.Decremental.WritesAddress ins c address) →
And (@Eq.{1} Real ((DecrAlmostLinearSSSP.Decremental.step p c).realMem address) (c.realMem address))
(@Eq.{1} Nat ((DecrAlmostLinearSSSP.Decremental.step p c).natMem address) (c.natMem address))) ∧ ((∀ (p : DecrAlmostLinearSSSP.Decremental.Program) (c : DecrAlmostLinearSSSP.Decremental.Machine) (t address : Nat),
(∀ (j : Nat),
@LT.lt.{0} Nat instLTNat j t →
∀ (ins : DecrAlmostLinearSSSP.Decremental.Instruction),
@Eq.{1} (Option.{0} DecrAlmostLinearSSSP.Decremental.Instruction)
(@GetElem?.getElem?.{0, 0, 0} (List.{0} DecrAlmostLinearSSSP.Decremental.Instruction) Nat
DecrAlmostLinearSSSP.Decremental.Instruction
(fun as i =>
@LT.lt.{0} Nat instLTNat i (@List.length.{0} DecrAlmostLinearSSSP.Decremental.Instruction as))
(@List.instGetElem?NatLtLength.{0} DecrAlmostLinearSSSP.Decremental.Instruction) p.code
(DecrAlmostLinearSSSP.Decremental.execute p c j).pc)
(@Option.some.{0} DecrAlmostLinearSSSP.Decremental.Instruction ins) →
Not
(DecrAlmostLinearSSSP.Decremental.WritesAddress ins (DecrAlmostLinearSSSP.Decremental.execute p c j)
address)) →
And (@Eq.{1} Real ((DecrAlmostLinearSSSP.Decremental.execute p c t).realMem address) (c.realMem address))
(@Eq.{1} Nat ((DecrAlmostLinearSSSP.Decremental.execute p c t).natMem address) (c.natMem address))) ∧ (∀ (ins : DecrAlmostLinearSSSP.Decremental.Instruction) (c : DecrAlmostLinearSSSP.Decremental.Machine) (address : Nat),
DecrAlmostLinearSSSP.Decremental.WritesAddress ins c address → DecrAlmostLinearSSSP.Decremental.ModifiesMemory ins)))))))) := by sorry