Merging two empty scratch tapes into one
Definitionsgl_merge_solutionTwo empty work tapes can be merged into one — a predicate decidable in polynomial time with empty work tapes is decidable in polynomial time with .
Two of the simulated machine's tapes are hosted as interleaved tracks of one physical tape: a block carries one cell of each track plus a flag marking where each track's head sits, and the region is a list of blocks parked with the physical head on a blank to its left. One stepProgram per simulated step reads both hosted symbols, applies the simulated transition to the identity-mapped tapes, updates each track, and parks the next state, preserving the merge invariant.
Three facts make it work. The hosted tapes start empty — the theorem's hypothesis, and the reason this is the tractable half of tape elimination: the initial region is a single blank block flagged on both tracks, so each track's projection is the empty tape and the initial invariant is one block and two reflexivities. The region grows by at most two blocks per step, one per track and only when a head steps off the end, so after steps it is , each step costs , and the simulation is quadratic — polynomial in, polynomial out. The degenerate case is uniform in the input: whether the simulated machine halts before its first step is decided by M.result M.start, a fact about the machine, so it splits off once at the top, and there the predicate is constant and a one-state machine decides it.
Two incidental findings. The index arithmetic relating to needs no casts, since Nat.add recurses on its second argument and the two are definitionally equal. And the composite's state type — seventeen layers of sums and products over an Option of a function type — has a Fintype instance by ordinary synthesis, so converting to a Machine needs no bespoke encoding.
import Definitions.Def_sgl_merge_compose
/-!
# Merging two empty scratch tapes into one
Module F4 — the campaign's target. A predicate decidable in polynomial time
with `scratch + 2` empty work tapes is decidable in polynomial time with
`scratch + 1`.
The construction is everything above: two of the simulated machine's tapes are
hosted as interleaved tracks of a single physical tape, and one `stepProgram`
per simulated step keeps the merge invariant. What is left here is the
bookkeeping.
* **The degenerate case is uniform, not per-input.** Whether the simulated
machine halts before its first step depends only on `M.result M.start` — a
fact about the machine, not the input. So it splits off once, at the top,
and in that branch the predicate is *constant* and a one-state machine
decides it.
* **The halting round is chosen per input** by well-ordering: the least time
at which the simulated machine's result is not `none`. It is at least one
(that is the non-degenerate branch) and at most the given time bound.
* **The time bound is quadratic** in the simulated one, because the hosted
region grows by at most two blocks per simulated step.
-/
namespace SipserGacsLautemann
set_option synthInstance.maxSize 4000
set_option synthInstance.maxHeartbeats 2000000
/-- The one-state machine that always reports `ans`. -/
def constMachine (n : Nat) (ans : Bool) : Machine n 1 where
start := ⟨0, by omega⟩
transition := fun s symbols => (s, fun j => (symbols j, HeadMove.stay))
result := fun _ => some ans
@[simp] theorem constMachine_run (n : Nat) (ans : Bool)
(input : Fin n → List Bool) (t : Nat) :
(constMachine n ans).result ((constMachine n ans).run input t).state =
some ans := rfl
/-- The composite's running-time bound. -/
def mergeTime (time : Nat → Nat) (n : Nat) : Nat :=
15 + (time n + 1) * (500 * (1 + 2 * time n) + 1501)
theorem mergeTime_poly {time : Nat → Nat} (h : PolynomiallyBounded time) :
PolynomiallyBounded (mergeTime time) := by
have h1 : PolynomiallyBounded (fun n => 500 * (1 + 2 * time n) + 1501) := by
have : PolynomiallyBounded (fun n => 1 + 2 * time n) :=
(PolynomiallyBounded.const 1).add (PolynomiallyBounded.const_mul 2 h)
exact (PolynomiallyBounded.const_mul 500 this).add
(PolynomiallyBounded.const 1501)
have h2 := (h.succ).mul h1
exact (PolynomiallyBounded.const 15).add h2
set_option maxHeartbeats 1000000 in
/-- **Two empty work tapes can be merged into one.** -/
theorem merge_empty_scratch_tapes {tapes : Nat} (scratch : Nat)
(predicate : (Fin tapes → List Bool) → Prop)
(hdecides : DecidesInPolynomialTimeWithScratch (scratch + 2) predicate) :
DecidesInPolynomialTimeWithScratch (scratch + 1) predicate := by
classical
obtain ⟨states, M, time, htime, hcorrect⟩ := hdecides
-- `tapes + (scratch + 2)` is definitionally `(tapes + scratch) + 2`
by_cases hstart : M.result M.start = none
· -- the simulated machine is live at its start
refine ⟨Fintype.card _,
(mergeComposite (tapes + scratch) M M.start).toMachine, mergeTime time,
mergeTime_poly htime, ?_⟩
intro input
-- the virtual and physical starting configurations
set virt := initialConfiguration M (withScratch (scratch + 2) input)
with hvirt
set base : Fin (tapes + scratch + 1) → Tape :=
fun j => Tape.ofBits (withScratch (scratch + 1) input j) with hbase
have hvstate : virt.state = M.start := rfl
have hident : IdentPart (tapes + scratch) virt base := by
intro j hj
show Tape.ofBits _ = Tape.ofBits _
rfl
have hhost : ∀ sd,
virt.tape (hostIdx (tapes + scratch) sd) =
⟨[], TapeSymbol.blank, []⟩ := by
intro sd
show Tape.ofBits _ = _
have hnil : withScratch (scratch + 2) input
(hostIdx (tapes + scratch) sd) = [] := by
simp only [withScratch]
exact dif_neg (by cases sd <;> simp [hostIdx] <;> omega)
rw [hnil]
rfl
have hbaselast : base (Fin.last (tapes + scratch)) =
⟨[], TapeSymbol.blank, []⟩ := by
show Tape.ofBits _ = _
have hnil : withScratch (scratch + 1) input
(Fin.last (tapes + scratch)) = [] := by
simp only [withScratch]
exact dif_neg (by simp)
rw [hnil]
rfl
-- the simulated machine halts within its own bound
set n := totalInputLength (withScratch (scratch + 2) 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⟩ := mergeComposite_spec M virt base (T - 1)
ans hident hhost hbaselast hlive (by rw [hrounds]; exact hans)
-- the composite's start configuration is the machine's initial one
have hhalts : HaltsExactly (mergeComposite (tapes + scratch) M M.start)
((mergeComposite (tapes + scratch) M M.start).initialConfiguration
(withScratch (scratch + 1) input)) total ans := hhalts
-- the composite's answer is the simulated machine's answer
have hmT : totalInputLength (withScratch (scratch + 1) input) = n := by
rw [hn, totalInputLength_withScratch, totalInputLength_withScratch]
have hbound : total ≤ mergeTime time
(totalInputLength (withScratch (scratch + 1) input)) := by
rw [hmT, mergeTime]
have h1 : T - 1 + 1 ≤ time n + 1 := by omega
have h2 : 500 * (1 + 2 * (T - 1)) + 1501 ≤
500 * (1 + 2 * time n) + 1501 := by omega
calc total ≤ 15 + (T - 1 + 1) * (500 * (1 + 2 * (T - 1)) + 1501) := htotal
_ ≤ 15 + (time n + 1) * (500 * (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 (scratch + 2) 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 + (scratch + 1)) ans,
(fun _ => 0), PolynomiallyBounded.const 0, ?_⟩
intro input
have hMconst : ∀ t,
M.result (M.run (withScratch (scratch + 2) 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