Two empty work tapes can be merged into one
ProvedSipserGacsLautemann.merge_empty_scratch_tapesA predicate decidable in polynomial time with blank work tapes is decidable in polynomial time with .
This is the easy half of tape elimination, and it is easy for one specific reason: both tapes being merged start empty, so there is nothing to gather and no existing content to re-encode. The two may simply be hosted as two tracks of a single tape, each position carrying one cell of each track together with a flag recording whether that track's head is there. Since exactly one physical head must serve two virtual heads, each simulated step costs a sweep of the region written so far; that region grows by at most one position per step, so the overhead is quadratic — comfortably polynomial.
The statement should not be mistaken for a warm-up exercise. Avoiding the re-encoding phase does not avoid the per-step simulation argument: the flags, the sweeps, and the invariant relating the simulated configuration to the physical one are all still required. It is the full construction minus one phase.
import Definitions.Def_sgl_scratch_tapes
namespace SipserGacsLautemann
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 sorry