op75_tm2_two_push_one_step
The explicit machine outputs two true symbols from an empty input in one TM2 step.
Statement
theorem op75_tm2_two_push_one_step :
Nonempty (Turing.TM2OutputsInTime op75_tm2_double_push_machine [] (some [true,true]) 1)- Source
- OP-75 Karp-reduction composition: finite-statement stack-growth bound in the repository TM2 model.
- Verified
- 15 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 1
- op75_tm2_double_push_machineA finite one-stack TM2 whose single statement pushes true twice and then halts.
The proof, explained
To show that the machine outputs `[true, true]` within 1 step on empty input, we provide a witness of computation in exactly 1 step. The step bound $1 \le 1$ is immediate, and running the machine for 1 step definitionally evaluates the program's two push operations and halts with the desired output.
It suffices to show that running the machine for exactly 1 step evaluates to the output `[true, true]`. automation
We instantiate the `Nonempty` witness with an execution of length 1. The time bound requirement $1 \le 1$ is discharged automatically by `omega`, leaving only the evaluation claim.
refine ⟨{ steps := 1, evals_in_steps := ?_, steps_le_m := by omega }⟩
Running the machine for 1 step from the initial state on empty input outputs `[true, true]`.
This holds by reflexivity (`rfl`): computing one step of `op75_tm2_double_push_machine` evaluates its statement block, which pushes `true` twice onto the stack and halts.
rfl
- In Lean's TM2 model, a single transition step executes an entire statement block. Here, that block contains two stack push operations followed by a halt, so both symbols are output in a single step.
Written by a model (gemini-3.8-flash) from the Lean proof and the goal states Lean reported at each step. Lean verified the proof; this explanation is a reading aid and is not itself machine-checked.
Lean source view module on GitHub
Choose a tactic — a marked line — to see the goals Lean had before and after it, as in Lean’s infoview. Step with ← → or j k.
theorem op75_tm2_two_push_one_step : Nonempty (Turing.TM2OutputsInTime op75_tm2_double_push_machine [] (some [true,true]) 1) := by refine ⟨{ steps := 1, evals_in_steps := ?_, steps_le_m := by omega }⟩ rfl