While this submission is a draft, it cannot be used by other submissions.

Proof of `Translations between machine models` (2nd statement)

groundedproofs/Lax119563Proofs/Bridges/ToTM2.lean · lax-119563

What this proof establishes

Assuming the claims on the left, the claim on the right holds — checked by the archive's pipeline. Proof code is not displayed here.

Read the Lean proof on GitHub

Description

The stack machine tmRidInidOuttm R idIn idOut simulates RR (TM2Sim.simulateTM2Sim.simulate) within 30(∣x∣+T)+3030 (|x| + T) + 30 steps for T=C(∣x∣+1)dT = C (|x| + 1)^d, a polynomial in ∣x∣|x|.