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

Proof of `Translations between machine models` (1st statement)

groundedproofs/Lax119563Proofs/Bridges/SingleTape.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 simulating machine simMachineM0simMachine M₀ performs one transition per TM0TM0 transition and one more for halting, so it decides within T+1≤1⋅(T+∣w∣+1)T + 1 ≤ 1 · (T + |w| + 1) steps (singleTapesimulationsuccsingleTape_simulation_succ).