Scratch tapes for the mission machine model
Definitionsgl_scratch_tapesScratch tapes: the missing notion of blank working storage in the mission's machine model.
DecidesInPolynomialTime on supplies exactly tapes, every one preloaded with a component of the input. There is no blank work tape anywhere in the model, and nothing in the development provides one: the encoded simulation preserves the tape count, and decidesInPolynomialTime_add_unused_tape runs the other way, adding a tape to the input rather than handing out scratch.
This is a hard obstruction rather than an inconvenience. One of the mission's open frontier obligations asks for a TypedMachine 3 that simulates a Machine 4, so tape multiplexing is forced by the statement itself. More broadly, without scratch one cannot even show that is closed under intersection: running a second machine requires somewhere to record the first one's answer.
This module supplies the notion. withScratch s x pads an input tuple with empty tapes, and
asserts decidability of in polynomial time by a machine granted extra tapes, each of which starts empty. decidesInPolynomialTimeWithScratch_zero records that at this collapses exactly to the mission's own DecidesInPolynomialTime, so the notion is a conservative extension rather than a new primitive.
The point of the definition is that it makes the obstruction addressable by a single theorem: provisioning any number of scratch tapes reduces, by induction, to eliminating one.
import Definitions.Def_sgl_vote_fold
/-!
# Scratch tapes
`DecidesInPolynomialTime` on `Fin k → List Bool` supplies exactly `k` tapes,
every one of them preloaded with a component of the input. There is no blank
work tape anywhere in the model, and nothing in the development provides one:
`encodedSimulation` preserves the tape count, and
`decidesInPolynomialTime_add_unused_tape` runs the other way, adding a tape to
the *input* rather than handing out scratch.
That is a hard obstruction rather than an inconvenience. One of the mission's
open frontier obligations asks for a `TypedMachine 3` that simulates a
`Machine 4`, so tape multiplexing is forced by the statement itself. More
broadly, without scratch one cannot even show `P` closed under intersection:
running a second machine requires somewhere to record the first one's answer.
This module introduces the missing notion and reduces it to a single theorem.
`DecidesInPolynomialTimeWithScratch scratch P` is decidability by a machine with
`scratch` extra tapes that start empty. The provisioning theorem — that this
implies ordinary `DecidesInPolynomialTime` — then follows by induction from the
elimination of **one** blank tape, so all the difficulty is concentrated in that
single step.
-/
namespace SipserGacsLautemann
variable {tapes : Nat}
/-- An input tuple padded with `scratch` empty tapes. -/
def withScratch (scratch : Nat) (input : Fin tapes → List Bool) :
Fin (tapes + scratch) → List Bool :=
fun i => if h : i.val < tapes then input ⟨i.val, h⟩ else []
@[simp] theorem withScratch_zero (input : Fin tapes → List Bool) :
withScratch 0 input = input := by
funext i
have h : i.val < tapes := i.isLt
simp [withScratch, h]
/-- Decidability in polynomial time by a machine granted `scratch` extra tapes,
each of which starts empty. For `scratch = 0` this is exactly
`DecidesInPolynomialTime`. -/
def DecidesInPolynomialTimeWithScratch (scratch : Nat)
(predicate : (Fin tapes → List Bool) → Prop) : Prop :=
∃ (states : Nat) (machine : Machine (tapes + scratch) states) (time : Nat → Nat),
PolynomiallyBounded time ∧
∀ input : Fin tapes → List Bool,
(machine.acceptsWithin (withScratch scratch input)
(time (totalInputLength (withScratch scratch input))) ↔
predicate input) ∧
(machine.rejectsWithin (withScratch scratch input)
(time (totalInputLength (withScratch scratch input))) ↔
¬predicate input)
/-- With no scratch tapes the notion collapses to the mission's own. -/
theorem decidesInPolynomialTimeWithScratch_zero
(predicate : (Fin tapes → List Bool) → Prop) :
DecidesInPolynomialTimeWithScratch 0 predicate ↔
DecidesInPolynomialTime predicate := by
constructor
· rintro ⟨states, machine, time, htime, hcorrect⟩
refine ⟨states, machine, time, htime, ?_⟩
intro input
have h := hcorrect input
rwa [withScratch_zero] at h
· rintro ⟨states, machine, time, htime, hcorrect⟩
refine ⟨states, machine, time, htime, ?_⟩
intro input
have h := hcorrect input
rwa [withScratch_zero]
end SipserGacsLautemann