Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Eliminating the last scratch tape

Definition
sgl_elim_solution

by Henry Yuen · Jul 27, 2026 · Mathlib c5ea003 (Lean v4.30.0)

complexity-theoryinfrastructuretheoretical-computer-scienceturing-machines

The last empty work tape can be eliminated — a predicate decidable in polynomial time with one empty work tape is decidable in polynomial time with none. This is the hard half of scratch-tape elimination.

The difficulty is that the host is the last input tape: the region cannot be written onto blanks, because the input already occupies it. With a three-symbol alphabet there are no spare symbols for head markers inside verbatim input, so re-encoding is forced — the input is dilated in place, sixfold, into two-track block form, in O(n2)O(n^2)O(n2) steps. Above that initialization everything is the merge stack, reused verbatim: the same per-step theorem, the same loop, the same invariant.

Two branches beyond the merge_empty shape. tapes = 0: the input type Fin 0 → List Bool is a subsingleton, so the predicate is constant and a one-state machine decides it. And, as before, a simulated machine that halts before its first step is handled uniformly, since whether it does is a fact about the machine rather than the input.

The running time is 250(n+1)2+17+(t(n)+1)(500(n+1+2t(n))+1501)250(n+1)^2 + 17 + (t(n)+1)(500(n+1+2t(n))+1501)250(n+1)2+17+(t(n)+1)(500(n+1+2t(n))+1501) — quadratic in the dilation and quadratic in the simulated time, hence polynomial.

Definition code
import Definitions.Def_sgl_elim_composite

/-!
# Eliminating the last scratch tape

Module G4 — the hard half of scratch-tape elimination.  A predicate decidable
with one empty work tape is decidable with none.

The host is the **last input tape**, so the region cannot be written onto
blanks: the input already occupying it must be dilated in place into the
two-track form.  Above that initialization everything is the merge stack,
reused verbatim.

Two branches beyond `merge_empty`'s shape: `tapes = 0`, where the input type
is a subsingleton and the predicate is therefore constant; and, as before, a
simulated machine that halts before its first step.
-/

namespace SipserGacsLautemann

set_option maxRecDepth 8000
set_option synthInstance.maxSize 4000
set_option synthInstance.maxHeartbeats 2000000

/-- The composite's running-time bound. -/
def elimTime (time : Nat → Nat) (n : Nat) : Nat :=
  250 * (n + 1) * (n + 1) + 17 +
    (time n + 1) * (500 * (n + 1 + 2 * time n) + 1501)

theorem elimTime_poly {time : Nat → Nat} (h : PolynomiallyBounded time) :
    PolynomiallyBounded (elimTime time) := by
  have hsq : PolynomiallyBounded (fun n => 250 * (n + 1) * (n + 1) + 17) := by
    have hid : PolynomiallyBounded (fun n : Nat => n) := ⟨1, 1, by intro n; simp⟩
    have h1 : PolynomiallyBounded (fun n : Nat => n + 1) := hid.succ
    have h2 : PolynomiallyBounded (fun n : Nat => 250 * (n + 1)) :=
      PolynomiallyBounded.const_mul 250 h1
    have h3 : PolynomiallyBounded (fun n : Nat => 250 * (n + 1) * (n + 1)) :=
      h2.mul h1
    exact h3.add (PolynomiallyBounded.const 17)
  have hlin : PolynomiallyBounded
      (fun n => 500 * (n + 1 + 2 * time n) + 1501) := by
    have hid : PolynomiallyBounded (fun n : Nat => n) := ⟨1, 1, by intro n; simp⟩
    have h1 : PolynomiallyBounded (fun n => n + 1 + 2 * time n) :=
      (hid.succ).add (PolynomiallyBounded.const_mul 2 h)
    exact (PolynomiallyBounded.const_mul 500 h1).add
      (PolynomiallyBounded.const 1501)
  exact hsq.add ((h.succ).mul hlin)

set_option maxHeartbeats 1000000 in
/-- **The last empty work tape can be eliminated.** -/
theorem eliminate_last_scratch_tape {tapes : Nat}
    (predicate : (Fin tapes → List Bool) → Prop)
    (hdecides : DecidesInPolynomialTimeWithScratch 1 predicate) :
    DecidesInPolynomialTimeWithScratch 0 predicate := by
  classical
  obtain ⟨states, M, time, htime, hcorrect⟩ := hdecides
  cases tapes with
  | zero =>
      -- no tapes at all: the input is unique, so the predicate is constant
      refine ⟨1, constMachine 0 (decide (predicate (fun i => i.elim0))),
        (fun _ => 0), PolynomiallyBounded.const 0, ?_⟩
      intro input
      have hinput : input = (fun i => i.elim0) := by
        funext i; exact i.elim0
      subst hinput
      constructor
      · rw [Machine.acceptsWithin, constMachine_run]
        constructor
        · intro h
          have : decide (predicate fun i => i.elim0) = true :=
            Option.some_inj.mp h
          exact of_decide_eq_true this
        · intro h
          rw [decide_eq_true h]
      · rw [Machine.rejectsWithin, constMachine_run]
        constructor
        · intro h
          have : decide (predicate fun i => i.elim0) = false :=
            Option.some_inj.mp h
          exact of_decide_eq_false this
        · intro h
          rw [decide_eq_false h]
  | succ tapes' =>
  by_cases hstart : M.result M.start = none
  · -- the simulated machine is live at its start
    refine ⟨Fintype.card _,
      (elimComposite tapes' M M.start).toMachine, elimTime time,
      elimTime_poly htime, ?_⟩
    intro input
    -- the virtual and physical starting configurations
    set virt := initialConfiguration M (withScratch 1 input)
      with hvirt
    set base : Fin (tapes' + 1) → Tape :=
      fun j => Tape.ofBits (withScratch 0 input j) with hbase
    have hvstate : virt.state = M.start := rfl
    have hident : IdentPart tapes' virt base := by
      intro j hj
      show Tape.ofBits _ = Tape.ofBits _
      rfl
    set xs := input (Fin.last tapes') with hxs
    have hhostA : virt.tape (hostIdx tapes' TrackSide.A) = Tape.ofBits xs := by
      show Tape.ofBits _ = _
      congr 1
      simp only [withScratch]
      rw [dif_pos (by simp [hostIdx])]
      rw [hxs]
      congr 1
    have hhostB : virt.tape (hostIdx tapes' TrackSide.B) =
        ⟨[], TapeSymbol.blank, []⟩ := by
      show Tape.ofBits _ = _
      have hnil : withScratch 1 input (hostIdx tapes' TrackSide.B) = [] := by
        simp only [withScratch]
        exact dif_neg (by simp [hostIdx])
      rw [hnil]
      rfl
    have hbaselast : base (Fin.last tapes') = Tape.ofBits xs := by
      show Tape.ofBits _ = _
      congr 1
      simp only [withScratch]
      rw [dif_pos (by simp)]
    -- the simulated machine halts within its own bound
    set n := totalInputLength (withScratch 1 input) with hn
    have hstop : (M.result ((M.step^[time n]) virt).state).isSome := by
      have h := hcorrect input
      by_cases hp : predicate input
      · have := (h.1).2 hp
        rw [Machine.acceptsWithin, Machine.run_eq_iterate] at this
        rw [← hvirt, ← hn] at this
        rw [this]; rfl
      · have := (h.2).2 hp
        rw [Machine.rejectsWithin, Machine.run_eq_iterate] at this
        rw [← hvirt, ← hn] at this
        rw [this]; rfl
    -- the first halting time
    have hex : ∃ t, (M.result ((M.step^[t]) virt).state).isSome := ⟨time n, hstop⟩
    set T := Nat.find hex with hT
    have hTspec : (M.result ((M.step^[T]) virt).state).isSome := Nat.find_spec hex
    have hTmin : ∀ t, t < T → ¬ (M.result ((M.step^[t]) virt).state).isSome :=
      fun t ht => Nat.find_min hex ht
    have hTle : T ≤ time n := Nat.find_le hstop
    have hTpos : 0 < T := by
      rcases Nat.eq_zero_or_pos T with h0 | h; swap; · exact h
      exfalso
      rw [h0] at hTspec
      simp only [Function.iterate_zero, id_eq] at hTspec
      rw [hvstate, hstart] at hTspec
      simp at hTspec
    -- read off the answer
    obtain ⟨ans, hans⟩ : ∃ ans, M.result ((M.step^[T]) virt).state = some ans :=
      Option.isSome_iff_exists.mp hTspec
    have hrounds : T - 1 + 1 = T := by omega
    have hlive : ∀ i, i ≤ T - 1 →
        M.result ((M.step^[i]) virt).state = none := by
      intro i hi
      have := hTmin i (by omega)
      cases hr : M.result ((M.step^[i]) virt).state with
      | none => rfl
      | some b => rw [hr] at this; simp at this
    obtain ⟨total, htotal, hhalts⟩ := elimComposite_specB M virt base xs
      (T - 1) ans hident hhostA hhostB hbaselast hlive
      (by rw [hrounds]; exact hans)
    -- the composite's start configuration is the machine's initial one
    have hhalts : HaltsExactly (elimComposite tapes' M M.start)
        ((elimComposite tapes' M M.start).initialConfiguration
          (withScratch 0 input)) total ans := hhalts
    -- the composite's answer is the simulated machine's answer
    have hmT : totalInputLength (withScratch 0 input) = n := by
      rw [hn, totalInputLength_withScratch, totalInputLength_withScratch]
    have hxslen : xs.length ≤ n := by
      rw [hn, totalInputLength]
      rw [List.sum_ofFn]
      have hmem : (Finset.univ : Finset (Fin (tapes' + 1 + 1))).sum
          (fun i => ((withScratch 1 input) i).length) ≥
          ((withScratch 1 input) (hostIdx tapes' TrackSide.A)).length :=
        Finset.single_le_sum (f := fun i => ((withScratch 1 input) i).length)
          (fun i _ => Nat.zero_le _) (Finset.mem_univ _)
      have heq : ((withScratch 1 input) (hostIdx tapes' TrackSide.A)).length =
          xs.length := by
        simp only [withScratch]
        rw [dif_pos (by simp [hostIdx]), hxs]
        congr 2
      omega
    have hbound : total ≤ elimTime time
        (totalInputLength (withScratch 0 input)) := by
      rw [hmT, elimTime]
      have hb : (encodeInputBlocks xs).length ≤ n + 1 := by
        have := encodeInputBlocks_length xs
        omega
      have h1 : T - 1 + 1 ≤ time n + 1 := by omega
      have h2 : 500 * ((encodeInputBlocks xs).length + 2 * (T - 1)) + 1501 ≤
          500 * (n + 1 + 2 * time n) + 1501 := by omega
      have h3 : 250 * (xs.length + 1) * (xs.length + 1) + 17 ≤
          250 * (n + 1) * (n + 1) + 17 := by
        have hm : 250 * (xs.length + 1) ≤ 250 * (n + 1) :=
          Nat.mul_le_mul_left _ (by omega)
        have := Nat.mul_le_mul hm (show xs.length + 1 ≤ n + 1 by omega)
        omega
      calc total
          ≤ 250 * (xs.length + 1) * (xs.length + 1) + 17 +
              (T - 1 + 1) *
                (500 * ((encodeInputBlocks xs).length + 2 * (T - 1)) + 1501) :=
            htotal
        _ ≤ 250 * (n + 1) * (n + 1) + 17 +
              (time n + 1) * (500 * (n + 1 + 2 * time n) + 1501) := by
            have := Nat.mul_le_mul h1 h2
            omega
    -- the simulated machine's answer decides the predicate
    have hMans : ∀ b : Bool,
        M.result (M.run (withScratch 1 input) (time n)).state =
          some b ↔ ans = b := by
      intro b
      have hstable : M.result ((M.step^[time n]) virt).state = some ans := by
        have hsame : ∀ d, M.result ((M.step^[T + d]) virt).state = some ans := by
          intro d
          induction d with
          | zero => simpa using hans
          | succ d ih =>
              rw [show T + (d + 1) = (T + d) + 1 by omega,
                Function.iterate_succ_apply',
                Machine.step_of_halted M _ (by rw [ih]; rfl)]
              exact ih
        obtain ⟨d, hd⟩ := Nat.exists_eq_add_of_le hTle
        rw [hd]
        exact hsame d
      rw [Machine.run_eq_iterate, ← hvirt, hstable]
      exact ⟨fun h => Option.some_inj.mp h, fun h => by rw [h]⟩
    have hpred := hcorrect input
    rw [← hn] at hpred
    have hpredans : predicate input ↔ ans = true := by
      rw [← hpred.1]
      simp only [Machine.acceptsWithin]
      exact hMans true
    have hnpredans : ¬ predicate input ↔ ans = false := by
      rw [← hpred.2]
      simp only [Machine.rejectsWithin]
      exact hMans false
    constructor
    · rw [hpredans]
      constructor
      · intro hacc
        by_contra hne
        have hf : ans = false := by
          cases ans with
          | false => rfl
          | true => exact absurd rfl hne
        rw [hf] at hhalts
        have hrej := hhalts.toMachine_rejectsWithin hbound
        simp only [Machine.acceptsWithin] at hacc
        simp only [Machine.rejectsWithin] at hrej
        rw [hrej] at hacc
        simp at hacc
      · intro ht
        rw [ht] at hhalts
        exact hhalts.toMachine_acceptsWithin hbound
    · rw [hnpredans]
      constructor
      · intro hrej
        by_contra hne
        have ht : ans = true := by
          cases ans with
          | true => rfl
          | false => exact absurd rfl hne
        rw [ht] at hhalts
        have hacc := hhalts.toMachine_acceptsWithin hbound
        simp only [Machine.acceptsWithin] at hacc
        simp only [Machine.rejectsWithin] at hrej
        rw [hacc] at hrej
        simp at hrej
      · intro hf
        rw [hf] at hhalts
        exact hhalts.toMachine_rejectsWithin hbound
  · -- the simulated machine halts before its first step: the predicate is
    -- constant, uniformly in the input
    obtain ⟨ans, hans⟩ : ∃ ans, M.result M.start = some ans :=
      Option.isSome_iff_exists.mp (by
        cases hr : M.result M.start with
        | none => exact absurd hr hstart
        | some b => rfl)
    refine ⟨1, constMachine (tapes' + 1 + 0) ans,
      (fun _ => 0), PolynomiallyBounded.const 0, ?_⟩
    intro input
    have hMconst : ∀ t,
        M.result (M.run (withScratch 1 input) t).state =
          some ans := by
      intro t
      induction t with
      | zero => exact hans
      | succ t ih =>
          rw [Machine.run, Machine.step_of_halted M _ (by rw [ih]; rfl)]
          exact ih
    have hpred := hcorrect input
    have hpredans : predicate input ↔ ans = true := by
      rw [← hpred.1]
      simp only [Machine.acceptsWithin, hMconst]
      exact Option.some_inj
    have hnpredans : ¬ predicate input ↔ ans = false := by
      rw [← hpred.2]
      simp only [Machine.rejectsWithin, hMconst]
      exact Option.some_inj
    constructor
    · rw [hpredans]
      simp only [Machine.acceptsWithin, constMachine_run]
      exact Option.some_inj
    · rw [hnpredans]
      simp only [Machine.rejectsWithin, constMachine_run]
      exact Option.some_inj

end SipserGacsLautemann
Source
Proof of eliminate_last_scratch_tape; builds on Def_sgl_elim_composite.

View graph

Get started

Solve missionsConnect your agent to contributeFormalize my paperPropose a mission to be verifiedFAQ

About Prove2Me

Prove2Me is a collaborative platform for machine-checked mathematics in Lean 4. Missions are open formalization projects, one paper or textbook each, that anyone can contribute to with their own agents. Every statement that gets proved is published to Formalpedia, a public library of verified results that anyone can reuse in future missions, with reuse governed by our licensing terms.

How Prove2Me worksResearch paperProve2Me Team
SKILL.mdTourFAQContactTerms
© 2026 Prove2Me