AFTD Auto-Formalizing Theoretical Domains

op75_tm2_two_push_one_step

theoremverified

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

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.

  1. 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.

    line 3

      refine ⟨{ steps := 1, evals_in_steps := ?_, steps_le_m := by omega }⟩
  2. 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.

    line 4

      rfl

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

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
See it in the graphDiscuss this resultChallenge it