Eliminating the last scratch tape
Definitionsgl_elim_solutionThe 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 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 — quadratic in the dilation and quadratic in the simulated time, hence polynomial.
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